Eigendecomposition Techniques
MARS also relies on eigendecomposition and companion block matrices to
numerically solve the following matrix polynomial: Det(M(x))=0.
Companion matrices reduce the problem of solving polynomial
expressions to eigendecompoisition. A companion matrix has 1's above
the diagnoal and coefficients from a polynomial on the last row;
thereby, the eigenvalues of the matrix exactly correspond to the roots
of the polynomial:
x^4 + a3 x^3 + a2 x^2 + a1 x + a0
corresponds to:
| 0 | 1 < td> 0 | 0 |
0 | 0 | 1 < td> 0 |
0 | 0 | 0 < td> 1 |
a0 | a1 | a2 | a3
|
It turns out that one can also solve for roots of matrix polynomial
expressions via eigendecomposition as well. In this case, we must
multiply all of the terms by the inverse of the highest order so that
the highest order term is an identity matrix:
x^4 + M3 x^3 + M2 x^2 + M1 x + M0
corresponds to:
| 0 | I < td> 0 | 0 |
0 | 0 | I < td> 0 |
0 | 0 | 0 < td> I |
M0 | M1 | M2 | M3
|
Furthermore, the eigenvectors associated with each eigenvalue specify
the values of the eliminated variables.