Hello I am trying to get a better understanding of the Householder Method for converting a matrix to a tridiagonal system. We've learned it in class but I have a couple questions.
Are there any matrices that can't be converted with the Householder Method?
Does Householder require the matrix to be n x n? can we have have non n x n, tridiagonal matrices?
This last question isn't as important... But why would one want to find the householder form of a matrix? What significance does it have?
The Householder reduction method converts the matrix to Hessenberg form which is like an upper triangular matrix but with one extra diagonal beneath the main diagonal. If the matrix is Hermitian you will get a tridiagonal matrix.
This last question isn't as important... But why would one want to find the householder form of a matrix? What significance does it have?
When you complete the step to Hessenberg form it cuts the number of computations in half. When it is in the tridiagonal form it is less. The number of operations for Hessenberg form is $ \approx \frac{10}{3} m^{3}$ flops whereas for tridiagonal form it would be $\approx \frac{ 4}{3} m^{3}$ flops. The savings is based on the sparsity of the matrix.
Does Householder require the matrix to be n x n? can we have have non n x n, tridiagonal matrices?
Yes. The point of the reduction is to find the eigenvalues which non-square matrices don't have but there is a difference between Householder for the QR decomp and the Householder reduction you're talking about. If you look specifically at how they're implemented they're similar but not quite the same.
The entire point of the reduction is a stage between finding the eigenvalues of a matrix to reduce the number of computations. You don't have to do it. It just makes it faster.