# Solve a linear equation with no unique solution

I want to calculate a unique equation for the following linear equation. The background is the page rank algorithm where I want to find a vector solution for the Google matrix:

The matrix on which I've started is: $$\left(\begin{array}{rrrr} 1&13&1&1\\ 1&1&7&7\\ 13&1&1&1\\ 1&1&13&1\end{array}\right).$$

Which is multiplied by $1/16$ in the end, but I leave this out, since its easier to do calculations on the matrix without this scalar. So yes, I am looking for the left eigenvector with eigenvalue 1, however I want to find a matching solution with linear equation. I used the Gauss algorithm on the matrix and came to the following solution:

$a = a/16$

$b = b/16 - a/16$

$c = c/16 + a/16 - 14b/16$

$d = 17a/16/16 - 15b/8/16 + c/16/16 + d/16$

(This equation is derived from a matrix by using the Gauss algorithm)

For me it is obivous, that there is no unique solution to this equation. I was, hoever, told, that there is one, when adding the following constraints:

$a + b + c + d = 1$ and $a,b,c,d \geq 0$

This what I actually want, but I don't see how this could help. Any hints or suggestions?

-
$b = b - a$ tells us $a = 0$, then we have $c = c - 14b$ which tells us $b = 0$, then we have $d = \frac{c}{16} + d$ which tells us $c = 0$ then we have $d = 1$, so we get $a = b = c = 0$, $d = 1$. – Deven Ware Jan 12 '12 at 23:13
@DevenWare Sorry, I forgot that every value has to be multiplied with $1/16$ although I am not sure if this changes anything. – Erandir Jan 12 '12 at 23:14
A matrix usually does have four eigenvectors (even if, like here, there is only one eigenvalue, $1$). The matrix corresponding to your system is defective, however, and there is thus only one set of $a,b,c,d$ values (only one eigenvector) that satisfy your equations. – J. M. Jan 12 '12 at 23:17
Could you edit to explicitly show which values should be multiplied by $\frac1{16}$? Yes, it might change... – J. M. Jan 12 '12 at 23:18
You changed the equations, which changes the answer, but I suspect these equations are still not what you want. – Henry Jan 12 '12 at 23:25

First version of the problem: Your first equation $a=a$ is tautological and so gives no information. So you are left with three equations and four variables, so you should not expect a unique solution. Add another equation and you may have the possibility of a unique solution which may satisfy your constraints; though you might have many solutions which satisfy your constraints, solution(s) which do not satisfy your constraints, or no solutions at all.
Your second equation implies $a=0$, which combined with your third equation implies $b=0$, which combined with your fourth equation implies $c=0$, but $d$ can take any value. Combining this with $a + b + c + d = 1$ implies $d=1$ and the solution $(0,0,0,1)$ satisfies your constraints so you are done.
Second version of the problem: Your first equation implies $a=0$, which combined with your second equation implies $b=0$, which combined with your third equation implies $c=0$, which combined with your fourth equation implies $d=0$. So the unique solution is $(0,0,0,0)$. If you then combine this with $a + b + c + d = 1$ then you have no solution.
Third version of the problem: I think your matrix form results in $a=b=c=d$ so there is not a unique solution. Combining this with $a + b + c + d = 1$ implies the unique solution $(0.25,0.25,0.25,0.25)$, which satisfies your constraints so you are done.