6
$\begingroup$

Question states: "Let $D_n$ denote the determinant of the $n$-by-$n$ matrix whose $(i,j)$th element (the element in the $i$th row and $j$th column) is the absolute value of the difference between $i$ and $j$. Show that $D_n = (-1)^{n-1}(n-1)2^{n-2}$."

It seems like that I can get a recurrence relation (especially the question was from a book chapter dealing with recursion). In trying to get a recurrence relation, here is what I have done so far:

(Let $R_k$ denote the $k$th row and let $(i,j)$ denote the element/spot of $i$th row and $j$th spot)

1) replace $R_1$ with $R_1-(R_2+R_{n-1})$ to get $R_1^*$

2) replace $R_1^*$ with $R_1^*+R_{n-2}$

3) If I am not mistaken, I should have $-2$ on $(1,1)$, $2$ on both $(1,n-1)$ and $(1,n)$, and all other element in the first row as $0$.

4) take out $2$ from the first row, and expand the determinant about the first row

5) I should have $D_n=2(-D_{n-1}+(-1)^n B_{n-1})$, where $B_{n-1}$ is the determinant of a not-easily-reducible mayrix whose last column consists of $n-1$ ones followed by one $-1$.

How should I go about from now on? Once I get a recurrence relation, it would be pretty easy to get the explicit formula for $D_n$ using induction.

P.S. This question apparently is a question taken from 1969 Putnam Competition

$\endgroup$
  • $\begingroup$ 1) For reference, such a matrix is constant along its diagonals and so is a Toeplitz matrix. 2) If one can find the eigenvectors of $D_n$, then the determinant is the product of the eigenvalues. So if these can be found by inspection, then the determinant can be computed directly. $\endgroup$ – Semiclassical Jan 2 '17 at 0:49
  • $\begingroup$ If you say that is Putnam, then you also have the solution here $\endgroup$ – Momo Jan 2 '17 at 0:51
  • $\begingroup$ In general, if $A=((a_{ij}))^{n\times n}$ such that $a_{ij}=|x_i-x_j|$ where $x_1\le x_2\le...\le x_n\in\mathbb{R}$, then it can be shown that $\det A=2^{n-2}(x_n-x_1)\prod_{i=1}^{n-1}(x_i-x_{i+1})$ effectively by the two successive operations $C_i'=C_i-C_{i+1}$ for $i=1,2,...,n-1$ and $R_i'=R_i+R_1$ for $i=2,3,...,n$. $\endgroup$ – StubbornAtom Mar 22 '17 at 18:34
4
$\begingroup$

As I said in the comments, the solution is here. I am copying it on this page just in case the referencing page gets deleted.

For $i = 1, 2, 3, ... , n-2$ subtract twice row $i+1$ from row $i$ and add row $i+2$ to row $i$. For $i < n-1$, row $i$ becomes all $0$s except for a $2$ in column $i+1$.

Now expand successively by the first, second, third ... rows to get $(-2)n-2$ times the $2 \times 2$ determinant with first row $n-2, 1$ and second row $n-1, 0$. This $2 \times 2$ determinant has value $-(n-1)$, so $|A| = (-1)^{n-1} (n-1) 2^{n-2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.