Matrix Equation

Nonhomogeneous matrix equations of the form

$${\hbox{\sf A}}{\bf x}={\bf b}$$ (1)

can be solved by taking the Matrix Inverse to obtain

$${\bf x}={\hbox{\sf A}}^{-1}{\bf b}.$$ (2)

This equation will have a nontrivial solution Iff the Determinant $\mathop{\rm det}({\hbox{\sf A}})\not=0$. In general, more numerically stable techniques of solving the equation include Gaussian Elimination, LU Decomposition, or the Square Root Method.

For a homogeneous $n\times n$ Matrix equation

$$\left[{\matrix{ a_{11} & a_{12} & \cdots & a_{1n}\cr a_{21... ...\cr}}\right] =\left[{\matrix{0\cr 0\cr \vdots\cr 0\cr}}\right]$$ (3)

to be solved for the $x_i$s, consider the Determinant

$$\left\vert\matrix{ a_{11} & a_{12} & \cdots & a_{1n}\cr a_... ...& \vdots\cr a_{n1} & a_{n2} & \cdots & a_{nn}\cr}\right\vert.$$ (4)

Now multiply by $x_1$, which is equivalent to multiplying the first column (or any column) by $x_1$,

$$x_1\left\vert\matrix{ a_{11} & a_{12} & \cdots & a_{1n}\cr ... ...vdots\cr a_{n1}x_1 & a_{n2} & \cdots & a_{nn}\cr}\right\vert.$$ (5)

The value of the Determinant is unchanged if multiples of columns are added to other columns. So add $x_2$ times column 2, ..., and $x_n$ times column $n$ to the first column to obtain

$$x_1\left\vert\matrix{ a_{11} & a_{12} & \cdots & a_{1n}\cr a... ..._2+\ldots+a_{nn}x_n & a_{n2} & \cdots & a_{nn}\cr}\right\vert.$$ (6)

But from the original Matrix, each of the entries in the first columns is zero since

$$a_{i1}x_1+a_{i2}x_2+\ldots+a_{in}x_n=0,$$ (7)

so

$$\left\vert\matrix{ 0 & a_{12} & \cdots & a_{1n}\cr 0 & a_{... ... & \vdots\cr 0 & a_{n2} & \cdots & a_{nn}\cr}\right\vert = 0.$$ (8)

Therefore, if there is an $x_1\not = 0$ which is a solution, the Determinant is zero. This is also true for $x_2$, ..., $x_n$, so the original homogeneous system has a nontrivial solution for all $x_i$s only if the Determinant is 0. This approach is the basis for Cramer's Rule.

Given a numerical solution to a matrix equation, the solution can be iteratively improved using the following technique. Assume that the numerically obtained solution to

$${\hbox{\sf A}}{\bf x}={\bf b}$$ (9)

is ${\bf x}_1={\bf x}+\delta{\bf x}_1$, where $\delta {\bf x}_1$ is an error term. The first solution therefore gives

$${\hbox{\sf A}}{\bf x}_1={\hbox{\sf A}}({\bf x}+\delta{\bf x}_1) = {\bf b}+\delta{\bf b}$$ (10)

$${\hbox{\sf A}}\delta{\bf x}_1=\delta {\bf b},$$ (11)

where $\delta{\bf b}$ is found by solving (10)

$$\delta{\bf b} = {\hbox{\sf A}}{\bf x}_1-{\bf b}.$$ (12)

Combining (11) and (12) then gives

$$\delta {\bf x}_1={\hbox{\sf A}}^{-1}\delta{\bf b}={\hbox{\sf... ... A}}{\bf x}_1-{\bf b}) = {\bf x}_1-{\hbox{\sf A}}^{-1}{\bf b}.$$ (13)

See also Cramer's Rule, Gaussian Elimination, LU Decomposition, Matrix, Matrix Addition, Matrix Inverse, Matrix Multiplication, Normal Equation, Square Root Method