# A Multi-Dimensional Matrix Product--A Natural Tool for Parameterized Graph Algorithms
## 1 Introduction  
Matrix multiplication over various rings or semi-rings is a basic tool in science and engineering. By the definition, the matrix product of two \(n\times n\) matrices can be easily computed using \(O(n^{3})\) additions and multiplications over the respective ring or semi-ring. This is optimal in the arithmetic case and the Boolean case if, respectively, only the operations of arithmetic addition and multiplication or the Boolean OR and AND are allowed [1, 2]. Five decades ago, [PERSON] presented a divide-and-conquer algorithm for arithmetic matrix multiplication based on algebraic term cancellation, breaking out of the \(O(n^{3})\) method. It used only \(O(n^{2.8074})\) multiplications, additions and subtractions [3]. The complexity of matrix multiplication is measured in terms of \(\omega\) which is the smallest real number such that two \(n\times n\) matrices can be multiplied using \(O(n^{\omega+\varepsilon})\) operations over the field of reals, for all \(\varepsilon>0\) (i.e., the number of operations is \(O(n^{\omega+\varepsilon(1)})\)[4]. The series of improvements of the upper bounds on \(\omega\) starting from \(\omega<2.8074\) culminates in the recent result of [PERSON] and [PERSON] showing \(\omega<2.3729\)[4]. By a straightforward reduction of the Boolean matrix product to the corresponding arithmetic one for \(0-1\) matrices, the same asymptotic upper bounds hold for the Boolean matrix product. We generalize the concept of matrix product of two matrices over a ring or semiring to include that of a \(k\)-dimensional matrix product \(D\) of \(k\) matrices \(A_{1},\ldots,A_{k}\), of sizes \(n_{1}\times n,\ldots,n_{k}\times n\), respectively, where \(D[i_{1},\ldots,i_{k}]=\sum_{\ell=1}^{n}A_{1}[i_{1},\ell]\times\ldots\times A_{k }[i_{k},\ell]\). Note that the _two_-dimensional product of the matrices \(A_{1}\) and \(A_{2}\) is equivalent to the standard matrix product of \(A_{1}\) and the transpose \((A_{2})^{T}\) of the matrix \(A_{2}\). For \(k\geq 2\), we define \(\omega_{k}(1,r)\) as the smallest real number such that the \(k\)-dimensional arithmetic product of \(k\)\(n\times n^{r}\) matrices can be computed using \(O(n^{\omega_{k}(1,r)+\epsilon})\) operations over the field of reals, for all \(\epsilon>0\). We show that \(\omega_{k}(1,r)\) does not exceed \(\omega(\lceil k/2\rceil,r,\lfloor k/2\rfloor)\), where \(\omega(p,q,r)\) stands for the smallest real number such that an \(n^{p}\times n^{q}\) matrix can be multiplied by \(n^{q}\times n^{r}\) matrix using \(O(n^{\omega(p,q,r)+\epsilon})\) operations over the field of reals for all \(\epsilon>0\). If \(A\) and \(B\) are two Boolean matrices and \(C\) is their Boolean matrix product, then for any entry \(C[i,j]=1\) of \(C\), a witness is an index \(m\) such that \(A[i,m]\wedge B[m,j]=1\). The smallest (or, largest) possible witness is called the _minimum witness_ (or, _maximum witness_, respectively). The problems of finding \"witnesses\" have been studied for several decades, mostly within stringology (e.g., algorithms for symbol matches or mismatches [5; 6]) and graph algorithms (e.g., algorithms for shortest paths [7; 8]). More recently, the problems of finding extreme (i.e., minimum or maximum) witnesses have found numerous applications (e.g., algorithms for all-pairs lowest common ancestors [9] or all-pairs bottleneck weight path problem [10]). [PERSON] and [PERSON] showed that the witness problem for the Boolean matrix product of two Boolean matrices, i.e., the problem of reporting a witness for each non-zero entry of the product, to be solvable in time required to compute the product up to polylogarithmic multiplicative factors [11]. (By the _time_ complexity of an algorithm, we mean the number of operations performed by the algorithm in the unit cost random access machine model, which is expressed as a function of an input size parameter.