Proving a system of n linear equations has only one solution

Question

I have been given the system:

$-x_1 + 2x_2 + ... + 2x_{n-1} + 2x_n = 1$

$2x_1 - x_2 + ... 2x_{n-1} + 2x_n = 2$

$.$

$2x_1 + 2x_2 + ... + 2x_{n-1} - x_n = n$

And the assignment to prove that it has only one solution. I am aware of the existence of discriminants and their role of solving system of linear equations, although I have no idea on how to use that to prove this system has only one solution. (And I currently lack materials on infinite determinants and recurrent relations, any links would be appreciated).

Could anyone provide suggestions or hints on how to prove this system has exactly one solution?

score 4 · Accepted Answer · answered Mar 31 '13 at 18:38

4

Your equation is of the form $Ax = b$ where $$A = \begin{bmatrix}-1 & 2 & 2 & 2 & 2 & \cdots & 2 & 2\\ 2 & - 1 & 2 & 2 & 2 &\cdots & 2 & 2\\ 2 & 2 & -1 & 2 & 2 &\cdots & 2 & 2\\ 2 & 2 & 2 & -1 & 2 &\cdots & 2 & 2\\ 2 & 2 & 2 & 2 & -1 &\cdots & 2 & 2\\ \vdots & \vdots & \vdots & \vdots & \vdots &\ddots & \vdots & \vdots\\ 2 & 2 & 2 & 2 & 2 &\cdots & -1 & 2\\ 2 & 2 & 2 & 2 & 2 &\cdots & 2 & -1 \end{bmatrix}$$ We then have $$A = -3I_{n \times n} + 2 \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1\\ \vdots\\ 1\\ 1\end{bmatrix} \begin{bmatrix} 1& 1& 1& 1& 1& \cdots& 1& 1\end{bmatrix}$$ By Sherman-Morrison, we have $$A^{-1} = -\dfrac13 I_{n \times n}-\dfrac2{3(3-2n)}\begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1\\ \vdots\\ 1\\ 1\end{bmatrix}\begin{bmatrix} 1& 1& 1& 1& 1& \cdots& 1& 1\end{bmatrix}$$ Clearly, $A^{-1}$ exists for all $n$.

answered Mar 31 '13 at 18:38

3

For those like who did not know there was name for that: Sherman-Morrison formula. Nicely done, +1. – Julien Mar 31 '13 at 18:40
@julien There is a more general one named Woodbury formula. A very useful identity to know. – Mar 31 '13 at 18:41
Thanks, Marvis. As I see it, it is also a generalization of the neat: $I+AB$ is invertible if and only if $I+BA$ is invertible. – Julien Mar 31 '13 at 18:46
@julien Yes. I have used this identity quite a few times in my research and it is really helpful. :) – Mar 31 '13 at 18:48
May I ask what your area of research is? – Julien Mar 31 '13 at 23:02
@julien Fast algorithms/Numerical linear algebra. – Mar 31 '13 at 23:35
Interesting. For sure, you must know what a useful formula is! – Julien Mar 31 '13 at 23:36

André Nicolas · Answer 2 · 2013-03-31T19:43:45.217

2

Symmetrize! Add up all the equations. You will find an expression for $x_1+\cdots+x_n$.

Now it is easy to write down the solution.

Details: Let $s=x_1+\cdots+x_n$. Adding up the equations, we get $$(2n-3)s=1+2+\cdots+n=\frac{n(n+1)}{2}.$$

The $k$-th equation can be written as $2s-3x_k=k$. It follows that $$x_k=\frac{1}{3}\left(\frac{n(n+1)}{2n-3}-k\right).$$

edited Mar 31 '13 at 19:43

answered Mar 31 '13 at 18:25

André Nicolas

507,029

score 2 · Answer 3 · edited Apr 13 '17 at 12:20

2

The system can be written in matrix form $Ax=b$ where $A$ is the matrix $$ A=2J-3I $$ with J the matrix with all entries 1 and $I$ the identity matrix.

Show that the matrix $A$ is invertible (equivalently all eigenvalues of $A$ are non zero) therefore the system has the unique solution $A^{-1}b$.

This answer is relevant.

edited Apr 13 '17 at 12:20

Community

1

answered Mar 31 '13 at 18:33

P..

14,929

Math Gems · Answer 4 · 2013-03-31T20:41:36.087

There is a very nice way to see this using the algebra of circulant matrices. Define

$$\rm X = \left[\begin{array}{} 0 & 1 & 0 & 0 &\cdots& 0\\ 0 & 0 & 1 & 0 &\cdots& 0\\ 0 & 0 & 0 & 1 &\cdots& 0\\ & & & & \cdots &\\ 0 & 0 & 0 & 0 &\cdots& 1\\ 1 & 0 & 0 & 0 &\cdots& 0\end{array}\right]\ \Rightarrow\ X^2\! = \left[\begin{array}{} 0 & 0 & 1 & 0 &\cdots& 0\\ 0 & 0 & 0 & 1 &\cdots& 0\\ & & & & \cdots &\\ 0 & 0 & 0 & 0 &\cdots& 1\\ 1 & 0 & 0 & 0 &\cdots& 0\\ 0 & 1 & 0 & 0 &\cdots& 0\\\end{array}\right]\ \Rightarrow\ \cdots\ \Rightarrow\ X^n = 1$$

Your circulant matrix is $\rm\:M = f(X)\, =\, -1\!+\!2X\!+\!2X^2\!+\,\cdots\,+2X^{n-1}.\,$ One easily checks (see below) that $\rm\:f(x)\:$ is coprime to $\rm\:x^n-1,\:$ so by the Euclidean algorithm there is a Bezout identity

$$\rm a(x)\ f(x) + b(x)\ (x^n\!-1)\, =\ 1$$

Since $\rm\:X^n=1,\:$ evaluating above at $\rm\: x = X\:$ yields $\rm\:a(X)\,f(X)\, =\, 1,\:$ so $\rm\ M = f(X)\:$ is invertible.

For coprimality, let $\rm\:g = 1\!+\!x\!+\cdots+\!x^{n-1}.\:$ Then $\rm\:f = 2g\!-\!3\:$ is coprime to $\rm\:g\:$ since $\rm\:2g-f = 3,\:$ and $\rm\:f\:$ is coprime to $\rm\:x\!-\!1\:$ (else $\rm\:x\!-\!1\mid f\:\Rightarrow\:0=f(1) = 2n\!-\!3).\:$ Therefore, by Euclid's Lemma, we deduce that $\rm\:f\:$ coprime to both $\rm\:g\:$ and $\rm\,x\!-\!1\:\Rightarrow\:f\:$ coprime to their product $\rm\:(x\!-\!1)g = x^n\!-\!1.$

pritam · Answer 5 · 2013-03-31T18:40:56.520

Note that the system can be written as $(2J-3I)x=(1,2,\ldots ,n)^t$, where $x=(x_1,\ldots ,x_n)$, $J$ is the matrix with all entries $1$ and $I$ is the identity matrix. Now the eigen values of $J$ are $n$ with mutiplicity $1$ and $0$ with multiplicity $n-1$ (this follows from the fact that rank of $J$ is $1$, which is also the number of non-zero eigen values, and the sum of the eigen values is $n$). Hence the eigen values of $2J-3I$ are $2n-3$ with mutiplicity $1$ and $-3$ with multiplicity $n-1$, so all the eigen values are non-zero and hence the rank of $2J-3I$ is $n$. Therefore the system has a unique soloution.

Proving a system of n linear equations has only one solution

5 Answers5

Linked