2026-07-24T21:21:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11936 2024-03-12T11:56:50Z ddc:004 open_access

When Can Matrix Query Languages Discern Matrices? Geerts, Floris matrix query languages linear algebra expressive power We investigate when two graphs, represented by their adjacency matrices, can be distinguished by means of sentences formed in MATLANG, a matrix query language which supports a number of elementary linear algebra operators. When undirected graphs are concerned, and hence the adjacency matrices are real and symmetric, precise characterisations are in place when two graphs (i.e., their adjacency matrices) can be distinguished. Turning to directed graphs, one has to deal with asymmetric adjacency matrices. This complicates matters. Indeed, it requires to understand the more general problem of when two arbitrary matrices can be distinguished in MATLANG. We provide characterisations of the distinguishing power of MATLANG on real and complex matrices, and on adjacency matrices of directed graphs in particular. The proof techniques are a combination of insights from the symmetric matrix case and results from linear algebra and linear control theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Floris Geerts 2020 Is Part Of LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2020.12 urn:nbn:de:0030-drops-119361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode