# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 3 Multi-Dimensional Matrix Product and Its Witnesses  
For the convenience of the reader, we gather all the definitions related to the multi-dimensional matrix product, repeating some of them, below. Definition 1: For \(k\)\(n_{q}\times n\) matrices \(A_{q}\), \(q=1,\ldots,k\), (arithmetic or Boolean, respectively), their \(k\)-dimensional (arithmetic or Boolean, respectively) matrix product \(D\) is defined by  
\[D[i_{1},i_{2},\ldots,i_{k}]=\sum_{\ell=1}^{n}A_{1}[i_{1},\ell]\times A_{2}[i_ {2},\ell]\times\ldots\times A_{k}[i_{k},\ell]\text{ or }\]  
\[D[i_{1},i_{2},\ldots,i_{k}]=\bigvee_{\ell=1}^{n}A_{1}[i_{1},\ell]\wedge A_{2}[ i_{2},\ell]\wedge\ldots\wedge A_{k}[i_{k},\ell],\]  
respectively, where \(i_{q}\in[n_{q}]\) for \(q=1,\ldots,k\). In the arithmetic case, \(\omega_{k}(r_{1},r_{2})\) denotes the smallest real number such that the \(k\)-dimensional arithmetic product of \(k\)\(n^{r_{1}}\times n^{r_{2}}\) matrices can be computed using \(O(n^{\omega_{k}(1,r)+\varepsilon})\) operations over the field of reals, for all \(\varepsilon>0\). For convenience, \(\omega_{k}\) stands for \(\omega_{k}(1,1)\). In the Boolean case, the corresponding numbers are denoted by \(\omega_{k}^{B}(r_{1},r_{2})\) and \(\omega_{k}^{B}\), respectively. Clearly, we have \(\omega_{k}^{B}(r_{1},r_{2})\leq\omega_{k}(r_{1},r_{2})\) and \(\omega_{k}^{B}\leq\omega_{k}\). A witness for a non-zero entry \(D[i_{1},i_{2},\ldots,i_{k}]\) of the \(k\)-dimensional Boolean matrix product is any index \(\ell\in[n]\) such that \(A_{1}[i_{1},\ell]\wedge A_{2}[i_{2},\ell]\wedge\ldots\wedge A_{k}[i_{k},\ell]\) is equal to (Boolean) \(1\). The witness problem for the \(k\)-dimensional Boolean matrix product is to report a witness for each non-zero entry of the product. The maximum witness problem for the \(k\)-dimensional Boolean matrix product is to report the maximum witness for each non-zero entry of the product. Note that in particular, the _two_-dimensional matrix product of the matrices \(A_{1}\) and \(A_{2}\) coincides with the standard matrix product of \(A_{1}\) and \((A_{2})^{T}\) which yields \(\omega_{2}=\omega\). The following lemma provides an upper bound on the time complexity of the multi-dimensional matrix product in terms of those for rectangular matrix multiplication. Lemma 1: _Let \(k,k_{1},k_{2}\) be three positive integers such that \(k=k_{1}+k_{2}\). Both in the arithmetic and Boolean case, the \(k\)-dimensional matrix product of \(k\)\(n\times n^{r}\) matrices can be computed using \(O(n^{\omega(k_{1},r,k_{2})+o(1)})\) arithmetic operations, consequently \(\omega_{k}\leq\omega(k_{1},1,k_{2})\). In addition, in the Boolean case, the witness problem for the \(k\)-dimensional matrix product can be solved in \(O(n^{\omega(k_{1},r,k_{2})+o(1)})\) time._  
Proof: To prove the first part, it is sufficient to consider the arithmetic case as the Boolean one trivially reduces to it. Let \(A_{1},\ldots,A_{k}\) be the input matrices. Form an \(n^{k_{1}}\times n^{r}\) matrix \(A\) whose rows are indexed by \(k_{1}\)-tuples of indices in \([n]\) and whose columns are indexed by indices in \([n^{r}]\) such that \(A[i_{1},\ldots i_{k_{1}},\ell]=A_{1}[i_{1},\ell]\times\ldots\times A_{k_{1}}[ i_{k_{1}},\ell]\). Similarly, form an \(n^{k_{2}}\times n^{r}\) matrix \(B\) whose rows are indexed by \(k_{2}\)-tuples of indices in \([n]\) and whose columns are indexed by indices in \([n^{r}]\) such that \(B[j_{1},\ldots j_{k_{2}},\ell]=A_{k_{1}+1}[j_{1},\ell]\times\ldots\times A_{k }[j_{k_{2}},\ell]\). Compute the rectangular matrix product \(C\) of the matrix \(A\) with the matrix \(B^{T}\). By the definitions, the \(D[i_{1},\ldots,i_{k_{1}},i_{k_{1}+1},\ldots,i_{k}]\) entry of the \(k\)-dimensional product of the input matrices \(A_{1},\ldots,A_{k}\) is equal to the entry \(C[i_{1},\ldots,i_{k_{1}},i_{k_{1}+1},\ldots,i_{k}]\). The matrices \(A,\ B\) can be formed in \(O(n^{k_{1}+r}+n^{k_{2}+r})\) time, i.e., \(O(n^{\max(k_{1}+r,k_{2}+r)})\) time, while the product \(C\) can be computed in \(O(n^{\omega(k_{1},r,k_{2})+o(1)})\) time.