Can we solve a system of linear equations with singular matrix?

Question

Given the system of equations $AX=B$ where $A$ is singular. Can one solve for $X$ in this case? Consider the following example for illustratrion

$A = \begin{pmatrix} 0 & a_3 & -a_2\\ -a_3 & 0 & a_1 \\ a_2 & -a_1 & 0 \end{pmatrix}$,

$X= \begin{pmatrix} x \\ y \\ z \end{pmatrix}$ and $B = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix} $.

Edit: There was a typo in $A$. How can one solve for $x,y,z$ in this case?

Answer 1

If a matrix is singular it means that its determinant is zero.
If a determinant is zero it means some row/col is a linear combination of other rows/cols.

So, not all vectors ${x,y,z}$ can be expressed as a combination of the vectors that each row/col of the matrix represents (The matrix is a tranformation between bases).

In general you can not solve the system.
But there are cases where the matrix is able to represent some group of vectors. Using a submatrix obtained by eliminating the linear combination, and that submatrix not being singular.
Suppose you eliminated the third column. Then, you can still obtain $x,y$, but $z$ coordinate will be undefined.

Answer 2

In general we cannot solve the system $Ax=b$ for a singular matrix $A$ and given $b$. In your example, take $a_1=a_2=a_3=0$. Then we cannot solve the system $Ax=b$, except for $b=0$.

Solutions of your example.

Case 1: $a_1=0$.

Case 1a: $a_2\neq 0$. Then we have $x=b_3/a_2$. Substitute this into the other equations.

Case 1b: $a_1=a_2=0$. We have no solution for $b_3\neq 0$.

Case 2: $a_1\neq 0$. Then $y=(b_3-a_2x)/a_1$. Subsitute this into the other equations.

Answer 3

Here the approach using the linear transformations could be useful, i.e. use matrices 3×3 and linear maps from $\mathbb{R}^3$ to $\mathbb{R}^3$ interchangebly :

For every noninvertible $A$ there is a vector $b$ s.t. $AX=b$ has no solutions

Indeed, $A$ has a rank less than 3 so it cannot be surjective onto $\mathbb{R}^3$ . Pick any $b$ outside the image of $A$ and we are done.

Answer 4

The solutions of $ A x = b $ (if they exist) will be of the form

$ x = \displaystyle x_0 + \sum_{i=1}^{k} c_i v_i $

where the ${v_i}$ form a basis of the null space of $A$. i.e. $A v_i = 0$ for $i = 1, 2, \dots , k $. ($k$ is the nullity of $A$).

And, $x_0$ is any solution of $A x = b$, to find it, reduce the augmented matrix $[A | b ]$ to Reduced-Row Echelon Form. If there is a row that is all zeroes except a non-zero entry at the end, then the system is inconsistent, and there is no solution. Otherwise, the system is consistent, and $x_0$ can be determined by solving the reduced system with the arbitrary variables all set to $0$. Determine the leading $1$'s in the reduced matrix. The columns with no leading $1$'s correspond to the arbitrary variables. Set these arbitrary variables to $0$, and solve the reduced system.

For example, suppose you have the following system

$ A x = b $

where

$ A = \begin{bmatrix} 1 && -2 && 5 \\ 4 && 3 && -2 \\ -1 && 1 && -3 \end{bmatrix},\hspace{20pt} b = \begin{bmatrix} -1 \\ 18 \\ -1 \end{bmatrix} $

Here, $A$ is singular, so to solve the system, form the augmented matrix, and reduce,

$ \begin{bmatrix} 1 && -2 && 5 && - 1 \\ 4 && 3 && -2 && 18 \\ -1 && 1 && -3 && -1 \end{bmatrix} $

After the first iteration, we get

$ \begin{bmatrix} 1 && -2 && 5 && -1 \\ 0 && 11 && - 22 && 22 \\ 0 && -1 && 2 && -2 \end{bmatrix} $

Switching rows $(2)$ and $(3)$ gives

$ \begin{bmatrix} 1 && -2 && 5 && -1 \\ 0 && -1 && 2 && -2 \\ 0 && 11 && - 22 && 22 \end{bmatrix} $

Eliminating the entries in the second column, we obtain,

$ \begin{bmatrix} 1 && 0 && 1 && 3 \\ 0 && 1 && -2 && 2 \\ 0 && 0 && 0 && 0 \end{bmatrix} $

This is the reduced-row echelon form of the augmented matrix. As can be seen, the system is consistent. The column with no leading $1$ is the third column. So we set $z=0$ and solve the remaining system.

We immediately get $ x = 3 $ , $ y = 2 $. Hence,

$ x_0 = \begin{bmatrix} 3 \\ 2 \\ 0 \end{bmatrix} $

Now, since we have one arbitrary variable, which is $z$, we want to find the corresponding $v$, by setting the last column to zero and solving

$ \begin{bmatrix} 1 && 0 && 1 && 0 \\ 0 && 1 && -2 && 0 \\ 0 && 0 && 0 && 0 \end{bmatrix} $

If we set $z = t$, where $ t \in \mathbb{R} $, then from the first and second rows, we get

$ x = -t $

$ y = 2 t $

Hence the solution of the homogenized system is

$ v_1 = \begin{bmatrix} -1 \\ 2 \\ 1 \end{bmatrix} $

And therefore, the solution to our system is

$ x = x_0 + t v_1 = \begin{bmatrix} 3 \\ 2 \\ 0 \end{bmatrix} + t \begin{bmatrix} -1 \\ 2 \\ 1 \end{bmatrix} $

As another example, I'll take your system mentioned in the question.

$ A = \begin{bmatrix} 0 && a_3 && - a_2 \\ -a_3 && 0 && a_1 \\ a_2 && - a_1 && 0 \end{bmatrix} \hspace{20pt} b = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} $

Again $A$ is singular, so we first form the augmented matrix

$ \begin{bmatrix} 0 && a_3 && - a_2 && b_1 \\ -a_3 && 0 && a_1 && b_2 \\ a_2 && - a_1 && 0 && b_3 \end{bmatrix} $

For simplicity assume $a_1 \ne 0 , a_2 \ne 0 , a_3 \ne 0 $, then divide the second and third rows by $(-a_3)$, and $a_2$, you get

$ \begin{bmatrix} 0 && a_3 && - a_2 && b_1 \\ 1 && 0 && -\dfrac{a_1}{a_3} && -\dfrac{b_2}{a_3} \\ 1 && - \dfrac{a_1}{a_2} && 0 && \dfrac{b_3}{a_2} \end{bmatrix} $

Switch the first and second rows:

$ \begin{bmatrix} 1 && 0 && -\dfrac{a_1}{a_3} && -\dfrac{b_2}{a_3} \\ 0 && a_3 && - a_2 && b_1 \\ 1 && - \dfrac{a_1}{a_2} && 0 && \dfrac{b_3}{a_2} \end{bmatrix} $

Eliminate the leading $1$ in the third row, and divide the second row by $ a_3 $, this leads to,

$ \begin{bmatrix} 1 && 0 && -\dfrac{a_1}{a_3} && -\dfrac{b_2}{a_3} \\ 0 && 1 && - \dfrac{a_2}{a_3} && \dfrac{b_1}{a_3} \\ 0 && - \dfrac{a_1}{a_2} && \dfrac{a_1}{a_3} && \dfrac{b_3}{a_2} + \dfrac{b_2}{a_3} \end{bmatrix} $

Eliminate the leading entry in the third row, this gives us,

$ \begin{bmatrix} 1 && 0 && -\dfrac{a_1}{a_3} && -\dfrac{b_2}{a_3} \\ 0 && 1 && - \dfrac{a_2}{a_3} && \dfrac{b_1}{a_3} \\ 0 && 0 && 0 && \dfrac{a_1 b_1}{a_2 a_3} + \dfrac{b_3}{a_2} + \dfrac{b_2}{a_3} \end{bmatrix} $

