Abstract
Matrix inversion methods are used to solve relatively simple simultaneous equations under very stringent requirements. One of these requirements is that there be a solution. If the matrix is singular or not square, it must be solved with other methods that are more computationally expensive or complicated. These methods typically give least-squares solutions. The primary one of these methods is that of Mr. Moore and Mr. Penrose. The Moore-Penrose solution also has its limitations. The method presented here provides a solution to the matrix problem without undue complexity, works on singular and non-square matrices, and produces a stable result, and can be used by itself or in combination with the Moore-Penrose method.
Try this with your own matrix problem using some JavaScript on the demonstration page.
When simple matrix inversion fails
The original equations
To demonstrate the shortcomings of the simplest methods for solving a system of linear equations we begin by creating equations that we know will fail. Consider this very simple system of equations:
| x | +y | = | b1 | |
| -y | +z | = | b2 | |
| x | +z | = | b3 |
The third equation is obviously a combination of the first two, but will demonstrate the problem. This is the simplest set of equations I could think of on short notice that demonstrates the problem. In matrix notation this is:
Where the matrix A is:
| 1 | 1 | 0 |
| 0 | -1 | 1 |
| 1 | 0 | 1 |
The vector x is:
| x |
| y |
| z |
And the vector b is:
| b1 |
| b2 |
| b3 |
In this case, of course, b3 = b1 + b2.
First attempt to invert the original matrix
Begin the matrix inversion by augmenting the matrix with an identity of the same apparent rank:
| 1 | 1 | 0 |
| 0 | -1 | 1 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Subtract row 1 from row 3.
| 1 | 1 | 0 |
| 0 | -1 | 1 |
| 0 | -1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| -1 | 0 | 1 |
Subtract row 2 from row 3.
| 1 | 1 | 0 |
| 0 | -1 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| -1 | -1 | 1 |
Row 3 of the reduced matrix is now identically 0.
This is completely expected because we chose a singular matrix where row 3
was a combination of the other two rows.
Attempt to use the Moore-Penrose method
The Moore-Penrose method in its simplest form involves multiplying the transpose of the A matrix
times both sides of the original matrix equation and solving the resulting equation. The original equation is
Ax = b,
and the new problem is:
We now invert the (ATA) matrix and then multiply this inverse times the
transpose of the original matrix
(AT)
and then multiply that into the b
vector to solve for x.
which (if the (ATA) inverse exists) reduces to
To begin with we invert the (ATA) matrix
using the same method shown above.
The AT matrix is:
| 1 | 0 | 1 |
| 1 | -1 | 0 |
| 0 | 1 | 1 |
And the product of the transform times the original matrix is:
| 1 | 0 | 1 |
| 1 | -1 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
| 0 | -1 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 1 | 2 | -1 |
| 1 | -1 | 2 |
Attempt to solve the problem with Moore-Penrose
Augment the matrix with identity as before.
| 2 | 1 | 1 |
| 1 | 2 | -1 |
| 1 | -1 | 2 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Subtract row 2 from row 1.
| 1 | -1 | 2 |
| 1 | 2 | -1 |
| 1 | -1 | 2 |
| 1 | -1 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Subtract row 1 from row 3.
| 1 | -1 | 2 |
| 1 | 2 | -1 |
| 0 | 0 | 0 |
| 1 | -1 | 0 |
| 0 | 1 | 0 |
| -1 | 1 | 1 |
Like the first attempt above, this one fails.
Results and next direction
There may be variants of the Moore-Penrose method that will work (and certainly, SVD will work for this problem),
but we can develop a method that works unconditionally
beginning on the next page.
This development starts with the astounding observation that
AT-1 = A-1T
for invertible matrices (square, non-singular).
To try this, see the JavaScript implementation on this page.