Lanczos tridiagonalization and core problems Original Research Article

The Lanczos tridiagonalization orthogonally transforms a real symmetric matrix A to symmetric tridiagonal form. The Golub–Kahan bidiagonalization orthogonally reduces a nonsymmetric rectangular matrix to upper or lower bidiagonal form. Both algorithms are very closely related. The paper [C.C. Paige, Z. Strakoš, Core problems in linear algebraic systems, SIAM J. Matrix Anal. Appl. 27 (2006) 861–875] presents a new formulation of orthogonally invariant linear approximation problems Ax ≈ b. It is proved that the partial upper bidiagonalization of the extended matrix [b, A] determines a core approximation problem A11x1 ≈ b1, with all necessary and sufficient information for solving the original problem given by b1 and A11. It is further shown how the core problem can be used in a simple and efficient way for solving different formulations of the original approximation problem. Our contribution relates the core problem formulation to the Lanczos tridiagonalization and derives its characteristics from the relationship between the Golub–Kahan bidiagonalization, the Lanczos tridiagonalization and the well-known properties of Jacobi matrices.