# On the expressive power of query languages for matrices

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2017.

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

- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [Going Deeper into Permutation-Sensitive Graph Neural Networks](https://mlsanity.com/paper/2205.14368/) (2022)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [Functional Collection Programming with Semi-Ring Dictionaries](https://mlsanity.com/paper/2103.06376/) (2021)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [Incorporating Heterophily into Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/2203.07678/) (2022)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)
- [Beyond 1-WL with Local Ego-Network Encodings](https://mlsanity.com/paper/2211.14906/) (2022)
- [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026)
- [ToL: A Tensor of List-Based Unified Computation Model](https://mlsanity.com/paper/2212.10740/) (2022)
- [Technical report: Graph Neural Networks go Grammatical](https://mlsanity.com/paper/2303.01590/) (2023)
- [Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning](https://mlsanity.com/paper/2410.01661/) (2024)

## Abstract (arXiv)

We investigate the expressive power of mathsfMATLANG, a formal language for matrix manipulation based on common matrix operations and linear algebra. The language can be extended with the operation mathsfinv of inverting a matrix. In mathsfMATLANG+mathsfinv we can compute the transitive closure of directed graphs, whereas we show that this is not possible without inversion. Indeed we show that the basic language can be simulated in the relational algebra with arithmetic operations, grouping, and summation. We also consider an operation mathsfeigen for diagonalizing a matrix, which is defined so that different eigenvectors returned for a same eigenvalue are orthogonal. We show that mathsfinv can be expressed in mathsfMATLANG+mathsfeigen. We put forward the open question whether there are boolean queries about matrices, or generic queries about graphs, expressible in mathsfMATLANG + mathsfeigen but not in mathsfMATLANG+mathsfinv. The evaluation problem for mathsfMATLANG + mathsfeigen is shown to be complete for the complexity class exists R.