Consider the set of $n\times n$ matrices $M_n$ where the entry in row $i$ and column $j$ is defined by$$m_{i,j}=\begin{cases}0&\text{for }i=j\[1ex]1&\text{otherwise}\end{cases}$$so for instance,$$M_2=\begin{pmatrix}0&1\[1ex]1&0\end{pmatrix}\quad\text{and}\quad M_3=\begin{pmatrix}0&1&1\[1ex]1&0&1\[1ex]1&1&0\end{pmatrix}$$and so on.

Show that for positive integers $n\ge1$,
$$\det M_n=(-1)^{n-1}(n-1)$$

Question

Consider the set of $n\times n$ matrices $M_n$ where the entry in row $i$ and column $j$ is defined by$$m_{i,j}=\begin{cases}0&\text{for }i=j\[1ex]1&\text{otherwise}\end{cases}$$so for instance,$$M_2=\begin{pmatrix}0&1\[1ex]1&0\end{pmatrix}\quad\text{and}\quad M_3=\begin{pmatrix}0&1&1\[1ex]1&0&1\[1ex]1&1&0\end{pmatrix}$$and so on.

Show that for positive integers $n\ge1$,
$$\det M_n=(-1)^{n-1}(n-1)$$

anonymous · Answer

I stumbled across this pattern while playing around with a system of recurrence relations that correspond to the matrices $M_n$ for $n\ge2$ (but it's true for $n=1$). I've been trying to prove this by induction, but the inductive step is tricky to me.

Manually crunching the numbers via cofactor expansions gets messy quickly. The pattern holds, ie. $\det M_2=-1$ and $\det M_3=2$ and so on, and I've verified with Mathematica for up to $n=100$.

Aside - the system of recurrence relations I mentioned. I've been looking at the system$$\begin{cases}a_0=A\[1ex]b_0=B\[1ex]a_{n+1}=b_n\[1ex]b_{n+1}=a_n\end{cases}~~\iff~~\begin{pmatrix}a_{n+1}\[1ex]b_{n+1}\end{pmatrix}=\begin{pmatrix}0&1\[1ex]1&0\end{pmatrix}\begin{pmatrix}a_n\[1ex]b_n\end{pmatrix}$$and the extension to $n$ equations$$\begin{pmatrix}a_{1,k+1}\[1ex]\vdots\[1ex]a_{n,k+1}\end{pmatrix}=M_n\begin{pmatrix}a_{1,k}\[1ex]\vdots\a_{n,k}\end{pmatrix}$$and it turns out that the determinant of each $M_n$ seems to play a role in one of the coefficients of the generating functions for the sequences $a_i$.

anonymous · Answer

The cofactor expansions for small $n$ gave me a basic pattern of being able to reduce the determinant of the initial matrix $\det M_n$ into significantly simpler determinants of $2\times2$ matrices, and these determinants are exclusively $1$, $0$, or $-1$. I don't think this helps in a proof by induction, though, but I'm not entirely convinced. Unless there's some way to inductively (or otherwise) prove that
$$\det M_n=\sum (\det m_a+\det m_b+\det m_c)$$where $m_a,m_b,m_c$ are all $2\times2$ matrices with determinants $1$, $0$, $-1$ respectively.

ganeshie8 · Answer

alternatively, elimination may work nicely

anonymous · Answer

I've also considered writing $M_n$ as $C_n-I_n$, where $C_n$ is a constant matrix composed entirely of $1$s, but alas, $\det(C_n-I_n)\neq\det C_n-\det I_n$.

ganeshie8 · Answer

1) $R_1 + R_2+\cdots + R_n$ makes all the elements in the first row equal to $(n-1)$

2) pull $n-1$ out from first row

3)  do $R_i - R_1$ for other rows to get a upper triangular matrix with $-1$ in the diagonal in all the below $n-1$ rows

4) multiply the entries in diagonal to get determinant

anonymous · Answer

Oh good call on the triangulizing (?)

ganeshie8 · Answer

