Find the inverse of the $n\times n$ matrix whose entries are given by $a_{ij} = \max (i,j)$ 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.
 A: 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}.
$$
A: 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$.
