When Can Matrix Query Languages Discern Matrices?
Geerts, Floris
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.
 Hi everyone, I'm Floris Geertz, welcome to my video presentation and I'm going to talk about matrix square languages and their expressive power. So let me first remind you what I mean by matrix square language. So with the matrix square language, I mean a bunch of atomic linear algebra operators such as matrix multiplication, linear combinations, transpositions, which is basically switching the rows and the columns of a matrix, trace computation, it looks like the diagonal elements and sums them up, one vector which is just a vector consisting of all ones, diagonalizing a vector which is putting the vector on the diagonal of a matrix, and finally point wise function applications which basically applies any kind of function to every entry of a matrix. Now given these basically linear algebra operators, we can make more complicated general expressions in our language just by composition and then we also use an input variable x for the input matrix. Now more generally, I will be considering matrix square language fragments which are denoted by MLL, where L is basically just a list of supported operators. In particular, I will only look at sentences in such a language and intuitively what such a sentence will do, it will just extract a single numerical quantity from a matrix. In the definition below, I'll make this more formal, so I say a sentence ex in my query language fragment describes a function from matrices to the reels. So basically you take a matrix as input and a sentence will map this matrix to a single real number. Now I know that many of you don't really like linear algebra or real numbers, so just think about matrices as a adjacency matrix of graphs and then basically a matrix square language is just a linear algebra based graph query language. So sentences that's going to be the focus and I want to measure somehow the expressive power of a matrix query language. And how am I going to do this, I'm going to introduce a notion of indistinguishability for two matrices given a matrix query language. So the definition here, I have two matrices A and B and I will call them indistinguishable with respect to my fragment that I'm looking at. Even only if all sentences that I can formulate in this matrix query language fragment will give the same value when applied to A to matrix A or to matrix B. So in other words, there is no way that you can extract some numerical quantity from those matrices that allows you to distinguish them. Now if A and B are adjacency matrices of graphs G and H, then basically the definition here on top, it basically is a generalization of biological equivalence of graphs. So what I want to do or what I'm interested in is to characterize when two matrices are indistinguishable. And this I want to kind of understand or characterize for various matrix query language fragments. In earlier work I did the same exercise or a similar exercise for unrected graphs which have symmetric adjacency matrices. And in this paper I'm actually lifting many of the results to directed graphs and more generally to arbitrary matrices. So let's consider for the moment graphs or more particular adjacency matrices and let's see what kind of results one can expect here. And so again, just to go to the previous slides, we want to understand when two given matrices A and B are indistinguishable. So there are two results that I would like to have. The first one is a logical one, a logical characterization. And this basically kind of is going to tell you that given two graphs G and H, they will be indistinguishable with respect to a matrix query language, in the only if this notion corresponds to some logical equivalence in some known logic. The second kind of result that I would like to have is in terms of graph properties. So in that case, you're given two adjacency matrices of a graph of graphs G and H. And you want to tell that these two graphs or adjacency matrices are equivalent or indistinguishable even only if the graph shares on graph properties. Now in the paper, I make connections to two and three variable fragments of first order logic with counting. So this corresponds to the logical kind of result that I was mentioning before. And secondly, I'm also making connections with graph properties, very simple ones like the number of walks, number of closed walks, equitable partitions, fractional isomorphisms and go and algebra. I'm not going to go into detail here. But what's nice about these results or what nice about the paper is that many of these kind of results for graphs, they automatically follow from characterizations for general matrices. So what I'm going to do next is I'm going to focus on general matrices. And let me first kind of try to explain what kind of results about indistinguishability that you can expect for general matrices. So what I'm going to do is I'm going to relate the notion of equivalence of two matrices or indistinguishability of two matrices A and B in terms of a notion of congruence. And this congruence is defined in terms of another class of matrices. And intuitively what this congruence means, it's just a way of transforming a matrix A to a matrix B by means of linear transformation, which come from this class of matrices. So this is described in this equation over here where you basically have matrix A, matrix B, and there is a well-described way of actually kind of going from this matrix A to matrix B. Now, there are also in this equation there are two operators like the PA and the PB, and these are optional projection matrices. I won't have time to go into detail about these projection matrices. So for more details, please look at the paper. Now, what does this congruence intuitively do? So if you look at equivalence of two matrices with respect to some matrix square language fragments, this notion basically divides the whole space of matrices into chunks into equivalence classes. And this congruency, like the right motion of congruency of two matrices, it will basically allow you to tell when two matrices belong to the same equivalence class. So you have a stratification, a partitioning of the space of all matrices, and each of these blocks, each of these equivalence classes is going to be described by such congruence relation. So what is technically going on in the paper is that I'm identifying for all possible matrix square language fragments L, I identify the right class of matrices with which to define the motion of congruence. Now, example classes of such congruence matrices, orthogonal matrices, doubly stochastic matrices and so on, I'm not going to go into detail here, but you can identify with each matrix square language fragments its own proper class of transformation, which means to define congruence. Now, what we need to show is that the equivalence of matrices with respect to the matrix square language indeed coincides with this notion of congruence that we are going to identify. Now, given a candidate's class of transformation, it's reasonably easy to show that when two matrices are indeed congruent with respect to this notion, that they will also be equivalent or indistinguishable with respect to the matrix square language. And the reason for this is very simple because basically you need just to check whether certain invariance properties of the operations in your matrix square language fragments hold. And so the congruence notion, it basically tells you when two matrices are equivalent and you have to just show that every of the atomic basic operators that are supported in the matrix square language are indeed also invariant under such notions of congruence. What is more challenging is the other direction. So if you only know that you're given two matrices A and B and they are indistinguishable with respect to your matrix square language to actually kind of infer that there exists a matrix U in a particular class so that these two input matrices A and B become congruent. And this is especially challenging here because now we're working with general matrices. While previously, previously in the ICT 2019 paper, I restricted myself to adjacency matrices of undirected graphs which were symmetric. And symmetric matrices are known to be diagonalizable and this was a property that was really using in that previous paper. So what I want to do next or to kind of finish up the presentation is to highlight two main general proof techniques that allowed me to kind of define the right notion of congruence. And the first proof technique, it covers basically all fragments which support matrix multiplication, trace and transposition. And it relies on something, a theorem which is known as Pech's theorem. And this theorem is a theorem from representation theory. And what it basically does, it allows you to test congruency of matrices in terms of testing equality conditions of trace conditions. Now a trace condition can be seen because we're working with matrix square languages which have matrix multiplication, trace and transposition as sentences in your query language, in your matrix query language. So then when given A and B, which are equivalent with respect to this language, it will imply that this certain trace equality will hold and the type of trace equality that we can show that holds determines this class of congruency. In this case, in this setting for these fragments, no projection operators are needed. So in the example below, I have a very simple matrix query language fragment, matrix multiplication, trace and transposition. And then when I know that two matrices are equivalent with respect to this language, then I can tell that the trace of any product of A with its transpose should be equal to the trace of B with the same product of the transmitted transpose. If that holds, then Pech's theorem guarantees me that there exists a matrix O, which is in this case an orthogonal matrix that will link the two input matrices A and B. So the congruency notion here will be just based on orthogonal matrices. So that's the first proof technique. In the second proof technique, it basically covers all other fragments. So when you don't have trace or you don't have transposition. And here I'm relying on minimal realizations from, which is something that comes from linear control theory. And these minimal realizations, they actually are, you can be seen them as the core of the matrices. So they are, when your original matrices are kind of equivalent or in this thing, which will be with respect to your matrix query language, also the minimal realizations will be. So what's important about the fact that they're minimal is that they will automatically be congruent in some other way. Now then we can use projection operators to lift this notion of congruency on minimal on the smaller representations, the minimal realizations to congruencies on the original matrices. So a very simple example is here below. So I have again a matrix query language consisting of matrix multiplication to one's vector, which is a vector consisting of all ones, and then we have also the transpose of this vector. So it's just going to be a row vector consisting of all ones. So when the two matrices A and B are equivalent with respect to this language, then there are also their minimalizations A min and B min will be equivalent with respect to this language. And then you can show that these minimal realizations are in fact related by means of a doubly quasi stochastic matrix Q. Such a doubly quasi stochastic matrix Q is just a matrix all its rows and columns are of the one. Given this correspondence, this congruency between the minimal realizations, you can lift this using the projection operators to the original matrices A and B as it's shown below. And these two proof techniques, they have been shown to work for all fragments that you can define or consider, all sensible fragments that you can consider, given the basic atomic linear algebra operators that this language is constituting. So in summary, so using these new techniques, I've shown that you can obtain characterization of the equivalence of matrices, general matrices relative to some matrix square language fragments. As a nice consequence, you obtain the characterizations for the directed graphs. And as previous results for undirected graphs can be seen as special cases. So what I want to do next, or what can be done next, is actually use similar techniques that are developed in the paper to understand, for example, the linear algebra based learning methods, for example, on graphs. So many of these methods, for example, graph neural networks, can be seen as expressions in the matrix square language fragments with the addition that there are some learnable parameters. And so the setting that I discussed so far, it doesn't have such parameterized setting. And so the idea would be to actually understand better what are the capabilities of graph neural networks, for example, in terms of their expressive power using techniques developed in the current paper. So that's everything I wanted to say in this short presentation. So thanks for your attention. Please have a look at the paper if you want to find out more details or just interest in this topic. Thank you.
 Hi everyone, I'm Floris Geertz, welcome to my video presentation and I'm going to talk  about matrix square languages and their expressive power.  So let me first remind you what I mean by matrix square language.  So with the matrix square language, I mean a bunch of atomic linear algebra operators  such as matrix multiplication, linear combinations, transpositions, which is basically switching  the rows and the columns of a matrix, trace computation, it looks like the diagonal elements  and sums them up, one vector which is just a vector consisting of all ones, diagonalizing  a vector which is putting the vector on the diagonal of a matrix, and finally point wise  function applications which basically applies any kind of function to every entry of a matrix.  Now given these basically linear algebra operators, we can make more complicated general expressions  in our language just by composition and then we also use an input variable x for the input  matrix.  Now more generally, I will be considering matrix square language fragments which are  denoted by MLL, where L is basically just a list of supported operators.  In particular, I will only look at sentences in such a language and intuitively what such  a sentence will do, it will just extract a single numerical quantity from a matrix.  In the definition below, I'll make this more formal, so I say a sentence ex in my query  language fragment describes a function from matrices to the reels.  So basically you take a matrix as input and a sentence will map this matrix to a single  real number.  Now I know that many of you don't really like linear algebra or real numbers, so just think  about matrices as a adjacency matrix of graphs and then basically a matrix square language  is just a linear algebra based graph query language.  So sentences that's going to be the focus and I want to measure somehow the expressive  power of a matrix query language.  And how am I going to do this, I'm going to introduce a notion of indistinguishability  for two matrices given a matrix query language.  So the definition here, I have two matrices A and B and I will call them indistinguishable  with respect to my fragment that I'm looking at.  Even only if all sentences that I can formulate in this matrix query language fragment will  give the same value when applied to A to matrix A or to matrix B.  So in other words, there is no way that you can extract some numerical quantity from those  matrices that allows you to distinguish them.  Now if A and B are adjacency matrices of graphs G and H, then basically the definition  here on top, it basically is a generalization of biological equivalence of graphs.  So what I want to do or what I'm interested in is to characterize when two matrices are  indistinguishable.  And this I want to kind of understand or characterize for various matrix query language fragments.  In earlier work I did the same exercise or a similar exercise for unrected graphs which  have symmetric adjacency matrices.  And in this paper I'm actually lifting many of the results to directed graphs and more  generally to arbitrary matrices.  So let's consider for the moment graphs or more particular adjacency matrices and let's  see what kind of results one can expect here.  And so again, just to go to the previous slides, we want to understand when two given matrices  A and B are indistinguishable.  So there are two results that I would like to have.  The first one is a logical one, a logical characterization.  And this basically kind of is going to tell you that given two graphs G and H, they will  be indistinguishable with respect to a matrix query language, in the only if this notion  corresponds to some logical equivalence in some known logic.  The second kind of result that I would like to have is in terms of graph properties.  So in that case, you're given two adjacency matrices of a graph of graphs G and H. And  you want to tell that these two graphs or adjacency matrices are equivalent or indistinguishable  even only if the graph shares on graph properties.  Now in the paper, I make connections to two and three variable fragments of first order  logic with counting.  So this corresponds to the logical kind of result that I was mentioning before.  And secondly, I'm also making connections with graph properties, very simple ones like  the number of walks, number of closed walks, equitable partitions, fractional isomorphisms  and go and algebra.  I'm not going to go into detail here.  But what's nice about these results or what nice about the paper is that many of these  kind of results for graphs, they automatically follow from characterizations for general  matrices.  So what I'm going to do next is I'm going to focus on general matrices.  And let me first kind of try to explain what kind of results about indistinguishability  that you can expect for general matrices.  So what I'm going to do is I'm going to relate the notion of equivalence of two matrices  or indistinguishability of two matrices A and B in terms of a notion of congruence.  And this congruence is defined in terms of another class of matrices.  And intuitively what this congruence means, it's just a way of transforming a matrix A  to a matrix B by means of linear transformation, which come from this class of matrices.  So this is described in this equation over here where you basically have matrix A, matrix  B, and there is a well-described way of actually kind of going from this matrix A to matrix  B.  Now, there are also in this equation there are two operators like the PA and the PB, and  these are optional projection matrices.  I won't have time to go into detail about these projection matrices.  So for more details, please look at the paper.  Now, what does this congruence intuitively do?  So if you look at equivalence of two matrices with respect to some matrix square language  fragments, this notion basically divides the whole space of matrices into chunks into  equivalence classes.  And this congruency, like the right motion of congruency of two matrices, it will basically  allow you to tell when two matrices belong to the same equivalence class.  So you have a stratification, a partitioning of the space of all matrices, and each of  these blocks, each of these equivalence classes is going to be described by such congruence  relation.  So what is technically going on in the paper is that I'm identifying for all possible matrix  square language fragments L, I identify the right class of matrices with which to define  the motion of congruence.  Now, example classes of such congruence matrices, orthogonal matrices, doubly stochastic matrices  and so on, I'm not going to go into detail here, but you can identify with each matrix  square language fragments its own proper class of transformation, which means to define congruence.  Now, what we need to show is that the equivalence of matrices with respect to the matrix square  language indeed coincides with this notion of congruence that we are going to identify.  Now, given a candidate's class of transformation, it's reasonably easy to show that when two  matrices are indeed congruent with respect to this notion, that they will also be equivalent  or indistinguishable with respect to the matrix square language.  And the reason for this is very simple because basically you need just to check whether certain  invariance properties of the operations in your matrix square language fragments hold.  And so the congruence notion, it basically tells you when two matrices are equivalent  and you have to just show that every of the atomic basic operators that are supported  in the matrix square language are indeed also invariant under such notions of congruence.  What is more challenging is the other direction.  So if you only know that you're given two matrices A and B and they are indistinguishable  with respect to your matrix square language to actually kind of infer that there exists  a matrix U in a particular class so that these two input matrices A and B become congruent.  And this is especially challenging here because now we're working with general matrices.  While previously, previously in the ICT 2019 paper, I restricted myself to adjacency matrices  of undirected graphs which were symmetric.  And symmetric matrices are known to be diagonalizable and this was a property that was really using  in that previous paper.  So what I want to do next or to kind of finish up the presentation is to highlight two main  general proof techniques that allowed me to kind of define the right notion of congruence.  And the first proof technique, it covers basically all fragments which support matrix multiplication,  trace and transposition.  And it relies on something, a theorem which is known as Pech's theorem.  And this theorem is a theorem from representation theory.  And what it basically does, it allows you to test congruency of matrices in terms of testing  equality conditions of trace conditions.  Now a trace condition can be seen because we're working with matrix square languages  which have matrix multiplication, trace and transposition as sentences in your query  language, in your matrix query language.  So then when given A and B, which are equivalent with respect to this language, it will imply  that this certain trace equality will hold and the type of trace equality that we can  show that holds determines this class of congruency.  In this case, in this setting for these fragments, no projection operators are needed.  So in the example below, I have a very simple matrix query language fragment, matrix multiplication,  trace and transposition.  And then when I know that two matrices are equivalent with respect to this language,  then I can tell that the trace of any product of A with its transpose should be equal to  the trace of B with the same product of the transmitted transpose.  If that holds, then Pech's theorem guarantees me that there exists a matrix O, which is  in this case an orthogonal matrix that will link the two input matrices A and B.  So the congruency notion here will be just based on orthogonal matrices.  So that's the first proof technique.  In the second proof technique, it basically covers all other fragments.  So when you don't have trace or you don't have transposition.  And here I'm relying on minimal realizations from, which is something that comes from linear  control theory.  And these minimal realizations, they actually are, you can be seen them as the core of the  matrices.  So they are, when your original matrices are kind of equivalent or in this thing, which  will be with respect to your matrix query language, also the minimal realizations will  be.  So what's important about the fact that they're minimal is that they will automatically be  congruent in some other way.  Now then we can use projection operators to lift this notion of congruency on minimal  on the smaller representations, the minimal realizations to congruencies on the original  matrices.  So a very simple example is here below.  So I have again a matrix query language consisting of matrix multiplication to one's  vector, which is a vector consisting of all ones, and then we have also the transpose  of this vector.  So it's just going to be a row vector consisting of all ones.  So when the two matrices A and B are equivalent with respect to this language, then there  are also their minimalizations A min and B min will be equivalent with respect to this  language.  And then you can show that these minimal realizations are in fact related by means of a doubly quasi  stochastic matrix Q.  Such a doubly quasi stochastic matrix Q is just a matrix all its rows and columns are  of the one.  Given this correspondence, this congruency between the minimal realizations, you can  lift this using the projection operators to the original matrices A and B as it's shown  below.  And these two proof techniques, they have been shown to work for all fragments that you  can define or consider, all sensible fragments that you can consider, given the basic atomic  linear algebra operators that this language is constituting.  So in summary, so using these new techniques, I've shown that you can obtain characterization  of the equivalence of matrices, general matrices relative to some matrix square language fragments.  As a nice consequence, you obtain the characterizations for the directed graphs.  And as previous results for undirected graphs can be seen as special cases.  So what I want to do next, or what can be done next, is actually use similar techniques  that are developed in the paper to understand, for example, the linear algebra based learning  methods, for example, on graphs.  So many of these methods, for example, graph neural networks, can be seen as expressions  in the matrix square language fragments with the addition that there are some learnable  parameters.  And so the setting that I discussed so far, it doesn't have such parameterized setting.  And so the idea would be to actually understand better what are the capabilities of graph  neural networks, for example, in terms of their expressive power using techniques developed  in the current paper.  So that's everything I wanted to say in this short presentation.  So thanks for your attention.  Please have a look at the paper if you want to find out more details or just interest in  this topic.  Thank you.
Geerts_0_59.png Geerts_60_131.png Geerts_132_323.png Geerts_324_587.png Geerts_588_1655.png Geerts_1656_3239.png Geerts_3240_4331.png Geerts_4332_4619.png Geerts_4620_4943.png Geerts_4944_5387.png Geerts_5388_5735.png Geerts_5736_5903.png Geerts_5904_7931.png Geerts_7932_11291.png Geerts_11292_12659.png Geerts_12660_13943.png Geerts_13944_16355.png Geerts_16356_19295.png Geerts_19296_21386.png
Hi everyone, I'm Floris Geertz, welcome to my video presentation and I'm going to talk about matrix square languages and their expressive power. So let me first remind you what I mean by matrix square language. So with the matrix square language, I mean a bunch of atomic linear algebra operators such as matrix multiplication, linear combinations, transpositions, which is basically switching the rows and the columns of a matrix, trace computation, it looks like the diagonal elements and sums them up, one vector which is just a vector consisting of all ones, diagonalizing a vector which is putting the vector on the diagonal of a matrix, and finally point wise function applications which basically applies any kind of function to every entry of a matrix. Now given these basically linear algebra operators, we can make more complicated general expressions in our language just by composition and then we also use an input variable x for the input matrix. Now more generally, I will be considering matrix square language fragments which are denoted by MLL, where L is basically just a list of supported operators. In particular, I will only look at sentences in such a language and intuitively what such a sentence will do, it will just extract a single numerical quantity from a matrix. In the definition below, I'll make this more formal, so I say a sentence ex in my query language fragment describes a function from matrices to the reels. So basically you take a matrix as input and a sentence will map this matrix to a single real number. Now I know that many of you don't really like linear algebra or real numbers, so just think about matrices as a adjacency matrix of graphs and then basically a matrix square language is just a linear algebra based graph query language. So sentences that's going to be the focus and I want to measure somehow the expressive power of a matrix query language. And how am I going to do this, I'm going to introduce a notion of indistinguishability for two matrices given a matrix query language. So the definition here, I have two matrices A and B and I will call them indistinguishable with respect to my fragment that I'm looking at. Even only if all sentences that I can formulate in this matrix query language fragment will give the same value when applied to A to matrix A or to matrix B. So in other words, there is no way that you can extract some numerical quantity from those matrices that allows you to distinguish them. Now if A and B are adjacency matrices of graphs G and H, then basically the definition here on top, it basically is a generalization of biological equivalence of graphs. So what I want to do or what I'm interested in is to characterize when two matrices are indistinguishable. And this I want to kind of understand or characterize for various matrix query language fragments. In earlier work I did the same exercise or a similar exercise for unrected graphs which have symmetric adjacency matrices. And in this paper I'm actually lifting many of the results to directed graphs and more generally to arbitrary matrices. So let's consider for the moment graphs or more particular adjacency matrices and let's see what kind of results one can expect here. And so again, just to go to the previous slides, we want to understand when two given matrices A and B are indistinguishable. So there are two results that I would like to have. The first one is a logical one, a logical characterization. And this basically kind of is going to tell you that given two graphs G and H, they will be indistinguishable with respect to a matrix query language, in the only if this notion corresponds to some logical equivalence in some known logic. The second kind of result that I would like to have is in terms of graph properties. So in that case, you're given two adjacency matrices of a graph of graphs G and H. And you want to tell that these two graphs or adjacency matrices are equivalent or indistinguishable even only if the graph shares on graph properties. Now in the paper, I make connections to two and three variable fragments of first order logic with counting. So this corresponds to the logical kind of result that I was mentioning before. And secondly, I'm also making connections with graph properties, very simple ones like the number of walks, number of closed walks, equitable partitions, fractional isomorphisms and go and algebra. I'm not going to go into detail here. But what's nice about these results or what nice about the paper is that many of these kind of results for graphs, they automatically follow from characterizations for general matrices. So what I'm going to do next is I'm going to focus on general matrices. And let me first kind of try to explain what kind of results about indistinguishability that you can expect for general matrices. So what I'm going to do is I'm going to relate the notion of equivalence of two matrices or indistinguishability of two matrices A and B in terms of a notion of congruence. And this congruence is defined in terms of another class of matrices. And intuitively what this congruence means, it's just a way of transforming a matrix A to a matrix B by means of linear transformation, which come from this class of matrices. So this is described in this equation over here where you basically have matrix A, matrix B, and there is a well-described way of actually kind of going from this matrix A to matrix B. Now, there are also in this equation there are two operators like the PA and the PB, and these are optional projection matrices. I won't have time to go into detail about these projection matrices. So for more details, please look at the paper. Now, what does this congruence intuitively do? So if you look at equivalence of two matrices with respect to some matrix square language fragments, this notion basically divides the whole space of matrices into chunks into equivalence classes. And this congruency, like the right motion of congruency of two matrices, it will basically allow you to tell when two matrices belong to the same equivalence class. So you have a stratification, a partitioning of the space of all matrices, and each of these blocks, each of these equivalence classes is going to be described by such congruence relation. So what is technically going on in the paper is that I'm identifying for all possible matrix square language fragments L, I identify the right class of matrices with which to define the motion of congruence. Now, example classes of such congruence matrices, orthogonal matrices, doubly stochastic matrices and so on, I'm not going to go into detail here, but you can identify with each matrix square language fragments its own proper class of transformation, which means to define congruence. Now, what we need to show is that the equivalence of matrices with respect to the matrix square language indeed coincides with this notion of congruence that we are going to identify. Now, given a candidate's class of transformation, it's reasonably easy to show that when two matrices are indeed congruent with respect to this notion, that they will also be equivalent or indistinguishable with respect to the matrix square language. And the reason for this is very simple because basically you need just to check whether certain invariance properties of the operations in your matrix square language fragments hold. And so the congruence notion, it basically tells you when two matrices are equivalent and you have to just show that every of the atomic basic operators that are supported in the matrix square language are indeed also invariant under such notions of congruence. What is more challenging is the other direction. So if you only know that you're given two matrices A and B and they are indistinguishable with respect to your matrix square language to actually kind of infer that there exists a matrix U in a particular class so that these two input matrices A and B become congruent. And this is especially challenging here because now we're working with general matrices. While previously, previously in the ICT 2019 paper, I restricted myself to adjacency matrices of undirected graphs which were symmetric. And symmetric matrices are known to be diagonalizable and this was a property that was really using in that previous paper. So what I want to do next or to kind of finish up the presentation is to highlight two main general proof techniques that allowed me to kind of define the right notion of congruence. And the first proof technique, it covers basically all fragments which support matrix multiplication, trace and transposition. And it relies on something, a theorem which is known as Pech's theorem. And this theorem is a theorem from representation theory. And what it basically does, it allows you to test congruency of matrices in terms of testing equality conditions of trace conditions. Now a trace condition can be seen because we're working with matrix square languages which have matrix multiplication, trace and transposition as sentences in your query language, in your matrix query language. So then when given A and B, which are equivalent with respect to this language, it will imply that this certain trace equality will hold and the type of trace equality that we can show that holds determines this class of congruency. In this case, in this setting for these fragments, no projection operators are needed. So in the example below, I have a very simple matrix query language fragment, matrix multiplication, trace and transposition. And then when I know that two matrices are equivalent with respect to this language, then I can tell that the trace of any product of A with its transpose should be equal to the trace of B with the same product of the transmitted transpose. If that holds, then Pech's theorem guarantees me that there exists a matrix O, which is in this case an orthogonal matrix that will link the two input matrices A and B. So the congruency notion here will be just based on orthogonal matrices. So that's the first proof technique. In the second proof technique, it basically covers all other fragments. So when you don't have trace or you don't have transposition. And here I'm relying on minimal realizations from, which is something that comes from linear control theory. And these minimal realizations, they actually are, you can be seen them as the core of the matrices. So they are, when your original matrices are kind of equivalent or in this thing, which will be with respect to your matrix query language, also the minimal realizations will be. So what's important about the fact that they're minimal is that they will automatically be congruent in some other way. Now then we can use projection operators to lift this notion of congruency on minimal on the smaller representations, the minimal realizations to congruencies on the original matrices. So a very simple example is here below. So I have again a matrix query language consisting of matrix multiplication to one's vector, which is a vector consisting of all ones, and then we have also the transpose of this vector. So it's just going to be a row vector consisting of all ones. So when the two matrices A and B are equivalent with respect to this language, then there are also their minimalizations A min and B min will be equivalent with respect to this language. And then you can show that these minimal realizations are in fact related by means of a doubly quasi stochastic matrix Q. Such a doubly quasi stochastic matrix Q is just a matrix all its rows and columns are of the one. Given this correspondence, this congruency between the minimal realizations, you can lift this using the projection operators to the original matrices A and B as it's shown below. And these two proof techniques, they have been shown to work for all fragments that you can define or consider, all sensible fragments that you can consider, given the basic atomic linear algebra operators that this language is constituting. So in summary, so using these new techniques, I've shown that you can obtain characterization of the equivalence of matrices, general matrices relative to some matrix square language fragments. As a nice consequence, you obtain the characterizations for the directed graphs. And as previous results for undirected graphs can be seen as special cases. So what I want to do next, or what can be done next, is actually use similar techniques that are developed in the paper to understand, for example, the linear algebra based learning methods, for example, on graphs. So many of these methods, for example, graph neural networks, can be seen as expressions in the matrix square language fragments with the addition that there are some learnable parameters. And so the setting that I discussed so far, it doesn't have such parameterized setting. And so the idea would be to actually understand better what are the capabilities of graph neural networks, for example, in terms of their expressive power using techniques developed in the current paper. So that's everything I wanted to say in this short presentation. So thanks for your attention. Please have a look at the paper if you want to find out more details or just interest in this topic. Thank you.
to measure somehow the expressive power of a actually lifting many of the results to directed graphs and more generally to arbitrary matrices. particular adjacency matrices and let's see what to understand when two given matrices A and B are case, you're given two adjacency matrices of a that these two graphs or adjacency matrices are walks, number of closed walks, equitable a matrix A to a matrix B by means of linear symmetric. And symmetric matrices are known to be proof techniques that allowed me to kind of trace and transposition. And it relies on and transposition as sentences in your query from, which is something that comes from linear control theory. And these minimal realizations, matrix query language consisting of matrix the two matrices A and B are equivalent with the basic atomic linear algebra operators that undirected graphs can be seen as special cases.