that looks more like a construction based proof...im still thinking of induction.. .

ganeshie8 · Answer

hey may i see the generating function of $\{a_n\}$

anonymous · Answer

Still, a useful technique!

A cofactor expansion of $M_{k+1}$ gives
$$\det M_k+\sum(\text{other matrices})=(-1)^{k-1}(k-1)+\cdots$$Cheating a bit, and "knowing" the RHS should add up to $(-1)^kk$, we get
$$\sum(\text{other matrices})=(-1)^k(2k-1)$$but whether that gives any useful results, I'm not sure.

anonymous · Answer

Here are the GFs for $a_n$ and $b_n$ in the case of the $2$ recurrence system. I got
$$a(x)=\color{red}{\frac{A+Bx}{1-x^2}}=\sum_{k\ge0}\left(\frac{A+B}{2}+(-1)^n\frac{A-B}{2}\right)x^n\
b(x)=\color{blue}{\frac{B+Ax}{1-x^2}}=\sum_{k\ge0}\left(\frac{A+B}{2}+(-1)^n\frac{B-A}{2}\right)x^n$$(possibly a typo somewhere, I wouldn't be surprised)

anonymous · Answer

I've only solved the double recurrence so far, and I have the GFs for the triple recurrence, but I've already made a basic conjecture that $\det M_n$ gives the coefficient of the highest power term in the denominator (possibly multiplied by a power of $-1$)

anonymous · Answer

Here's the set of GFs for the triple recurrence:
$$\begin{cases}a_0=A;\quad b_0=B;\quad c_0=C\[1ex]a_{n+1}=b_n+c_n\[1ex]b_{n+1}=a_n+c_n\[1ex]c_{n+1}=a_n+b_n\end{cases}$$$$a(x)=\frac{Ax-(A-B-C)x^2}{1-x-2x^2}\
b(x)=\frac{Bx-(B-A-C)x^2}{1-x-2x^2}\
c(x)=\frac{Cx-(C-A-B)x^2}{1-x-2x^2}$$I wish I had the time and patience to work with the quadruple recurrence just to see if there's any merit to the conjecture about the leading coefficient.

anonymous · Answer

Interesting observation (though it's actually not completely surprising now that I think about it), for the triple recurrence, the $k$th term of the sequence $\{a_n,b_n,c_n\}$ is given by ${M_3}^k\begin{pmatrix}A\B\C\end{pmatrix}$.

It's probably true then that the $k$th term of $\{a_{1,n},\ldots\,a_{k,j}\}$ is given by ${M_n}^k\begin{pmatrix}A_1\\vdots\A_j\end{pmatrix}$. Pretty neat.

kainui · Answer

I came here to try to figure out and say what ganeshie already did, but I am still figuring stuff out and interested in your recurrence problems more this looks fun.

kainui · Answer

Interesting, it appears that my linear algebra workbook has this fun example of showing that:
$$\det[M_5 -4I]=0$$ 

Which probably generalizes to this (if you don't already know that from earlier I can't say)
$$\det[M_n +(n-1)I]=0$$

anonymous · Answer

$M_n$s the same matrix, right?

kainui · Answer

Yes, actually they have the same exact problem as you're asking, verbatim here it is:

Show that the n-square determinant 
$$\begin{vmatrix}
0 &1  &1  &\cdots  &1 \1 
 &0  &1  &\cdots  &1 \1 
 &1  &0  &\cdots  &1 \\cdots 
 &\cdots  &\cdots  &\cdots  &\cdots \\cdots 
 &\cdots  &\cdots  &\cdots  &\cdots \1 
 &1  &1  &1  &0 
\end{vmatrix} = (n-1)\begin{vmatrix}
0 &1  &1  &\cdots  &1 \1 
 &0  &1  &\cdots  &1 \1 
 &1  &0  &\cdots  &1 \\cdots 
 &\cdots  &\cdots  &\cdots  &\cdots \\cdots 
 &\cdots  &\cdots  &\cdots  &\cdots \1 
 &1  &1  &1  &1 
\end{vmatrix} = (-1)^n (n-1)$$

anonymous · Answer

And here I thought I was being so creative :P

kainui · Answer

Here's another problem in the book! 

$$\begin{vmatrix}
a+b &a  &a  &\cdots  &a \a 
 &a+b  &a  &\cdots  &a \\cdots 
 &\cdots  &\cdots  &\cdots  &\cdots \a 
 &a  &a  &\cdots  &a+b 
\end{vmatrix} = b^{n-1}(na+b)$$

anonymous · Answer

I've also been thinking about another set of matrices with this pattern:
$${M'}_2=M_2\quad\quad{M'}_3=\begin{pmatrix}0&1&2\[1ex]1&0&1\[1ex]2&1&0\end{pmatrix}\quad\quad{M'}_4=\begin{pmatrix}0&1&2&3\[1ex]1&0&1&2\[1ex]2&1&0&1\[1ex]3&2&1&0\end{pmatrix}$$and so on. These also have a cool alternating pattern with their determinants: $-1,4,-12,32,\ldots$.

anonymous · Answer

So basically the entry in row $i$, column $j$ is $|i-j|$.

kainui · Answer

Oooh ok these look cool, they're not just symmetric they're centrosymmetric! https://en.wikipedia.org/wiki/Centrosymmetric_matrix The exchange matrix J is defined as the anti-diagonal (top right to bottom left) version of the identity matrix, then your matrices satisfy the centrosymmetric equation: AJ=JA just like a symmetric matrix satisfies $A=A^\top$ I don't know if that would help/be interest to you, also this reminds me of the pascal triangle matrices $$UL=P$$ So upper triangular pascal matrix times lower triangular pascal matrix gives the full pascal matrix... (might have to put in a third column and row to see the pattern better: $$\begin{bmatrix} 1 &0 \1 &1 \end{bmatrix}\begin{bmatrix} 1 &1 \0 &1 \end{bmatrix}=\begin{bmatrix} 1 &1 \1 &2 \end{bmatrix} $$ Some related problems or ideas for inspiration for now while I think of other stuff.

anonymous · Answer

Haha I was wondering if these types of matrices had a name. For my original $M_n$ I was thinking something like antidiagonal or "pseudodiagonal", but I found the former was already taken.

kainui · Answer

Yeah, there's Persymmetric, Centrosymmetric, Bisymmetric, and Toeplitz matrices which all seem to be pretty closely related, I've looked into this before just from playing around with some permutations since the exchange matrix J had interested me when I tried to solve some problem a while back.

kainui · Answer

So these $M_n'$ matrices you've introduced here are interesting, all I can tell so far is that their determinant is always divisible by (n-1) due to the fact that adding the first column to the last column produces a column with all 1's in it multiplied by (n-1).

anonymous · Answer

Hmm, I wonder how that result might change if we mirror the matrices across their centers (such that ${M'}_2$ becomes $I_2$, for instance).

kainui · Answer

Oh could you explain that a little more what you mean by mirroring, I'm not sure I follow.

kainui · Answer

Although probably far from the beaten path, I still find this to be kind of interesting. You can represent every matrix as the sum of a centrosymmetric and skew-centrosymmetric matrix:

$$A = \frac{A+JAJ}{2}+\frac{A-JAJ}{2} = B+C$$

$BJ=JB$ (hehe) and $CJ=-JC$ are the relations for  centrosymmetric and skew-centrosymmetric

anonymous · Answer

By mirroring (maybe there's an existing term that's more technical) I mean some transformation, let's call it $\mathrm{Mirv}$, that gives
$$\mathrm{Mirv}\begin{pmatrix}1&2&3\[1ex]4&5&6\[1ex]7&8&9\end{pmatrix}=\begin{pmatrix}3&2&1\[1ex]6&5&4\[1ex]9&8&7\end{pmatrix}$$or another transformation $\mathrm{Mirh}$ which gives the transpose of a "mirv'd" matrix. (v for reflection along some vertical axis, h for horizontal)