Determinants of a N x N MatrixDate: 01/16/2004 at 16:45:31 From: Mahbooba Chowdhury Subject: determinants of a n X n matrix If S(i,j) denotes the sum of the common divisors of i and j, show that: |S(1,1) S(1,2) ... S(1,n)| |S(2,1) S(2,2) ... S(2,n)| Det | . . . . | = n! | . . . . | | . . . . | |S(n,1) S(n,2) ... S(n,n)| Getting the entries of the matrix was most difficult, however; showing that the determinant is = n! is very confusing. I have found that the matrix is symmetric and, if we call A the matrix in the question then: |A|=det(A)=(SUM OF)(-1)^(i+j)a_ijM_ij Where M_ij is a minor matrix of A => n-1 by n-1 matrix made by the rows and columns of A except ith row and jth column is not included. Date: 01/18/2004 at 05:59:59 From: Doctor Jacques Subject: Re: determinants of a n X n matrix Hi Mahbooba, This is a very interesting question indeed. Let us look first at an example; the simplest non-trivial example is n = 6. The matrix S is: 1 1 1 1 1 1 1 3 1 3 1 3 S = 1 1 4 1 1 4 1 3 1 7 1 3 1 1 1 1 6 1 1 3 4 3 1 12 As we are asked to prove that det S = 6!, we may start with a matrix whose determinant is obviously 6!, and try to obtain the matrix S by row and column operations that do not change the determinant. An example of a 6*6 matrix with determinant 6! is the matrix A: 1 0 0 0 0 0 0 2 0 0 0 0 A = 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 6 If we look at a particular element, for example 2, we note that S (i,j) must contain a term 2 whenever i and j are multiples of 2. We first add each row "i" to all rows whose indices are multiples of i; this gives the matrix B: 1 0 0 0 0 0 1 2 0 0 0 0 B = 1 0 3 0 0 0 1 2 0 4 0 0 1 0 0 0 5 0 1 2 3 0 0 6 Next, we do the same with columns: we add column "j" to all columns whose indices are multiples of j; we do this starting from the right, to avoid adding the same column twice. Specifically: * We add column 3 to column 6 * We add column 2 to columns 4 and 6 * We add column 1 to all subsequent columns If you check this, you will find that this gives the matrix S we started with. As none of these operations changes the value of the determinant, this shows that det S = 6!. I wrote this to show you the idea of the proof. Now, we must prove that formally, and prove that it works for all n. Remember that adding rows is equivalent to multiplying by a matrix on the left, and adding columns is equivalent to multiplying by a matrix on the right. We start with the matrix A above, defined by: A(i,i) = i A(i,j) = 0 if i <> j Obviously, det A = n! Consider now the matrix Z defined by: Z(i,j) = 1 if i | j (read: i divides j) Z(i,j) = 0 otherwise Note that i | j implies i <= j, which means that Z is upper triangular. The determinant of such a matrix is the product of its diagonal elements, and, in this case, those diagonal elements are all equal to 1, since any number divides itself. To sum up, det Z = 1. (The matrix Z is a particular case of what is called the Zeta matrix; its inverse is called the Möbius matrix, and has many interesting applications.) In our example, the matrix Z is: 1 1 1 1 1 1 0 1 0 1 0 1 A = 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 Note that multiplying on the right by Z will add any column to its "multiples", as we did before. In a similar way, multiplying by Z' (the transpose of Z) on the left will add any row to its "multiples". Formally, we want to show that: S = Z' A Z As det A = n!, and det Z' = det Z = 1, this will prove that det S = n! Now, we have, explicitly: S(i,j) = SUM [ Z'(i,r) A(r,s) Z(s,j) ] = SUM [ Z(r,i) A(r,s) Z(s,j) ] where all indices range from 1 to n, and we must prove that S(i,j) is the sum of the common divisors of i and j. Note that, by the definition of A, the only terms in the sum will be those with r = s, and, in such a case, A(r,s) = r = s. We may therefore drop the index s and replace it by r, and replace A(r,r) by r: S(i,j) = SUM [ r * Z(r,i) * Z(r,j) ] Can you use the definition of Z to show that this corresponds to the definition of the matrix S we started with? Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/