## 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 0 a0
 0 1 < td> 0 0 0 1 < td> 0 0 0 < td> 1 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 0 M0
 0 I < td> 0 0 0 I < td> 0 0 0 < td> I M1 M2 M3
Furthermore, the eigenvectors associated with each eigenvalue specify the values of the eliminated variables.