# Expressive power of linear algebra query languages

arXiv: https://arxiv.org/abs/2010.13717 · HTML: https://mlsanity.com/paper/2010.13717/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2020.

## Built on by (most cited first, 4 of 4)

- [Separation Power of Equivariant Neural Networks](https://mlsanity.com/paper/2406.08966/) (2024)
- [ToL: A Tensor of List-Based Unified Computation Model](https://mlsanity.com/paper/2212.10740/) (2022)
- [AMULET: Adaptive Matrix-Multiplication-Like Tasks](https://mlsanity.com/paper/2305.08872/) (2023)
- [IterLara: A Turing Complete Algebra for Big Data, AI, Scientific Computing, and Database](https://mlsanity.com/paper/2307.08315/) (2023)

## Abstract (arXiv)

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.