# 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. 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

There are perhaps three or four themes lurking in here. NB that "undergraduate linear algebra" is perhaps an artificial construct, and examples set to test whether students understand basic concepts do not really need formal algorithms to do that. What "we teach" may simply be a pedagogic construct. NB the discussion about Cramer's rule already poses the issue of what the point is (formulae or practical answers).

There is a whole area of "numerical linear algebra" for those who need actual answers involving real numbers, that are meaningful and stable.

There is an underlying concept of "bad locus", e.g. the vanishing of the discriminant of the characteristic polynomial of a square matrix, so that most serious problems in linear algebra come out as working well away from the "bad locus". There is probably a way of saying this in algebraic terms, by inverting elements of rings. In other words one can teach things that work well on Zariski-open sets, and the question is then more one of conscience.

But there is another slant, which is that Gaussian elimination and what lies behind it reveal other kinds of serious mathematics. E.g. Schubert cells. Here the combinatorial problems of non-general position are not to be waved away. This material has retained such importance for mathematicians that I doubt it should be de-emphasised in teaching.

-
Good untangling of a convoluted post. It's hard to answer a query that is going in several directions at once. Unfortunately, that is a common situation when the motivation is nebulous. – Victor Protsak Sep 6 '10 at 9:07

If we talk about algorithms in a strict sense, then the data involved should be given constructively. This effectively limits us to rational numbers (represented as pairs of integers) or some 'easy' algebraic numbers (for which we can provide algorithms for basic arithmetic). And for these data types most linear algebra algorithms are polynomial in time and stable in the sense that they do not give any inaccuracy due to rounding/overflow/etc. This philosophy is implemented in the computer algebra system GAP.

-