There are some algorithms for transforming arrowhead matrices to tridiagonal form. Is any arrowhead matrix similar to a tridiagonal matrix? What techniques can we use to prove that an arrowhead matrix is similar to a tridiagonal matrix?
Dear Wiwat
Really, there are quite o lot of algorithms for transforming arrowhead matrices into tridiagonal ones (much easier for eigenvalues counting). We know that in general if A, B are similar, then they have the same determinant, eigenvalues, trace, and so on. Unfortunately, converse is not true. The only technique, I think, is finding a matrix M such that A = M-1BM..
Greetings, Tadeusz
For symmetric matrices there are ways to show the similarity. One way is to start with an arrowhead matrix, and find its eigenvalues, then construct a tridiagonal matrix with those eigenvalues. The existence of the tridiagonal matrices with a given set of eigenvalues is shown in several papers. One best source is: A.L. Duarte, Construction of acyclic matrices from spectral data, Linear Algebra Appl., 113 (1989) 173–182.
Then the easiest way to show the similarity I think is by the diagonalization.
Any matrix A is similar to a matrix H which is upper Hessenberg and there is an orthonormal similarity transformation. The appropriate keywords are "reduction to Hessenberg form". The transformation is frequently carried out using Householder reflections. If the matrix A is also symmetric, then so is H, and the Hessenberg structure implies that H is also tridiagonal. In short, if A is symmetric, then the sparsity pattern is "only" important in the sense that it affects the time spent to complete the transformation to tridiagonal form.
Dear Tadeusz, Keivan Hassani, and Carl Christian Kjelgaard,
Thank you so much for your kindly comments and advice.
@Tadeusz, we would like to find the matrix M.
@Keivan Hassani, the arrowhead matrix not necessary a symmetric matrix.
@Carl Christian Kjelgaard, tridiagonal matrix need not be triangular matrix.
Thank you.
Regards,
Wiwat Wanicharpichat
@Wiwat. My apologies, I wrote triangular twice where I should have written tridiagonal. I have edited my original answer. A Hessenberg matrix which is also symmetric is automatically tridiagonal. I realize that you interested in the general nonsymmetric case, and I do not have an answer there.
Every square complex matrix is similar to a direct sum of Jordan blocks, referred to as Jordan canonical form or simply Jordan form. Since the Jordan form is a bidiagonal matrix it is also a special tridiagonal matrix. Therefore the answer of my question is "Yes".
We need another tridiagonal form which is not Jordan form.
Here is an idea, if you don't mind zeros on the superdiagonal and subdiagonal entries:
Find the eigenvalues of the arrowhead matrix A, say aj + i bj , aj - i bj, and cj's and form the matrix B, the direct sum of [ [ aj , bj ] , [ -bj , aj ] ]'s and diag( cj ). That's a tridiagonal matrix with the given eigenvalues.
Keivan, for a matrix of order n ≥ 5, we see that the characteristic equation can not solvable by radicals, therefore it is not easy to find the eigenvalues of the arrowhead matrix A.
Hi Wiwat,
I haven't read this paper, but it might help: https://www.jstor.org/stable/pdf/2584980.pdf?seq=1#page_scan_tab_contents
Also, see this one: http://www.sciencedirect.com/science/article/pii/S0024379507004697 The question is much stronger, but the ideas might help.
- Badges
- Science topic
- Similar topics
- Mathematics
- Algebra
- Matrix