Efficient calculation of the determinants of all sub-matrices produced via a sliding window 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.
 A: 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)}.
$$
