SEARCH HOME
 Math Central Quandaries & Queries
 Question from Bhavya, a student: Let Cn be the undirected graph with vertex set V = {1,2,3,...,n} and edge set E = {(1,2), (2,3), (3,4),.... , (n-1,n), (n,1)}. Let An be the adjacency matrix of Cn. a. Find the determinant of An. b. Find (An)^2

Bhavya,

Write out the matrix for (say) n=5 - this won't take you very long.

The expansion of the determinant has n! terms, one for every permutation p() of {1,2,..n}. The term is equal to

A[1,p(1)]*A[2,p(2)]*...*A[n,p(n)]*(-1)sign(p)

The only mysterious part here is the sign of the permutation. This is the number of pair swaps needed to achieve it starting from the identity; a slightly deep theorem of combinatorics says that while this is not well-defined, it IS well defined modulo 2, which is all you need in order to raise -1 to that power. [In other words, a position reachable in an odd number of swaps cannot be reached in an even number of swaps. Or, as swaps are self-inverse, no odd sequence of swaps can return to the original position.]

Equivalently there is one term for every subset S of the matrix such that S has exactly one element in each row and in each column. This is visually appealing but doesn't give an easy expression for the sign.

OK now - for your 5x5 matrix how many of these 120 terms are nonzero? This won't take you long either.

You should now be able to find the answer.

Good Hunting!
RD

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.