To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T08:51:00Z http://mathoverflow.net/feeds/question/37853 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37853/to-what-extent-can-algorithms-in-undergraduate-linear-algebra-be-made-continuous To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.? Theo Johnson-Freyd 2010-09-06T07:44:48Z 2010-09-08T04:02:27Z <p>I feel like many of the algorithms that I learned &mdash; indeed, that I have taught &mdash; 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.</p> <p>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 &mdash; they don't even depend continuously, only semicontinuously &mdash; 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.</p> <p>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:</p> <blockquote> <p>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 &mdash; e.g. when the coefficients are given by truncated decimal expansions &mdash; 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?</p> </blockquote> <p>My motivation for asking this question was the (closed) question <a href="http://mathoverflow.net/questions/37842/matrix-that-annihilates-matrix" rel="nofollow">matrix that annihilates matrix</a>, 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.)</p> http://mathoverflow.net/questions/37853/to-what-extent-can-algorithms-in-undergraduate-linear-algebra-be-made-continuous/37858#37858 Answer by Charles Matthews for To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.? Charles Matthews 2010-09-06T08:25:30Z 2010-09-06T08:25:30Z <p>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).</p> <p>There is a whole area of "numerical linear algebra" for those who need actual answers involving real numbers, that are meaningful and stable.</p> <p>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.</p> <p>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. </p> http://mathoverflow.net/questions/37853/to-what-extent-can-algorithms-in-undergraduate-linear-algebra-be-made-continuous/38029#38029 Answer by mathreader for To what extent can algorithms in undergraduate linear algebra be made continuous/polynomial/etc.? mathreader 2010-09-08T04:02:27Z 2010-09-08T04:02:27Z <p>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.</p>