# To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.?

I feel like many of the algorithms that I learned — indeed, that I have taught — in undergraduate linear algebra classes depend sensitively on whether certain numbers are $0$. For example, many a linear algebra homework exercise consists of a matrix and a request that the student calculate a basis for the kernel or image. The standard approach consists of row-reducing the matrix and reading off the answer. The algorithm to row-reduce a matrix has many steps of the form "if $a \neq 0$, do something that involves a division by $a$, and if $a = 0$, do something else". Such a step is unfortunate from many points of view. In particular, it is not even continuous in $a$, so if you only have partial data about the value of $a$ (say, a truncated decimal expansion), then you cannot hope to apply this algorithm.

For the purpose of calculating kernel and image bases, perhaps this is not too surprising. Indeed, the dimensions of the kernel and image of a basis do not depend polynomially on the coefficients — they don't even depend continuously, only semicontinuously — and so there is really no hope in writing an algorithm that computes the coefficients of a basis for either and that is algebraic in the matrix.

On the other hand, even the usual algorithm we teach to compute inverses to invertible matrices again uses row reduction. The final answer is algebraic in the matrix coefficients, and there are algorithms that run algebraically (something to do with minors). So my (slightly ambiguous and open-ended) questions are:

What problems in undergraduate linear algebra can be solved by algorithms that are totally polynomial/algebraic/continuous in the matrix coefficients? In settings where there is not complete information about a matrix — e.g. when the coefficients are given by truncated decimal expansions — what types of algorithms do people actually use to "approximate" the answers to problems that cannot be solved continuously? And how do people who do such problems measure/define how good their "approximations" are?

My motivation for asking this question was the (closed) question matrix that annihilates matrix, in which the asker asks for an algorithm that, when fed an $n\times m$ matrix $A$, computes an $m\times n$ matrix $B$ so that $\ker B = \operatorname{im} A$. This is another example of a problem that is easy to do by row reduction, but it's not clear to me if there are solutions that run "more" continuously than that. (There won't be a completely continuous algorithm. Set $m=n$ and feed in an invertible matrix $A$. Then $B = 0$. But the invertibles are dense among all matrices.)

• I don't follow the statement that there are algorithms for computing inverses which run "algebraically" as opposed to "discontinuosly." Consider the problem of solving the equation $ax=1$. The solution is: if $a \neq 0$, output $x=1/a$, else output "no solution." This depends "discontinuously" on $a$, so I gather you would dislike it, but it is the correct answer, and any algorithm for solving systems of equations or computing inverses has to check if $a \neq 0$ somehow. – alex Sep 6 '10 at 8:20
• The usual requirements to an algorithm are (a) speed; (b) numerical stability. Are you interested in those + (c) algebraic (rational, etc) dependence on the parameters, or is it a purely theoretical question about which problems in LA admit an answer expressible by an algebraic formula? – Victor Protsak Sep 6 '10 at 8:25
• Concerning you motivation: the key step is to complement a subspace, and for a real vector space it's not necessary to use row reduction, you can compute the orthogonal complement instead. Indeterminacy arises because the dimension of the subspace, i.e. the rank of A, is only semialgebraic. – Victor Protsak Sep 6 '10 at 8:39
• Well, for one thing, the provably stable algorithms of numerical linear algebra all rely on the judicious use of orthogonal (unitary in the complex case) matrices. Yes, Gaussian elimination is a fluke. – J. M. isn't a mathematician Sep 6 '10 at 9:14
• May I suggest that you rephrase the title of the question a bit? The suggestion that there is some part of linear algebra which is "not algebraic" seems unnecessarily perplexing. – Pete L. Clark Sep 6 '10 at 17:15