# MultiAspect Graphs: Algebraic Representation and Algorithms
## 3 Algebraic Representation
### Adjacency Matrix  
As a direct consequence of the isomorphism between MAGs and traditional directed graphs, it is expected that a MAG can be represented in matrix form. In fact, such representations can be achieved directly by the composite vertices representation of MAGs, presented in Section 2.1. Since for any given MAG \(H\) its composite vertices representation is a traditional directed graph, it can be represented in matrix form. Figure 4: \(m(T)\) of the example MAG \(T\). One of such representations is the MAG's adjacency matrix. This matrix is obtained from the MAG's composite vertices representation, \(g(H)\), and its companion tuple \(\tau(H)\). In fact, the MAG's adjacency matrix is the adjacency matrix of the composite vertices representation, where the sequence of the rows and columns is given by the numerical representation of the composite vertices of \(g(H)\). Since the set \(\mathbb{V}(H)\) of composite vertices of a given MAG \(H\) is obtained by the cartesian product of all aspects of the MAG (as shown in Expression (1)), it follows that the number of composite vertices on a given MAG \(H\) with \(p\) aspects is  
\[n=|\mathbb{V}(H)|=\prod_{i=1}^{p}\tau_{i}, \tag{19}\]  
where \(\tau_{i}\) is the \(i\)-th element of the MAG's companion tuple, i.e., the number of elements on the MAG's \(i\)-th aspect. The general form of any entry of the matrix \(\mathbf{J}(H)\) is given by  
\[j_{\mathbf{u},\mathbf{v}}=\left\{ \begin{array}{ll}1&\text{if }(\mathbf{u}, \mathbf{v})\in E(g(H)),\\ 0&\text{otherwise},\end{array} \right. \tag{20}\]  
where \((\mathbf{u},\mathbf{v})\in E(g(H))\) means that \((\mathbf{u},\mathbf{v})\) is an edge on the composite vertices representation \(g(H)\) of the MAG \(H\), so that \(\mathbf{u},\mathbf{v}\in\mathbb{V}(H)\) are composite vertices of \(H\). It follows from the definition of \(g(H)\) and its natural isomorphism to \(H\), that \((\mathbf{u},\mathbf{v})\in E(g(H))\) if and only if there is an edge \(e\in E(H)\) such that \(\mathbf{u}=\pi_{o}(e)\) and \(\mathbf{v}=\pi_{d}(e)\). It is important to note, however, that the notation \(j_{\mathbf{u},\mathbf{v}}\) is in fact a shorthand for \(j_{D(\mathbf{u},\tau),D(\mathbf{v},\tau)}\), where \(D(\mathbf{u},\tau)\) is the row number and \(D(\mathbf{v},\tau)\) the column number of the matrix entry. This ties the construction of the adjacency matrix of a MAG with its companion tuple, since it is used in the determination of the numerical representation of a composite vertex (\(D(\mathbf{u},\tau)\)). Therefore, the adjacency matrix of any given MAG is always presented with its companion tuple. The adjacency matrix of a given MAG \(H\) is constructed by Algorithm 5, where \(|\mathbb{V}(H)|\) is the number of composite vertices in \(H\), which can be calculated using Equation (19), \(D(\pi_{o}(e),\tau)\) and \(D(\pi_{d}(e),\tau)\) are the numerical representation of the origin and destination composite vertices of edge \(e\in E(H)\), respectively, as defined in Section 3.2. ```
input :\(H=(A,E)\) output :\(\mathbf{J}(H)\), \(\tau(H)\)
1 AdjMatrix(\(H\))
2\(n\leftarrow|\mathbb{V}(H)|\) // companion tuple
3\(T\gets CompTuple(A(H))\) // companion tuple
4\(\mathbf{J}(H)\gets n\times n\) matrix with all entries = 0
5 for each \(e\in E(H)\)do
6\(\mathbf{u}\gets D(\pi_{o}(e),T)\) // numerical origin
7\(\mathbf{v}\gets D(\pi_{d}(e),T)\) // numerical destination
8\(\mathbf{J}(H)[\mathbf{u},\mathbf{v}]\gets 1\)
9
10 end for return\(\mathbf{J}(H),T\)
```  
**Algorithm 5**Building \(\mathbf{J}(H)\) from MAG \(H\). Considering that a sparse matrix with all entries 0 can be created in constant time, and that both functions \(CompTuple\) and \(D\) (see Algorithms 1 and 3) have time complexity \(O(p)\), we conclude that Algorithm 5 has time complexity \(O(p*|E(H)|)\), where \(p\) is the number of aspects of MAG \(H\) and \(|E(H)|\) the number of edges. As an example, the adjacency matrix of the MAG \(T\) is shown in Expression (21). This adjacency matrix \(\mathbf{J}(T)\in\mathbb{R}^{18\times 18}\) has 324 entries, of which just 22 are non-zero.