Efficient calculation of the determinants of all sub-matrices produced via a sliding window

Question

Suppose we have a $64 \times 127$ matrix $A$ and a $64 \times 64$ window $B$ sliding on matrix $A$. Note that there are $64$ sub-matrices. How to calculate the determinant of all sub-matrices with the fewest computation steps?

A naive approach would be to compute all determinants from scratch, complexity is $n \, m^3$, where $n$ is the number of matrices and $m$ is the size.

Answer 1

We could go from the determinant of one window to the determinant of the next using a rank-1 update and the matrix determinant lemma.

Let $v_1,v_2,\dots,v_{64}$ denote the columns of the first window $B_1$, and let $v_{65}$ denote the first column of $A$ outside the window $B$. We note that $$ \det B_2 = \det \pmatrix{v_2 & v_3 & \cdots & v_{64} & v_{65}} = \\ (-1)^{64 - 1} \det \pmatrix{v_{65} & v_2 & v_3 & \cdots & v_{64}} = \\ (-1)^{64 - 1} \det \left[\pmatrix{v_{65} - v_1 & 0&0& \cdots & 0} + \pmatrix{v_{1} & v_2 & v_3 & \cdots & v_{64}}\right] = \\ - \det[(v_{65} - v_1)e_1^T + B_1], $$ where $e_1^T = (1 \ \ 0 \ \ \cdots \ \ 0)$. By the matrix determinant lemma, this means that $$ \det(B_2) = -(1 + e_1^TB_1^{-1}(v_{65} - v_1)) \det(B_1). $$

---

We might be able to make things more efficient still if, instead of computing $B_k^{-1}(v_{k+m} - v_k)$ or $e_1^TB_k^{-1}$ directly each time, we use a rank-1 update formula for this as well. Let $P$ denote the permutation matrix $$ P = \pmatrix{&&&1\\1\\&\ddots\\&&1}. $$ We find that $$ B_{k+1} = [(v_{k+m} - v_k)e_1^T + B_k]P \implies B_{k+1}^{-1} = P^T[B_k + (v_{k+m} - v_k)e_1^T]^{-1}. $$ By the Sherman Morrison formula, we have $$ [B_k + (v_{k+m} - v_k)e_1^T]^{-1} = B_k^{-1} - \frac{B_k^{-1}(v_{k+m} - v_k)e_1^TB_k^{-1}}{1 + e_1^TB_k^{-1}(v_{k+m} - v_k)}. $$