Linear Simultaneous Equations

The general form of a set of linear simulatenous equations:

$$\begin{array}{r}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n=b_2\\ a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n=b_m\end{array}$$

This can be rewritten in a matrix/vector form:

$$Ax=b$$

$$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{1n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}\right]b=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right]x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$$

Equations of this form have three cases for their solutions:

• The system has no solution
• The system has a unique solution
• The system has an infinite number of solutions
  • $x$ can take a number of values

An over-determined system has more equations than unknowns and has no solution:

$$\left[\begin{array}{cc}1& 1\\ -1& 2\\ -2& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\left[\begin{array}{c}2\\ 1\\ 2\end{array}\right]$$

An under-determined system has more unknowns than equations and has infinite solutions:

$$\left[\begin{array}{cc}1& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\left[\begin{array}{c}2\end{array}\right]$$

A consistent system has a unique solution

$$\left[\begin{array}{cc}1& 1\\ -1& 2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\left[\begin{array}{c}2\\ 1\end{array}\right]$$

The solution for this system is $\left[\begin{array}{c}1\\ 1\end{array}\right]$. Note that the rank and order of $A$ are both 2, and $A^{-1}$ exists in this case. If the determinant of a consistent system is 0, there will be no solutions.

Solutions of Equations

To determine which of the three cases a system is:

• Introduce the augmented matrix: $\tilde{A}=\left[A|b\right]$
• Calculate the rank of $A$ and $\tilde{A}$

No Solution

• If $\mathrm{rank}(A)\ne \mathrm{rank}(\tilde{A})$, then the system has no solution
• All vectors $x$ will result in an error vector
• A particular error vector will minimise the norm of the equation error
  • The least square error solution, $x^{\ast }$

$$||ϵ|{|}^2=||Ax-b|{|}^2=(Ax-b{)}^{\prime }(Ax-b)$$

$$x^{\ast }=A_L^{+}b=(A^{\prime }A{)}^{-1}{A}^{\prime }b$$

Unique Solution

$\mathrm{rank}(A)=\mathrm{rank}(\tilde{A})=n$ where $n$ is the number of variables in $x$

• $\det (A)\ne 0$.

$$x=A^{-1}b$$

Infinite Solutions

• $\mathrm{rank}(A)=\mathrm{rank}(\tilde{A})=k<n$
• Paramaeters can be assigned to any $n-k$ elements of the vector $x$ and the remaining $k$ elements can be computed in terms of these parameters
• A particular vector $x^{\ast }$ will again minimise the square of the norm of the solution vector

$$x^{\ast }=A_R^{+}b=A^{\prime }(A{A}^{\prime }{)}^{-1}b$$

Homogenous Systems

A system of homogenous equations take the form:

$$Ax=o_{n}b=o_n=\left[\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right]$$

• $A$ is an $n$x$n$ matrix of known coefficients
• $b$ is an $n$x$1$ null column vector
• $x$ is an $n$x$1$ vector of unknowns

The augmented matrix $\mathrm{rank}(\tilde{A})=\left[A|o_n\right]$ and $\mathrm{rank}(A)=\mathrm{rank}(\tilde{A})$, so there is at least one solution vector $x=o_n$. There are two possible cases for other solutions:

• $\mathrm{rank}(A)=n$ and $\det (A)\ne 0$, then the trivial solution is the only unique solution
• If $\mathrm{rank}(A)<n$ and $\det (A)=0$, then there is an infinite number of non-trivial solutions $x\ne o_n$
  • This includes the trivial solution $x=o_n$

Example 1

Solutions to:

$$\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 0\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}6\\ 15\\ 15\end{array}\right]$$

$$\tilde{A}=\left[\begin{array}{cccc}1& 2& 3& 6\\ 4& 5& 6& 15\\ 7& 8& 0& 15\end{array}\right]$$

First calculate the determinant of $A$:

$$\left|\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 0\end{array}\right|=\left|\begin{array}{cc}5& 6\\ 8& 0\end{array}\right|-2\left|\begin{array}{cc}4& 6\\ 7& 0\end{array}\right|+3\left|\begin{array}{cc}5& 5\\ 7& 8\end{array}\right|=27$$

$\det (A)=3$ so $A$ is a full rank matrix (rank = order = 3). We know solutions exist, but need to find the rank of $\tilde{A}$ to check if unique or infinite solutions. Using gaussian elimination to put $\tilde{A}$ into row-echelon form:

$$\left[\begin{array}{cccc}1& 2& 3& 6\\ 0& -2& -6& -9\\ 0& 0& -9& -9\end{array}\right]$$

The rank of $\mathrm{rank}(A)=\mathrm{rank}(\tilde{A})=3$, so there is a unique solution $x=A^{-1}b$

$$A^{-1}=\frac{1}{27}\left[\begin{array}{ccc}-48& -24& -3\\ 42& -21& 6\\ 3& 6& -3\end{array}\right]$$

$$x=\frac{1}{27}\left[\begin{array}{ccc}-48& -24& -3\\ 42& -21& 6\\ 3& 6& -3\end{array}\right]\left[\begin{array}{c}6\\ 15\\ 15\end{array}\right]=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$$

Example 2

Solutions to:

$$\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$

There is the trivial solution $x=o_n$, but we need to known if there is infinite solutions, which we can determine from $\mathrm{rank}(A)$. Putting it into row-echelon form:

$$\left[\begin{array}{ccc}1& 2& 3\\ 0& -3& -6\\ 0& 0& 0\end{array}\right]$$

$\mathrm{rank}(A)=2<n$, so there is infinite solutions. Can introduce a parameter $\alpha$ to express solutions in terms of. Using the coefficients from the row-echelon form:

$$\begin{gathered} x_1+2x_2+3x_3=0 \\ -3x_2-6x_3=0 \end{gathered}$$

$$\begin{gathered} x_1=x_3=\alpha \\ {x}_2=-2x_3=-2\alpha \end{gathered}$$

$$x=\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$$

$$x=\left[\begin{array}{c}\alpha \\ -2\alpha \\ \alpha \end{array}\right]$$