Associated Topics || Dr. Math Home || Search Dr. Math

### Determinants of a N x N Matrix

```Date: 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/
```
Associated Topics:
College Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search