# Determinant of a special matrix

The question is related to the eigenvalue problem. Using MAPLE, I calculated the following determinants:

\begin{align} \begin{vmatrix} -\lambda & 1 \\ 1 & -\lambda \\ \end{vmatrix}&=\lambda^2-1\\ \begin{vmatrix} -\lambda & 1 & 0 \\ 1& -\lambda & 1 \\ 0& 1 & -\lambda \\ \end{vmatrix}&=-\lambda^3+2\lambda\\ \begin{vmatrix} -\lambda & 1 &0 &1 \\ 1& -\lambda & 1 &0 \\ 0& 1& -\lambda & 1 \\ 1& 0& 1& -\lambda \\ \end{vmatrix}&=\lambda^4-4\lambda^2\\ \begin{vmatrix} -\lambda &1 &0 &1 &0 \\ 1& -\lambda &1 &0 &1 \\ 0& 1& -\lambda &1 &0 \\ 1& 0& 1& -\lambda &1 \\ 0& 1& 0& 1& -\lambda \\ \end{vmatrix}&=-\lambda^5+6\lambda^3\\ \begin{vmatrix} -\lambda &1 &0 &1 &0 &1 \\ 1& -\lambda &1 &0 &1 &0 \\ 0& 1& -\lambda &1 &0 &1 \\ 1& 0& 1& -\lambda &1 &0 \\ 0& 1& 0& 1& -\lambda &1 \\ 1& 0& 1& 0&1 & -\lambda \\ \end{vmatrix}&=-9\lambda^4+\lambda^6\\ \end{align} But I have no idea how to calculate the determinants quickly by hand. Here is my question:

What is the determinant in the $n$ by $n$ case?

-
The determinant of the $3 \times 3$ matrix is actually $-x^3 + 2x$. This should help establish a pattern, at least for the leading term of the polynomial. –  JavaMan Jul 27 '11 at 18:18
There's something wrong in the computation of the second determinant: the determinant should be a polynomial of degree $3$ in $\lambda$ with leading coefficient $-1$, not $-3$. –  Arturo Magidin Jul 27 '11 at 18:18
Doing a quick look, is your 3 by 3 case correct? It seems that the leading coefficient should always be either 1 or negative 1 so perhaps you just meant $- \lambda ^3 + 2 \lambda$? –  mixedmath Jul 27 '11 at 18:20
@DJC,@Arturo: Corrected, thanks. –  Jack Jul 27 '11 at 18:20
What if we permute the indices of the rows and columns, so that instead of listing them in the order 1, 2, 3, 4, 5, 6, we write them in the order 1, 3, 5, 2, 4, 6, i.e. first odd, then even? We get: $$\begin{bmatrix} -\lambda & 0 & 0 & 1 & 1 & 1 \\ 0 & -\lambda & 0 & 1 & 1 & 1 \\ 0 & 0 & -\lambda & 1 & 1 & 1 \\ 1 & 1 & 1 & -\lambda & 0 & 0 \\ 1 & 1 & 1 & 0 & -\lambda & 0 \\ 1 & 1 & 1 & 0 & 0 & -\lambda \end{bmatrix}$$ The eigenvalues of the $3\times 3$ matrix of 1s are: 3, 0, 0. –  Michael Hardy Jul 27 '11 at 18:26

You are computing the characteristic polynomial of the matrix whose rows/columns alternate $0$ and $1$s, with first row beginning with $0$, second row beginning with $1$, then $0$, then $1$, etc.

The matrix is symmetric, hence diagonalizable; in particular, the dimension of the nullspace equals the multiplicity of $0$ as a root of the characteristic polynomial. Since the matrix is $n\times n$ and has rank $2$, the multiplicity of $\lambda=0$ as a root of the characteristic polynomial is $n-2$. Thus, the polynomial is a multiple of $(-1)^n\lambda^{n-2}$. Hence it is of the form $(-1)^n\lambda^{n-2}p(\lambda)$, where $p(\lambda)$ is a monic polynomial of degree $2$.

The only remaining question is what are the two other eigenvalues.

Looking at your pattern, you have the following values for $p(\lambda)$: \begin{align*} n&=2 &\qquad p(\lambda)&= \lambda^2-1\\ n&=3 &\qquad p(\lambda)&= \lambda^2-2\\ n&=4 &\qquad p(\lambda)&= \lambda^2-4\\ n&=5 &\qquad p(\lambda)&= \lambda^2-6\\ n&=6 &\qquad p(\lambda)&= \lambda^2-9 \end{align*}