And we're done.

For this system to have a solution, we must have

$ \dfrac{a_1 b_1}{a_2 a_3} + \dfrac{b_3}{a_2} + \dfrac{b_2}{a_3} = 0 $

The left hand side of this equation is just

$ \dfrac{ a_1 b_1 + b_2 a_2 + b_3 a_3 }{a_2 a_3 } $

And this will be zero if and only if $(a_1, a_2, a_3)$ is orthogonal to $(b_1, b_2, b_3) $

Assuming this to be the case, then we now have

$ \begin{bmatrix} 1 && 0 && -\dfrac{a_1}{a_3} && -\dfrac{b_2}{a_3} \\ 0 && 1 && - \dfrac{a_2}{a_3} && \dfrac{b_1}{a_3} \end{bmatrix} $

By setting the third variable to zero, we get as a particular solution

$ x_0 = \begin{bmatrix} -\dfrac{b_2}{a_3} \\ \dfrac{b_1}{a_3} \\ 0 \end{bmatrix} $

Now to find $v_1$ the solution to the homogenized system, take the last column to be zero, and solve, you get

$ v_1 = \begin{bmatrix} \dfrac{a_1}{a_3} \\ \dfrac{a_2}{a_3} \\ 1 \end{bmatrix} $

Since $t$ is arbitrary, we can simplify things, by multiplying this vector by $a_3$, and take

$v_1 = \begin{bmatrix} a_1 \\ a_2 \\ a_3 \end{bmatrix} $

Hence, the general solution is

$ x = x_0 + t v_1 = \begin{bmatrix} -\dfrac{b_2}{a_3} \\ \dfrac{b_1}{a_3} \\ 0 \end{bmatrix} + t \begin{bmatrix} a_1 \\ a_2 \\ a_3 \end{bmatrix} $

To verify this is indeed a valid solution, remember,

$ A = \begin{bmatrix} 0 && a_3 && - a_2 \\ -a_3 && 0 && a_1 \\ a_2 && - a_1 && 0 \end{bmatrix} \hspace{20pt} b = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} $

Caclulate $Ax$:

$A x = \begin{bmatrix} 0 && a_3 && - a_2 \\ -a_3 && 0 && a_1 \\ a_2 && - a_1 && 0 \end{bmatrix} \left( \begin{bmatrix} -\dfrac{b_2}{a_3} \\ \dfrac{b_1}{a_3} \\ 0 \end{bmatrix} + t \begin{bmatrix} a_1 \\ a_2 \\ a_3 \end{bmatrix} \right) = \begin{bmatrix} b_1 \\ b_2 \\ \dfrac{-a_2 b_2 -a_1 b_1}{a_3} \end{bmatrix}$

Since we've assumed that $ a_1 b_1 + a_2 b_2 + a_3 b_3 = 0 $ then the above simplifies to

$ A x = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} = b $

Answer 5

Too long for a comment:

Notice that in our particular case, $$A X = X \times {\bf a}, \qquad \textrm{where} \qquad {\bf a} := \pmatrix{a_1\\a_2\\a_3} .$$ So, if $X$ satisfes $A X = B$, that is, if $X \times {\bf a} = B$, then $B$ is orthogonal to both $X$ and ${\bf a}$. Thus:

• If ${\bf a} \cdot B \neq 0$, then there is no solution $X$.
• If ${\bf a} \neq {\bf 0}$, then $\operatorname{rank} A = 2$, so $A X = B$ has a solution if and only if ${\bf a} \cdot B = 0$. In that case, since $A {\bf a} = {\bf 0}$, we have $\ker A = \operatorname{span}\{{\bf a}\}$, hence the solution space is $\{X_0 + \lambda {\bf a} : \lambda \in \Bbb F\}$.
• If ${\bf a} = {\bf 0}$, then the equation becomes $B = {\bf 0}$, which has solution space $\Bbb F^3$ if $B = {\bf 0}$ and no solutions otherwise.