# MultiAspect Graphs: Algebraic Representation and Algorithms
## 3 Algebraic Representation
### Adjacency Matrix
\[\mathbf{J}(T)=\left[ \begin{array}{cccccccccccccccc}0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0 &0&0\\ 0&0&0&0&\mathbf{1}&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0&0&0&0&0\\ 0&\mathbf{1}&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&\mathbf{1}&0&\mathbf{1}&\mathbf{1}&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0\\ 0&0&0&0&0&0&\mathbf{1}&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ \end{array} \right] \tag{21}\]  
It is important to note that the sequence of the columns and rows of \(\mathbf{J}(T)\) is given by the numerical representation of the composite vertices. Thus, for instance, the 1 at row 2, column 8 represents the edge between the composite vertices with numerical representations 2 and 8, with in turn represents the edge \((2,Bus,t_{1},2,Bus,t_{2})\) of the MAG \(T\). In this way, although \(\mathbf{J}(T)\) is presented in matrix form, together with the companion tuple \(\tau(T)\), it fully represents the MAG \(T\), carrying the proper adjacency notion used to define transitive constructions, such as walks and paths on the MAG. For an arbitrary MAG \(H\), its main components graph \(m(H)\) is obtained by removing the MAG's trivial components, as stated in Section 3.3. The matrix \(\mathbf{J}(m(H))\) is then obtained with the use of the matrix \(\mathbf{R}(H)\), presented in Section 3.3. \  
\[\mathbf{J}(m(T))=\left[ \begin{array}{cccccccccccc}0&0&0&\mathbf{1}&\mathbf{1}& \mathbf{1}&0&0&0&0&0&0\\ 0&0&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0&0&0\\ 0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0\\ \mathbf{1}&0&0&0&0&0&\mathbf{1}&\mathbf{1}&0&0&0&0\\ 0&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}&\mathbf{1}&0&0\\ 0&0&0&0&0&0&0&0&0&\mathbf{1}&\mathbf{1}\\ 0&0&0&0&\mathbf{1}&0&0&0&0&\mathbf{1}&\mathbf{1}\\ 0&0&0&0&0&0&0&0&0&0&\mathbf{1}\\ 0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&\mathbf{1}&0&0&0\end{array} \right]. \tag{25}\]  
In general, the adjacency matrices associated with a MAG are sparse, meaning that for an \(n\times n\) adjacency matrix the number of non-zero entries of the matrix is of the order \(O(n)\). Since the non-zero entries on the MAG adjacency matrix corresponds to the edges present on the MAG, the adjacency matrix being sparse means that the number of edges \(m\) on the MAG is of the same order of the number of composite vertices \(n\), i.e., \(m\) is of order \(O(n)\). Therefore, these matrices can be stored efficiently using sparse matrices representations, such as Compressed Sparse Column (CSC) or Compressed Sparse Row (CSR) [33], because such representations omit all entries of value zero. Assuming that the number of edges is larger than the number of composite vertices, these representations provide a space complexity of \(O(m)\) for storing the MAG's adjacency matrices. Further, they also provide efficient matrix operations, which will be explored in the algorithms presented in Section 4.