Computability in linear algebra

Abstract

Many problems in Linear Algebra can be solved by Gaussian Elimination. This famous algorithm applies to an algebraic model of real number computation where operations +, -, *, / and tests like, e.g., < and == are presumed exact. Implementations of algebraic algorithms on actual digital computers often lead to numerical instabilities, thus revealing a serious discrepancy between model and reality.

A different model of real number computation dating back to Alan Turing considers real numbers as limits of rational approximations. In that widely believed to be more realistic notion of computability, we investigate problems from Linear Algebra. Our central results yield algorithms which in this sense

solve systems of linear equations A (.) x = b,

determine the spectral resolution of a symmetric matrix B,

and compute a linear subspace's dimension from its Euclidean distance function,

provided the rank of A and the number of distinct eigenvalues of B are known. Without such restrictions, the first two problems are shown to be, in general, uncomputable. (C) 2004 Elsevier B.V. All rights reserved.