For even $n$, $n=2k$, it seems reasonable to conjecture that $p(\lambda)=\lambda^2-k^2$. A simple way to verify this is to show that the matrix has eigenvectors associated to $k$ and to $-k$. For example, when $k=2$, the matrix is $$\left(\begin{array}{cccc} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \end{array}\right).$$ It is easy to verify that $(1,-1,1,-1)^t$ is an eigenvector associated to $-2$, and that $(1,1,1,1)^t$ is an eigenvector associated to $2$. Similar vectors will work for all even $n$.

For odd $n$, it seems a bit tricker, but the same basic idea works. Try to find appropriate eigenvectors and eigenvalues, which is very easy to do. Suggestion. Due to the symmetry, it seems like a good idea to look for an eigenvector $(a_1,a_2,\ldots,a_n)^t$ with $a_1=a_3=a_5=\cdots=a_n$ and $a_2=a_4=\cdots=a_{n-1}$. By scaling, we may assume that $a_1=1$, and $a_2=r$ for some $r$. If $n=2k+1$, then applying the matrix to such a vector will give you that the odd entries of the image have value $kr$, and the even entries have value $k+1$. If you want this to be an eigenvector associated to some $\lambda\neq 0$, then you want $\lambda = kr$, and $\lambda r = k+1$; take it from there.

Moral. While we usually think of the characteristic polynomial as "the easy way" to find the eigenvalues, it's important to remember that the relationship goes both ways: every eigenvalue you can find gives you a linear factor of the characteristic polynomial too. It's often useful to "play one against the other". Here, the determination of "most" of the roots follows by staring at the matrix, and because the matrix is highly structured it turns out to be easier to find the eigenvalues directly than trying to compute the characteristic polynomial and then factoring.

-
Hmm, we often find the eigenvalues first and then the eigenvectors. It's interesting to see that in this case we do somewhat the opposite. –  Jack Jul 27 '11 at 19:11
I don't quite follow you in the second paragraph that why the factor is $(-1)^n\lambda ^{n-2}$ instead of $\lambda^{n-2}$. After all, the $n-2$ multiple root $0$ gives the factor $C\lambda^{n-2}$ where $C$ is a nonzero constant. –  Jack Jul 27 '11 at 19:20
@Jack: The leading coefficient of the characteristic polynomial of an $n\times n$ matrix is $(-1)^n$. By pulling out the $(-1)^n$ into the factor that "we already know", I am left with a monic quadratic polynomial still to be determined. If you only factor out $\lambda^{n-2}$, then the remaining factor will be a quadratic polynomial with leading coeffcient $(-1)^{n}$, and why bother with that leading coefficient, if we can put it into the "known part" immediately? –  Arturo Magidin Jul 27 '11 at 19:22
Fair enough. So you first factor out the known part $(-1)^n\lambda^{n-2}$ which is from the spectrum theorem as I understand, then you use the possible eigenvectors to find the quadratic part, i.e., the two nonzero eigenvalues. Correct? –  Jack Jul 27 '11 at 19:28
@Jack: Essentially, yes. I factor out $(-1)^n\lambda^{n-2}$, then look for a pattern in what's left. For even $n$, the pattern is obvious, so we try it: find eigenvectors with eigenvalues $k$ and $-k$, that gives the roots of the quadratic (note that in the even case, all rows add up to $k$, so $(1,\ldots,1)^t$ must be an eigenvector). For odd $n$ the pattern may not be so obvious, so we play a bit with possible eigenvectors (trying simplified vectors first because they are easier); turns out that one can quickly figure out what two other eigenvalues/eigenvectors are, which finishes it. –  Arturo Magidin Jul 27 '11 at 19:31

Let us denote the matrix in $n$-dimensions by $\Lambda_n$ and the two non vanishing eigenvalues by $a$ and $b$. We have

$a+b = tr(\Lambda_n) = 0$

$a^2+b^2 = tr(\Lambda_n^2) = 2\lceil \frac{n}{2}\rceil\lfloor\frac{n}{2}\rfloor$

which implies that:

$a ^2= b^2 =-ab = \lceil \frac{n}{2}\rceil \lfloor\frac{n}{2}\rfloor$

Thus the two nonvanishing eigenvalues contributtion to the characteristic polynomial:

$\lambda^2-\lceil \frac{n}{2}\rceil \lfloor\frac{n}{2}\rfloor$

-

Based on the given results, you should be able to guess what the eigenvalues are. Can you write down an explicit set of eigenvectors for those eigenvalues? Does your construction generalize?

-