0
$\begingroup$

Let $A$ be a matrix, and let $E$ be the elementary matrix corresponding to a row operation.

Since $A$ and $EAE^{-1}$ are related by a similarity transformation, their characteristic polynomials are the same.

$EAE^{-1}$ is the matrix obtained by first performing the row operation on $A$ then performing the inverse operation on the columns of the matrix just obtained. For example, if multiplying by $E$ on the left corresponds to performing the row operation R2 = R2 + aR1, then multiplying by $E^{-1}$ on the right corresponds to performing the column operation C2 = C2 - aC1.

If one can perform a sequence of pairs of operations of the form \begin{align*} \text{row operation} \qquad \text{then} \qquad \text{inverse of same row operation on columns} \end{align*} to reduce $A$ to an upper triangular form, then the eigenvalues of $A$ can just be read off the diagonal of the reduced matrix.

Is there a systematic (i.e., algorithmic) way to perform such a reduction (similar to Gaussian elimination)?

$\endgroup$
  • $\begingroup$ Interesting question, but is Gaussian elimination not your answer? It is rather simple to find inverse of an elementary matrix, so why not just apply your reduction until you are in row-echelon form? Regardless, it might be better to consider the effect of each transformation on the determinant of your original matrix $A$? Just a thought. $\endgroup$ – Rellek Apr 10 '15 at 19:45
  • $\begingroup$ Suppose I start with $A$. Then I perform rows ops to get to a row echelon form R. This means $R = E_k \cdots E_1 A$ where $E_i$ is the elementary matrix corresponding to the i-th row op I performed. Now the characteristic polynomial of $A$ and $R$ will not be the same (generically). Further perform the inverses of the used rows ops to the columns of $R$. This means multiply $R = E_k \cdots E_1 A$ on the right by $E_{1}^{-1} \cdots E_{k}^{-1} = (E_k \cdots E_1)^{-1}$. In the end, you get the matrix $E_k \cdots E_1 A E_{1}^{-1} \cdots E_{k}^{-1}$. $\endgroup$ – LucasSilva Apr 10 '15 at 20:21
  • $\begingroup$ The matrix $E_k \cdots E_1 A E^{-1}_{1} \cdots E^{-1}_{k}$ has the same characteristic polynomial as $A$. But is it in triangular form? We know $R = E_k \cdots E_1 A$ was triangular, but do we know $E_k \cdots E_1 A E^{-1}_{1} \cdots E^{-1}_{k}$ is? $\endgroup$ – LucasSilva Apr 10 '15 at 20:23
  • $\begingroup$ The relevant thing is not how $\text{det} A$ is related to $\text{det} EAE^{-1}$, but how $\text{det} (A-\lambda I)$ is related to $\text{det} (EAE^{-1} - \lambda I)$ (spoiler: they are equal). $\endgroup$ – LucasSilva Apr 10 '15 at 20:31
  • $\begingroup$ Of course they are equal. Some clarification, are you writing a program for this? Or do you just want to know if an algorithmic way to do this exists? $\endgroup$ – Rellek Apr 10 '15 at 20:52
1
$\begingroup$

The answer is "yes" or "no", depending on what you ask precisely. The answer is "yes" in the sense that there always exists (at least over$~\Bbb C$) a sequence of two-sided elementary operations that reduce $A$ to an upper triangular matrix. After all, $A$ is certainly triangularisable, which means there exist invertible $P$ (not unique) such that $PAP^{-1}$ is upper triangular, and it suffices to express $P$ as a product of elementary matrices.

But on the other hand if you are asking for an algorithmic method similar to Gaussian elimination, and I interpret that as using only rational operations on the coefficients, then the answer is certainly "no". After all, even a matrix with integer coefficients may require complex coefficients in the conjugating matrix $P$ to be triangularised, and you certainly won't get those from rational operations. Indeed even if you would allow extracting radicals, the Abel-Ruffini theorem says this cannot be possible for $n>4$, since every polynomial can be realised as a characteristic polynomial (of its companion matrix) and such a method would give you a means to construct its roots.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Twenty minutes ago I came to the same realization after reading Lecture 25 in Numerical Linear Algebra by Trefethen and Bau. $\endgroup$ – LucasSilva Apr 11 '15 at 19:37
  • $\begingroup$ If you know $P$ in advance, then you can factor it into elementary matrices, and then apply those operations algorithmically to $A$: $A \mapsto E_1 A E_{1}^{-1} \mapsto E_2 E_1 A E_{1}^{-1} E_{2}^{-1} \mapsto \cdots$. But knowing $P$ in advance is cheating. And if you could find $P$ using just rational operations, you could disprove the Abel-Ruffini theorem. $\endgroup$ – LucasSilva Apr 11 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.