2 changed the title

1

# To what extent can algorithms in undergraduate linear algebra be made algebraic?

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