Determinant and inverse matrix calculation of a special matrix [duplicate]

Question

Is there any smart way of calculating the determinant of this kind matrix?

\begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ 2 & 1 & 2 & \cdots & n-1 \\ 3 & 2 & 1 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & n-1 & n-2 & \cdots & 1 \end{pmatrix}

I encountered this in a problem for the case $n=4$. I need to find the inverse matrix.
I doubt the idea of this problem is to calculate all the cofactors and then the inverse matrix in the usual way.
I see the pattern here and some recursive relations... but I am not sure if this helps for calculating the determinant of the existing matrix.

Answer 1

$$\begin{vmatrix} 1 & 2 & 3 & \cdots & n \\ 2 & 1 & 2 & \cdots & n-1 \\ 3 & 2 & 1 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n & n-1 & n-2 & \cdots & 1 \end{vmatrix}$$ Notice the sum of an element from the first column and an element from the last column (with the same row) will always be equal to $n+1$,thus we can do $(C_1 = C_1+C_n)$ $$ = \begin{vmatrix} n+1 & 2 & 3 & \cdots & n \\ n+1 & 1 & 2 & \cdots & n-1 \\ n+1 & 2 & 1 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ n+1 & n-1 & n-2 & \cdots & 1 \end{vmatrix} = (n+1) \begin{vmatrix} 1 & 2 & 3 & \cdots & n \\ 1 & 1 & 2 & \cdots & n-1 \\ 1 & 2 & 1 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & n-1 & n-2 & \cdots & 1 \end{vmatrix}$$ From here, we can do as follows:
go from the last row towards the first and decrease each row's value with the one above it (for any row but the first one). ($\forall i \neq 1, R_i=R_i-R_{i-1}$, Starting with $i=n$ then $i=n-1 ... i=2$). $$ = (n+1)\begin{vmatrix} 1 & 2 & 3 & \cdots & n \\ 0 & -1 & -1 & \cdots & -1 \\ 0 & 1 & -1 & \cdots & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 1 & \cdots & -1 \end{vmatrix}$$ Expand $C_1$: $$ = (n+1)\begin{vmatrix} -1 & -1 & -1 & \cdots & -1 \\ 1 & -1 & -1 & \cdots & -1 \\ 1 & 1 & -1 & \cdots & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & -1 \end{vmatrix}$$ Now Add the first row to all of the other rows ($\forall i \neq 1, R_i = R_i + R_1$). $$ = (n+1)\begin{vmatrix} -1 & -1 & -1 & \cdots & -1 \\ 0 & -2 & -2 & \cdots & -2 \\ 0 & 0 & -2 & \cdots & -2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -2 \end{vmatrix} = (n+1)[-(-2)^{n-2}]$$

Answer 2

If it’s the determinant you are looking for, then what if you subtract column $j+1$ from column $j$ to get the matrix

$$\begin{pmatrix} -1 & -1 & -1& \cdots & n \\ 1& -1 & -1& \cdots & n-1 \\ 1& 1& -1 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1& 1& 1& \cdots & 1 \end{pmatrix}_{n\times n}$$

Then you could add the bottom row to the top row to get $[0,0,...,n+1]$ then the determinant will be $$(-1)^{n+1}(n+1)\begin{vmatrix} 1& -1 & -1& \cdots & -1\\ 1& 1& -1 & \cdots & -1\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1& 1& 1& \cdots & 1 \end{vmatrix}_{(n-1)\times(n-1)}$$

From which you can always add the bottom row to the top to get $[2,0,...,0]$, so you end up getting

$(-1)^{n+1}(n+1)2^{n-2}$?

It looks like for the $n \times n$ matrix $A$ given, the inverse has the general form

$$B= \begin{pmatrix} \frac{-n}{2(n+1)}& \frac{1}{2} & 0 & 0 &\cdots & 0 & \frac{1}{2(n+1)} \\ \frac{1}{2} & -1 & \frac{1}{2} & 0 & \cdots & 0& 0 \\ 0 & \frac{1}{2} & -1 & \frac{1}{2} & \cdots & 0&0 \\ 0 & 0 & \frac{1}{2} & -1 & \cdots & 0&0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots &\vdots\\ 0 & 0 & 0 & 0 & \cdots &-1&\frac{1}{2}\\ \frac{1}{2(n+1)} & 0 & 0 & 0& \cdots &\frac{1}{2}& \frac{-n}{2(n+1)} \end{pmatrix} $$

I don't really have proof of how I got this except plugging in the matrix to an inverse matrix calculator for various values of $n$ and noticing a pattern. But one can certainly check that it is indeed the inverse, multiplying on the left and getting $B\cdot A=I$ ensures it is the inverse.

