  Linear algebra algorithms often require some sort of iteration or recursion
as is illustrated by standard algorithms for Gaussian elimination, matrix
inversion, and transitive closure. A key characteristic shared by these
algorithms is that they allow looping for a number of steps that is bounded by
the matrix dimension. In this paper we extend the matrix query language MATLANG
with this type of recursion, and show that this suffices to express classical
linear algebra algorithms. We study the expressive power of this language and
show that it naturally corresponds to arithmetic circuit families, which are
often said to capture linear algebra. Furthermore, we analyze several
sub-fragments of our language, and show that their expressive power is closely
tied to logical formalisms on semiring-annotated relations.
