On the expressive power of query languages for matrices

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.