To check this, when multiplying this matrix on the left, it’s not hard to check for the rows of the form $[0,...,\frac{1}{2},-1,\frac{1}{2},...,0]$ because either we have three consecutive integers $n,n+1,n+2$ or $n,n-1,n-2$ $$\frac{n}{2}-(n+1)+\frac{n+2}{2}=0$$ $$\frac{n}{2}-(n-1)+\frac{n-2}{2}=0$$ or $$2\cdot\frac{1}{2}+(-1)\cdot 1+ 2\cdot \frac{1}{2}=1$$ which always is a diagonal entry. Then considering the top row:

$$\frac{-n}{2(n+1)} + 2\cdot \frac{1}{2} + \frac{n}{2(n+1)}=1$$

$$(i+1)\cdot\frac{-n}{2(n+1)}+ i\cdot \frac{1}{2} + (n-i)\cdot \frac{1}{2(n+1)}=0$$ for $i=1,2,...,n-1$.

The bottom row acts similarly. Thus we indeed get $I$. This probably yields to a nice method to find the inverse through $[A|I] \rightsquigarrow [I|B]$.

Hope this helps!

Answer 3

Treat $n$ as a parameter, let

• $M$ be your $n \times n$ matrix.
• $\eta$ be the $n\times n$ matrix with $1$ on the lower diagonal and $0$ otherwise.
• $\bar{\eta}$ be the transpose of $\eta$.
• $u$ be the $n \times 1$ column vector with all entries $1$.
• $e$ be the $n \times 1$ column vector with $1$ on first row and $0$ otherwise.
• $f$ be the $n \times 1$ column vector with $1$ on last row and $0$

There are several algebraic facts we need.

1. $\eta$ and $\bar{\eta}$ are nil-potent. More precisley, $\eta^n = \bar{\eta}^n = 0$.

2. $\eta\bar{\eta} = I - ee^T$ and $\bar{\eta}\eta = I -ff^T$.

3. $uu^T = (I-\eta)^{-1} + \bar{\eta}(I-\bar{\eta})^{-1} = (I-\eta)^{-1}\eta + (I-\bar{\eta})^{-1}$.

4. $(I - \eta)u = e$, $(1 - \bar{\eta}) u = f$ and $(I - \bar{\eta}) e = e$.

If one look at the lower triangular part of $M$, it equals to $$I + 2\eta + 3\eta^2 + \cdots + n\eta^{n-1} = (I - \eta)^{-2}$$ Similar things happens to the upper triangular part of $M$. This leads to:

$$ \begin{align}M &= (I - \eta)^{-2} + (I-\bar{\eta})^{-2} - I\\ &= (I-\eta)^{-1}(uu^T - \bar{\eta}(1-\bar{\eta})^{-1}) + (uu^T - (1-\eta)^{-1}\eta)(1 - \bar{\eta})^{-1} - I\\ &= (I-\eta)^{-1}((ue^T - \bar{\eta}) + (eu^T - \eta))(1-\bar{\eta})^{-1} - I \end{align} $$ As a result, following product of matrix has a relatively simple structure:

$$\begin{align} N \stackrel{def}{=} (1-\eta)M(1-\bar{\eta}) &= (eu^T - \eta) + (ue^T - \bar{\eta}) - (I - \eta)(I - \bar{\eta})\\ &= ee^T + eu^T + ue^T - 2I \end{align}$$

Let $v = \frac{u - e}{\sqrt{n-1}}$. It is easy $e, v$ are orthogonal unit vectors. Extend $\{ e, v \}$ to an orthonormal basis. In the new basis, $N$ is block-diagonalized and has the form $$N_{new} = \begin{bmatrix} 1 & \sqrt{n-1} & 0 & 0 & \ldots & 0\\ \sqrt{n-1} & -2 & 0 & 0 & \ldots & 0\\ 0 & 0 & -2 & 0 & \ldots & 0\\ 0 & 0 & 0 & -2 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & 0 & \ldots & -2 \end{bmatrix}$$ Since $\det(1-\eta) = \det(1-\bar{\eta}) = 1$, we find

$$\det(M) = \det(N) = (-2-(n-1))(-2)^{n-2} = -(n+1)(-2)^{n-2}$$

In the new basis, inverting $N$ comes down to inverting a $2 \times 2$ matrix. In terms of $e, v$, we have

$$\begin{align} N^{-1} &= \frac{1}{n+1}(2 ee^T + \sqrt{n-1}(ve^T + ev^T) - vv^T) - \frac12(I - ee^T - vv^T)\\ &= \frac{ue^T + eu^T}{n+1} + (\frac12-\frac{1}{n+1})vv^T - \frac12(I- ee^T)\\ &= \frac{ue^T + eu^T}{n+1} + \frac{(u-e)(u-e)^T}{2(n+1)} - \frac12(I - ee^T)\\ &= \frac{(u+e)(u+e^T)}{2(n+1)} - \frac12(I- ee^T) \end{align} $$ This leads to $$\begin{align}M^{-1} &= (1-\bar{\eta})N^{-1}(1-\eta)\\ &= \frac{(e+f)(e+f)^T}{2(n+1)} - \frac12((I-\bar{\eta})(I-\eta)-ee^T)\\ &= \frac{(e+f)(e+f)^T}{2(n+1)} - \frac12(I - \eta - \bar{\eta} + \bar{\eta}\eta - ee^T)\\ &= \underbrace{-I + \frac12(\eta + \bar{\eta})}_J + \underbrace{\frac{(n+2)(ee^T+ff^T) + (ef^T+fe^T)}{2(n+1)}}_K \end{align} $$ This implies $M^{-1}$ is very close to a tri-diagonal matrix

