A simple $n\times n$ system of linear equations

Question

Can anyone provide the analytical solution of the following $n\times n$ system of linear equations

$\underbrace{\begin{pmatrix} a & -b & -b & ... & -b\\ -b & a & -b & ... & -b\\ -b & -b & a & ... & -b\\ : & : & : & ... & : \\ : & : & : & ... &: & \\ -b & -b & -b & ... & a \\ \end{pmatrix}}_{A}\underbrace{\begin{pmatrix}x_1\\ x_2\\ x_3\\ :\\ :\\ x_n \end{pmatrix}}_{X}=\underbrace{\begin{pmatrix}y_1\\ y_2\\ y_3\\ :\\ :\\ y_n \end{pmatrix}}_{Y} $ where $A_{(n\times n)}$ is a symmetric matrix and $a$, $b$, $y_i$ are positive real numbers.

Note: I would appreciate if someone could provide more details about the theory of eigenvalues-eigenvectors related to the solutuion of a linear system of eaquations.

Answer 1

You can write your equations as $$ \left((a+b)I-b\mathbb{1}\mathbb{1}^T\right)x=y\ ,$$ where $\ \mathbb{1}\ $ is the column vector whose entries are all $1$. Multiplying this equation on the left by the row vector $\ \mathbb{1}^T\ $ gives \begin{align} (a+b)\mathbb{1}^Tx-b\mathbb{1}^T\mathbb{1}\mathbb{1}^Tx&=\mathbb{1}^Ty\\ &=\big(a-(n-1)b\big)\mathbb{1}^Tx\ ,\\ \hspace{-18em}\text{or}\\ \mathbb{1}^Tx&=\big(a-(n-1)b\big)^{-1}\mathbb{1}^Ty\ , \end{align} provided $\ a-(n-1)b\ne0\ $. Now rewriting the first equation above as $$ (a+b)x=y+b\mathbb{1}\mathbb{1}^Tx\ , $$ and substituting $\ \big(a-(n-1)b\big)^{-1}\mathbb{1}^Ty\ $ for $\ \mathbb{1}^Tx\ $ gives \begin{align} x&=\left(\frac{1}{a+b}\right)y+\left(\frac{b}{(a+b)\big(a-(n-1)b\big)}\right)\mathbb{1}\mathbb{1}^Ty\\ &=\left(\left(\frac{1}{a+b}\right)I+\left(\frac{b}{(a+b)\big(a-(n-1)b\big)}\right)\mathbb{1}\mathbb{1}^T\right)y\ , \end{align} provided $\ (a+b)\ne0\ $, which gives you the solution to your problem.

Answer 2

Hint

Use linear combinations in the main matrix:

• Take every line (except the first) minus the first:

$$\begin{pmatrix} a & -b & -b & ... & -b\\ -(a+b) & a+b & 0 & ... & 0\\ -(a+b) & 0 & a+b & ... & 0\\ : & : & : & ... & : \\ : & : & : & ... &: & \\ -(a+b) & 0 & 0 & ... & a+b \\ \end{pmatrix} $$

• Now sum at the first column, the sum of the other columns:

$$\begin{pmatrix} a-(n-1)b & -b & -b & ... & -b\\ 0 & a+b & 0 & ... & 0\\ 0 & 0 & a+b & ... & 0\\ : & : & : & ... & : \\ : & : & : & ... &: & \\ 0 & 0 & 0 & ... & a+b \\ \end{pmatrix} $$

Can you finish?

Answer 3

The matrix is of type: linear combination of the identity and a rank $1$ matrix, the latter being the matrix all of whose entries are $-b$, call it $B$. Then $B$ is easily diagonalisable, with an $n-1$ dimensional kernel (eigenspace for $0$) given by the equation $x_1+\dots+x_n=0$, and a $1$ dimensional other eigenspace, spanned by $(1,1,\ldots,1)$, whose eigenvalue for $B$ equals $-nb$. We have $A=B+(a+b)I_n$; the eigenspaces of $B$ are also eigenspaces for $A$, but with eigenvalues $\lambda=a+b$ respectively $\mu=-nb+a+b=a+(1-n)b$.

The linear problem is easy to solve on each eigenspace: on the $n-1$ dimensional eigenspace $A$ acts by multiplication by $\lambda$ and, provided $\lambda\neq0$, the solution will be $X=\frac1\lambda Y$, while on the $1$-dimensional eigenspace $A$ acts by multiplication by $\lambda$ and, provided $\mu\neq0$, the solution will be $X=\frac1\mu Y$. For the general solution one can decompose $Y$ into its projections $Y_1$ and $Y_2$ on the two eigenspaces, and provided both $\lambda=a+b$ and $\mu=a+(1-n)b$ are nonzero one can find the solution by adding the solutions associated to $Y_1$ and $Y_2$. One has $Y_2=\frac{(y_1+\cdots+y_n)}n(1,1,\ldots,1)$ and $Y_1=Y-Y_2$; the general solution then is $X=\frac1\lambda Y_1+\frac1\mu Y_2$. Working this out explicitly is a bit messy, but straightforward.

Here is a concrete example if you find this too abstract. Take $n=5$, $a=2$ and $b=1$. Then neither $\lambda=a+b=3$ nor $\mu=a+(1-n)b=-2$ is zero, so the problem is solvable for all $Y$. Take for instance $Y=(3,-1,2,5,-4)$, it decomposes as the sum of a multiple $Y_2$ of $(1,1,1,1,1)$ by the scalar $\frac{3-1+2+5-4}5=1$, and a vector $Y_1=Y-Y_2=(2,-2,1,4,-5)$ whose sum of coordinates is $0$. The solution for $X$ then is $\frac1\lambda Y_1+\frac1\mu Y_2=\frac13(2,-2,1,4,-5)-\frac12(1,1,1,1,1)=\frac16(1,-7,-1,5,-13)$.