Find the inverse of the $n\times n$ matrix whose entries are given by $a_{ij} = \max (i,j)$

Question

The actual question on the past papers is "Let $n\ge 1$ be an integer and consider the $n\times n$ matrix $A$ whose entries are given by $a_{ij} = \max(i,j)$ for all $1\le i,j\le n$. Show that $A$ is invertible and find the inverse." I have shown the matrix is invertible by finding the determinant to be $(-1)^{n-1}n$ which doesnt equal 0 for any value of $n$. Just wondering if someone can tell me how to find the inverse, I was thinking along the lines of using $A^{-1} = (1/\det(A))\mathrm{adj}(A)$ but I cant figure it out, thanks.

Answer 1

Let $\{e_1,\ldots,e_n\}$ be the standard basis, $e=\sum_ie_i$ be the all-one vector, $E=ee^T$ be the all-one matrix and $U$ be the upper triangular part of $E$. Then $A=(n+1)E-UU^T$. Apply Sherman-Morrison formula and simplify, we get $A^{-1}=\frac{n+1}n e_ne_n^T - U^{-T}U^{-1}$, i.e. $$ A^{-1}=\pmatrix{ -1&1\\ 1&-2&1\\ &1&\ddots&\ddots\\ &&\ddots&\ddots&\ddots\\ &&&\ddots&-2&1\\ &&&&1&\frac{1-n}n}. $$

Answer 2

This solutions is a direct calculation.

The matrix $A$ is something like: $$ A=\left(\begin{array}{ccccc} 1&2&3&\cdots&n\\ 2&2&3&\cdots&n\\ 3&3&3&\cdots&n\\ \vdots&\vdots&\vdots&&\vdots\\ n-1&n-1&n-1&\cdots&n\\ n&n&n&\cdots&n \end{array}\right) $$

Let $v$ be a $n\times 1$ matrix, write $$ v=\left(\begin{array}{c}x_1\\x_2\\x_3\\\vdots\\x_n\end{array}\right) $$ and calculate $Av$. Denote by $e_i$ the $n\times 1$ matrix with entry $1$ in the $i$-th line and $0$ in the other entries. Then, the condition $Av=e_i$ implies necessarily:

Step 1: $x_j=0$ for $j=1,2,\cdots,i-2$ (just look to the first $i$ equations and subtract one from the next).

Step 2: Also, if we look to the equations $i+1$ to $n$, we have $$ \left\{\begin{array}{lll} \sum_{j=1}^llx_j+\sum_{j=l+1}^njx_j&=&0\quad(l>i). \end{array}\right. $$ This gives (subtracting $i$-th from $(i+1)$-th) $\sum_{j=1}^{i+1}x_j=0$, and $x_j=0$ for all $j=i+2,i+4,\cdots, n$ (subtracting one from next, and using the previous relation).

Combining both steps and looking to $Av=e_i$, we get (for $1<i<n$): $$ \left\{\begin{array}{cccll} x_{i-1}&+x_i&+x_{i+1}&=&0\\ (i-1)x_{i-1} &+ ix_i &+ (i+1)x_{i+1} &=& 0\\ ix_{i-1} &+ ix_i &+ (i+1)x_{i+1} &=& 1\\ (i+1)x_{i-1} &+ (i+1)x_i &+ (i+1)x_{i+1} &=& 0 \end{array}\right. $$ (and all other $x_j=0$, which gives $x_{i+1}=x_{i-1}=1,x_i=-2$). For $i=1$, we have only Step 2, and obtain: $$ \left\{\begin{array}{cll} x_{1}+x_2&=&0\\ x_1+2x_2&=&1 \end{array}\right. $$ and we obtain $x_1=-1$, $x_2=1$.

For $i=n$, we only have Step 1 and obtain: $$ \left\{\begin{array}{lll} (n-1)x_{n-1}+nx_n&=&0\\ nx_{n-1}+nx_n&=&1 \end{array}\right. $$ which gives $x_{n-1}=1$ and $x_n=-(n-1)/n$.

Hence, we obtain the inverse of $A$.