# MultiAspect Graphs: Algebraic Representation and Algorithms
## 3 Algebraic Representation
### Incidence Matrix  
Given that every MAG is isomorphic to a directed graph, it follows that it can be represented by an incidence matrix (and its companion tuple). For any given MAG \(H\), this matrix is constructed from the composite vertices \(g(H)\) and the companion tuple \(\tau(H)\), adopting the vertex sequence induced by the numerical representation presented in Section 3.2. The MAG's incidence matrix \(\mathbf{C}(H)\in\mathbb{R}^{m\times n}\), where \(m=|E(H)|\) is the number of edges in the MAG and \(n=|\mathbb{V}(H)|\) is the number of composite vertices on the MAG, is defined then as  
\[c_{e,\mathbf{u}}=\left\{\begin{array}{rl}1&\text{if }\mathbf{u}=\pi_{0}(e),\\ -1&\text{if }\mathbf{u}=\pi_{d}(e),\\ 0&\text{otherwise},\end{array}\right. \tag{26}\]  
where \(e\in E(g(H))\) is an edge in MAG \(H\) and \(\mathbf{u}\in\mathbb{V}(H)\) is a composite vertex in MAG \(H\). Here, the notation \(c_{e,\mathbf{u}}\) is a shorthand for \(c_{I_{d}(e),D(\mathbf{u},\tau)}\), where \(I_{d}(e)\) is an numerical index for each edge and \(D(\mathbf{u},\tau)\) is the numerical representation of the composite vertex \(\mathbf{u}\). Note that the use of the composite vertex numerical representation ties the incidence matrix to the MAG's companion tuple.  
Although the sequence of the composite vertices is defined by each composite vertex numerical representation, the sequence used to present the MAG edges in the incidence matrix is not relevant. The incidence matrix of a directed graph has several well-known properties [34], among which, the property that the incidence matrix of a directed graph with \(k\) connected components has rank \(n-k\), where \(n\) is the number of vertices of the graph. This property is useful for defining other matrices based on the incidence matrix.  
For a given MAG \(H\), the incidence matrix \(\mathbf{C}(H)\) is built by Algorithm 6, where \(D(\pi_{o}(e),T)\) and \(D(\pi_{d}(e),T)\) are the numerical representation of the origin and destination composite vertices of edge \(e\in E(H)\), respectively, as defined in Section 3.2, and \(I_{d}(e)\) is a unique numerical index for the edge \(e\in E(H)\), ranging from 1 to \(m\). 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 of \(O(p)\), we conclude that Algorithm 6 has time complexity of \(O(p*|E(H)|)\), where \(p\) is the number of aspects of MAG \(H\) and \(|E(H)|\) the number of edges.  
The main components incidence matrix \(\mathbf{C}(m(T))\) is depicted in Expression (30). It is obtained from the matrix \(\mathbf{C}(T)\) by removing the trivial components, as shown in Expression (28).  
\[\mathbf{C}(m(T))=\left[\begin{array}{ccccccccc}\mathbf{1}&0&0&-\mathbf{1}&0&0 &0&0&0&0&0\\ -\mathbf{1}&0&0&1&0&0&0&0&0&0&0&0\\ 0&0&0&1&0&0&-\mathbf{1}&0&0&0&0\\ 0&0&0&-\mathbf{1}&0&0&\mathbf{1}&0&0&0&0\\ 0&0&0&0&0&0&0&1&0&-\mathbf{1}\\ 0&0&0&0&0&0&-\mathbf{1}&0&0&0&0\\ 1&0&0&-\mathbf{1}&0&0&0&-\mathbf{1}&0&0&0&0\\ 0&0&1&0&0&-\mathbf{1}&0&0&0&0&0\\ 0&0&0&1&0&0&-\mathbf{1}&0&0&0&0\\ 0&0&0&0&1&0&0&-\mathbf{1}&0&0&0\\ 0&0&0&0&1&0&0&0&-\mathbf{1}&0&0\\ 0&0&0&0&0&1&0&0&-\mathbf{1}&0&0\\ 0&0&0&0&0&1&0&0&0&-\mathbf{1}\\ 1&0&0&0&-\mathbf{1}&0&0&0&0&0&0\\ 0&1&0&0&0&-\mathbf{1}&0&0&0&0&0\\ 0&0&1&0&0&0&-\mathbf{1}&0&0&0&0\\ 0&0&0&1&0&0&0&-\mathbf{1}&0&0&0\\ 0&0&0&1&0&0&0&0&-\mathbf{1}&0&0\\ 0&0&0&0&1&0&0&0&-\mathbf{1}&0&0\\ 0&0&0&0&0&1&0&0&0&-\mathbf{1}\\ \end{array}\right] \tag{30}\]  
In general, the incidence matrices related to MAGs are sparse, and therefore can be efficiently stored using sparse matrices representations, such as CSC or CSR [33]. Assuming that the number of edges on the MAG is larger than the number of composite vertices, the use of these representation lead to a memory complexity of \(O(m)\), where \(m=|E(H)|\) is the number of edges on the MAG \(H\).