# MultiAspect Graphs: Algebraic Representation and Algorithms
## 4 MAG Algorithms
### Auxiliary Matrices and Vectors  
When operating upon a matrix representation, a few auxiliary matrices and vectors are necessary to express the desired operations. We now define these vectors, which are used on the remainder of this section. We denote \(\mathbf{0}\) and \(\mathbf{1}\) the column vectors with all entries equal to \(0\) and \(1\), respectively. In all cases, we assume the vectors have the dimension necessary for the operation where they are applied. When necessary to improve readability, we indicate the dimension by a sub-script as in \(\mathbf{0}_{n}\) or \(\mathbf{1}_{n}\). Moreover, specially constructed matrices are used to build sub-determined algebraic algorithms for MAGs. These matrices provide reduction/aggregation operations needed for sub-determined algorithms. Although these matrices are specially constructed for the MAG and the sub-determination in question, they have distinct properties and can be constructed by a general algorithm. In fact, the construction of sub-determined algorithms relies on the use of functions to aggregate/reduce results according to the applied sub-determination. In some cases, this function can be as simple as just summing up values obtained in composite vertices, which are reduced to the same sub-determined vertex. However, depending on the algorithm being constructed, this aggregation may need a more elaborate function, which may not be expressed in terms of matrix multiplications. Given a MAG \(H\) and a sub-determination \(\zeta\), the sub-determination matrix \(\mathbf{M}_{\zeta}(H)\in\mathbb{R}^{n_{\zeta}\times n}\) is a rectangular matrix, where \(n=|\mathbb{V}(H)|\) is the number of composite vertices of \(H\) and \(n_{\zeta}=|\mathbb{V}_{\zeta}(H)|\) is the number of composite vertices of the sub-determination \(\zeta\) applied to the MAG \(H\). Since a sub-determination is a (proper) subset of the aspects of a MAG, it follows that \(n_{\zeta}\mid n\), i.e., the number of composite vertices of a MAG is a multiple of the number of composite vertices in any of its sub-determinations. Further, \(\mathbf{M}_{\zeta}(H)\) has the property of having exactly one non-zero entry in each column, and the position of this entry is determined by the numerical value of the sub-determined composite vertex. Algorithm 7 shows the construction of the sub-determination matrix \(\mathbf{M}_{\zeta}(H)\) for a given MAG \(H\) and sub-determination \(\zeta\). The function \(D\) takes a composite vertex to its numerical representation and the function \(S_{\zeta}\) takes a composite vertex to its sub-determined form, i.e., it drops the aspects not present in the sub-determination. To determine the time complexity of Algorithm 7, we consider that the count of composite vertices in line 3 is \(O(|\mathbb{V}(H)|)\), the same is the case for the count on line 4, the construction of companion tuple at line 2 is \(O(p)\), the construction of an empty sparse matrix at line 5 is \(O(1)\), and, finally, the **for** loop initiated at line 6 is also \(O(|\mathbb{V}(H)|)\). Since the number of aspects \(p\ll|\mathbb{V}(H)|\), we conclude that the time complexity of Algorithm 7 is \(O(|\mathbb{V}(H)|)\). ```
input :\(\tau(H)\) and \(\zeta\) output :M\({}_{\zeta}(H)\)
1 SubDetMatrix(\(\tau(H)\), \(\zeta\))
2\(T_{\zeta}=SubCompTuple(\tau(H),\zeta)\)// \(\zeta\) sub-determined companion tuple
3\(n\leftarrow|\mathbb{V}(H)|\)
4\(z\leftarrow|\mathbb{V}_{\zeta}(H)|\)
5\(\mathbf{M}_{\zeta}(H)\gets z\times n\) sparse matrix
6 for\(j\gets 1\)to\(n\)do// numeric tuple form of j
7\(i\gets D(\mathbf{u},T_{\zeta})\)// sub-determined numerical representation
8\(\mathbf{M}_{\zeta}(H)[i,j]\gets 1\)
9 end for
10 return\(\mathbf{M}_{\zeta}(H)\)
```  
**Algorithm 7**Construction of \(\mathbf{M}_{\zeta}\). For instance, consider the example MAG \(T\) and a sub-determination \(\zeta_{t}=011_{2}\), which drops the third aspect of \(T\). The aspect dropped is the aspect of time instants and, therefore, the two aspects present in \(\zeta_{t}\) are location and transit layers.