# MultiAspect Graphs: Algebraic Representation and Algorithms
## 3 Algebraic Representation
### Companion Tuple  
Although we show that every MAG \(H\) is isomorphic to a directed graph designated \(g(H)\), it is important to note that the set of vertices of this graph is \(\mathbb{V}(H)\), as shown in Expression (6). Since the set \(\mathbb{V}(H)\) is the cartesian product of all the aspects in the MAG \(H\), it is possible to reconstruct the MAG's aspect list from \(\mathbb{V}(H)\), which is a step necessary to obtain the MAG \(H\) from the directed graph \(g(H)\). When the vertices of the directed graph \(G\) associated with a given MAG \(H\) are not the composite vertices themselves, it is necessary to provide a mechanism to link each vertex of the directed graph to its corresponding composite vertex on the MAG. This mechanism can be, for instance, a bijective function between \(\mathbb{V}(H)\) and \(V(G)\). In the current work, we construct representations for \(g(H)\), such as matrices, which do not directly carry the tuples that characterize the MAG's composite vertices. In this kind of representation, a vertex is associated with a row or column of a matrix. Therefore, additional information has to be provided to properly link each row (column) of a matrix to its corresponding composite vertex on the MAG represented by this matrix. This is done by a bijective function \(D\), defined in Section 3.2, where \(D\) takes a composite vertex to a natural number, which is the row (column) number in the matrix. The implementation of \(D\) presented in this work is based on the concept of a _companion tuple_, which complements the matrix representation of a given MAG. For a MAG \(H\) with \(p\) aspects, its companion tuple has the form \((|A(H)[1]|,|A(H)[2]|,\ldots,|A(H)[p]|)\), so that the number of elements on it equals the order of \(H\) and each element represents the number of elements of an aspect of \(H\). As a matter of notation, we represent the companion tuple of a given MAG \(H\) as  
\[\tau(H)=(|A(H)[1]|,|A(H)[2]|,\ldots,|A(H)[p]|), \tag{13}\]  
where \(p\) is the order of \(H\). When there is no ambiguity in relation to which MAG we are referring to, we may use the notation \(\tau\) instead of \(\tau(H)\). For instance, the companion tuple of the MAG \(T\) shown in Figure 2 is \(\tau(T)=(3,2,3)\), since \(T\) has 3 aspects, of which the first has 3 elements, the second 2 elements, and the third 3 elements. Algorithm 1 shows the building of the companion tuple for a given MAG \(H\). Assuming that the size of the aspect list \(A(H)\) and the size of each of the aspect sets contained in \(A(H)\) are known from the computational representation of \(A(H)\), the time complexity for building the companion tuple is \(O(p)\), where \(p\) is the number of aspects on MAG \(H\). If, however, these sizes are unknown, then the time complexity is \(O(s)\), where \(s=\sum_{i=1}^{p}|A(H)[i]|\), since each element of each aspect has to be counted. We remark that, in either case, the time complexity for building the companion tuple is less than \(O(\mathbb{V}(H))\), which is the cardinality of the set of composite vertices of the MAG. ```
input :\(A(H)\) output :\(\tau(H)\)
1 CompTuple(\(A(H)\))
2\(p\leftarrow|A(H)|\)// number of aspects in the MAG
3 for\(i\gets 1\)to\(p\)do
4\(T[i]\leftarrow|A(H)[i]|\)// number of elements in \(i\)-th aspect
5 end for
6 return\(T\)
```  
**Algorithm 1**Construction of the companion tuple of a MAG. For a given MAG \(H\) and a sub-determination \(\zeta\), we also define the sub-determined companion tuple \(\tau_{\zeta}(H)\), which is obtained by multiplying each entry of the original companion tuple by the equivalent entry of the tuple representation of \(\zeta\), as shown in Algorithm 2. The sub-determined companion tuple has the same value as the original companion tuple for the aspects that have value 1 in \(\zeta\) and 0 otherwise.