We investigate the expressive power of $mathsf{MATLANG}$, a formal languagefor matrix manipulation based on common matrix operations and linear algebra.The language can be extended with the operation $mathsf{inv}$ of inverting amatrix. In $mathsf{MATLANG}+mathsf{inv}$ we can compute the transitiveclosure of directed graphs, whereas we show that this is not possible withoutinversion. Indeed we show that the basic language can be simulated in therelational algebra with arithmetic operations, grouping, and summation. We alsoconsider an operation $mathsf{eigen}$ for diagonalizing a matrix, which isdefined so that different eigenvectors returned for a same eigenvalue areorthogonal. We show that $mathsf{inv}$ can be expressed in$mathsf{MATLANG}+mathsf{eigen}$. We put forward the open question whetherthere are boolean queries about matrices, or generic queries about graphs,expressible in $mathsf{MATLANG} + mathsf{eigen}$ but not in$mathsf{MATLANG}+mathsf{inv}$. The evaluation problem for $mathsf{MATLANG} +mathsf{eigen}$ is shown to be complete for the complexity class $existsmathbf{R}$.
展开▼
