# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 3 Multi-Dimensional Matrix Product and Its Witnesses
To prove the second part of the lemma, it is sufficient to consider Boolean versions of the matrices \(A,\ B,\ C\) and use Fact 2. By combining Lemma 1 with Fact 1, we obtain the following corollary. Corollary 1: _For even \(k\geq 8\), \(\omega_{k}=k+o(1)\)._Proof. : We obtain the following chain of equations on the asymptotic time required by the \(k\)-dimensional matrix product using Lemma 1 and Fact 1:  
\[n^{\omega(k/2,1,k/2)+o(1)}=(n^{k/2})^{\omega(1,2/k,1)+o(1)}=(n^{k/2})^{2+o(1)}=n^ {k+o(1)}.\]  
Consider the Boolean case. By the definition, the \(k\)-dimensional Boolean matrix product can be computed in time proportional to the size of the product multiplied by the size of witness range. By generalizing the column-row method for the Boolean matrix product of two Boolean matrices, we obtain an output-sensitive upper bound on the time required to compute the \(k\)-dimensional Boolean matrix product. Theorem 3.1: _Suppose \(k\geq 2\) and \(k=O(1)\). Let \(w\) be the total number of witnesses for the entries of the \(k\)-dimensional Boolean product of \(k\)\(n\times n\) Boolean matrices. The non-zero entries of the product can be listed in \(O(n^{2}+w)\) time. Consequently, they can be listed in \(O(n^{2}+sn)\) time, where \(s\) is the number of non-zero entries in the product._  
Proof. : Let \(D\) stand for the \(k\)-dimensional Boolean matrix product. For \(m=1,\ldots,k\), \(\ell=1,\ldots,n\), compute the set \(S_{m}(\ell)\) of indices \(i\) such that \(A_{m}[i,\ell]=1\). Next, for \(\ell=1,\ldots,n\), compute the Cartesian product \(S(\ell)=S_{1}(\ell)\times\ldots\times S_{k}(\ell)\). Note that \(S(\ell)\) coincides with the set of \(k\)-tuples \(i_{1},\ldots,i_{k}\) such that \(\ell\) is a witness for \(D[i_{1},\ldots,i_{k}]\). Assuming \(k=O(1)\), we can compute the sets \(S_{m}(\ell)\) in \(O(n^{2})\) time. The sets \(S(\ell)\) can be computed in \(O(w+n)\) time. On their basis, the non-negative entries of the product \(D\) can be listed in \(O(w)\) time. This proves the first part. The second part follows immediately from the fact that a non-zero entry of \(D\) can have at most \(n\) witnesses. The best known algorithm for the maximum witness problem for the two-dimensional Boolean matrix product from [9] relies on the multiplication of rectangular submatrices of the input matrices. We generalize this idea to include the maximum witness problem for the \(k\)-dimensional Boolean matrix product. First, each of the input matrices is divided into vertical strip submatrices of an appropriate width \(\leq\ell\). Then, the multi-dimensional Boolean products of the corresponding submatrices are computed in order to detect, for each positive entry of the multi-dimensional output matrix, the interval of length \(\leq\ell\) containing the maximum witness. Finally, the maximum witnesses are found separately for each of the positive entries by verifying the respective \(\leq\ell\) candidates. More details can be found in the following pseudo-code (in Algorithm 1). ```
Input: Boolean \(n\times n\) matrices \(A_{i}\), \(i\in[k]\), and a parameter \(\ell\in[n]\). Output: maximum witnesses for all non-zero entries of the \(k\)-dimensional Boolean product of the matrices \(A_{1},\ldots,A_{k}\) and \"No\" for all zero entries of the product. 1. For \(i\in[k]\), divide \(A_{i}\) into \(\lceil n/\ell\rceil\) vertical strip submatrices \(A_{i}^{1},\ldots,A_{i}^{\lceil n/\ell\rceil}\) of width \(\ell\) with the exception of the last one that can have width \(\leq\ell\). 2. for\(p\in\lceil n/\ell\rceil\) compute the \(k\)-dimensional Boolean product \(B_{p}\) of \(A_{1}^{p},\ldots,A_{k}^{p}\)
3. for all \(i_{1},\ldots,i_{k}\in[n]\)do (a) Find the largest \(p\) such that \(B_{p}[i_{1},\ldots,i_{k}]=1\) or set \(p=0\) if it does not exist.