$$J = -I + \frac12(\eta + \bar{\eta}) \quad\text{ with }\quad J_{ij} = \begin{cases} -1, & i = j\\ \frac12, & |i - j| = 1\\ 0, & \text{ otherwise } \end{cases}$$

The difference $K$ is non-zero only at following $4$ entries:

$$K_{11} = K_{nn} = \frac{n+2}{2(n+1)},\quad K_{n1} = K_{1n} = \frac{1}{2(n+1)}$$

As an example, following is what $M^{-1}$ looks like at $n = 7$. $$\begin{bmatrix}-\frac{7}{16} & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{16}\cr \frac{1}{2} & -1 & \frac{1}{2} & 0 & 0 & 0 & 0\cr 0 & \frac{1}{2} & -1 & \frac{1}{2} & 0 & 0 & 0\cr 0 & 0 & \frac{1}{2} & -1 & \frac{1}{2} & 0 & 0\cr 0 & 0 & 0 & \frac{1}{2} & -1 & \frac{1}{2} & 0\cr 0 & 0 & 0 & 0 & \frac{1}{2} & -1 & \frac{1}{2}\cr \frac{1}{16} & 0 & 0 & 0 & 0 & \frac{1}{2} & -\frac{7}{16}\end{bmatrix}$$

One can see that $M^{-1}_{17} = M^{-1}_{71} = \frac{1}{2(7+1)} = \frac{1}{16}$ and $M^{-1}_{11} = M^{-1}_{77} = \frac{7+2}{2(7+1)} - 1 = -\frac{7}{16}$. Matching what we have computed before.

Answer 4

Call your matrix $A$. Let $\{e_1,e_2,\ldots,e_{n-1}\}$ be the standard basis of $\mathbb R^{n-1}$. Let also $e=\sum_ie_i=(1,1,\ldots,1)^T$ and $$ L=\pmatrix{1\\ -1&1\\ &\ddots&\ddots\\ &&-1&1}. $$ Then $B:=LAL^T=\pmatrix{1&e^T\\ e&-2I_{n-1}}$. Using Schur complement, we obtain $$ \det(A)=\det(B)=\det(-2I_{n-1})\left(1-e^T(-2I_{n-1})^{-1}e\right)=(-2)^{n-1}\frac{n+1}{2}. $$ To find $A^{-1}$, partition $L$ as $\pmatrix{1&0\\ -e_1&L'}$. Then \begin{aligned} A^{-1} &=L^TB^{-1}L\\ &=\pmatrix{1&-e_1^T\\ 0&L'^T} \pmatrix{\frac{2}{n+1}&\frac{1}{n+1}e^T\\ \frac{1}{n+1}e&\frac{1}{2(n+1)}ee^T-\frac12I_{n-1}} \pmatrix{1&0\\ -e_1&L'}\\ &=\pmatrix{\frac{1}{n+1}&\frac{1}{2(n+1)}e^T+\frac12e_1^T\\ \ast&\frac{1}{2(n+1)}e_ne^T-\frac12L'^T} \pmatrix{1&0\\ -e_1&L'}\\ &=\pmatrix{\frac{-n}{2(n+1)}&\frac{1}{2(n+1)}e_n^T+\frac12e_1^T\\ \ast&\frac{1}{2(n+1)}e_ne_n^T-\frac12L'^TL'}. \end{aligned} By direct calculation, $L'^TL'$ is the symmetric tridiagonal matrix whose main diagonal is $(2,\ldots,2,1)$ and whose superdiagonal is a vector of $-1$s. Since $A^{-1}$ is symmetric, we finally get $$ A^{-1}=\pmatrix{ \frac{-n}{2(n+1)}&\frac12&&&\frac{1}{2(n+1)}\\ \frac12&-1&\frac12\\ &\frac12&-1&\ddots\\ &&\ddots&\ddots&\frac12\\ \frac{1}{2(n+1)}&&&\frac12&\frac{-n}{2(n+1)} }. $$

Answer 5

On a related note, the inverse of the closely related matrix $(a_{ij}) = (\frac{n}{4}- \frac{1}{2} |i-j|)$ is still Toeplitz and symmetric with first row $(2,-1, 0, \ldots, 0, 1)$, determinant $4$, and eigenvalues coming in pairs ( and a $4$, when $n$ odd). Moreover, one can explicitely find the eigenvectors of this inverse, using trigonometric functions. Now, there is a formula for the inverse of a peturbation of a matrix by a matrix of rank $1$. So finding the inverse is feasible.

As an example, check out this inverse ( case $n=5$): WA link .