# Sum of determinants of block submatrices

I have a $$2n \times 2n$$ matrix, $$M$$. I view it a block matrix, of $$n^2$$ blocks, each of shape $$2\times 2$$. Computing the determinant of $$M$$ is easy by conventional methods. I could also look at diagonal block submatrices: given a set $$S \subseteq [n]$$, I take the submatrix of all the rows in $$S$$ and columns in $$S$$.

For instance, if $$n=3$$, I have 9 blocks (each of 4 entries), $$A_{1,1}, A_{1,2} \dots A_{3,3}$$. $$S$$ could be $${1,3}$$, in which case I take the 4x4 submatrix

$$\begin{bmatrix} A_{1,1} & A_{1,3} \\ A_{3,1} & A_{3,3}\end{bmatrix}$$

There are $$2^n$$ such submatrices, and each has its own determinant. I would like to compute the sum of those determinants as efficiently as possible. (The trivial case, where $$S = \emptyset$$, naturally has a determinant of 1.) This might sound like a bold hope, but consider that if this were not a block matrix, then you can very easily compute the sum of the determinants of the diagonal submatrices:

$$\sum_{S \subseteq [n]} M_{S,S} = \det(M + I)$$

So I'm hoping that there's some way to make a good "block identity matrix" that I can carry out operations with to compute this sum. Honestly, I'd be happy with anything in polynomial time.

Proofs of hardness would also be interesting. For instance, I could believe that the problem of computing the permanent might somehow be reduced this problem, in which case it would be NP-Hard. I have several fairly different approaches that take $$2^n$$ time, so anything in even $$1.9^n$$ would be stimulating.

As no one has answered let me offer something between a comment and a non-answer.

You have the formula $$\sum_{S \subseteq [n]} M_{S,S} = \det(M + I)$$ expressing the sum of the principal minors of an $$n\times n$$ matrix $$M$$ in terms of $$\det(M+I)$$. We can generalise this a bit, replacing $$I$$ by the diagonal matrix $$\Lambda:=\text{diag}(\lambda_1,\dots,\lambda_n)$$. We will get $$\sum_{S \subseteq [n]} M_{S,S}\lambda^{S'} = \det(M + \Lambda),$$ where $$S'$$ is the complementary set of indices, and $$\lambda^{S'}$$ is the monomial $$\prod_{i\in S'}\lambda_i$$.

Now suppose we are working with block matrices, with $$M$$ being $$mn\times mn$$, the blocks being of size $$m\times m$$. [Note, I choose to do the more general case (i) to illustrate the general technique; (ii) more importantly, to make clear that the line I am pursuing probably complicates matters, although (luckily?) for $$m=2$$ it does not.]

We want to use our formula for $$\det(M+\Lambda)$$; the 'problem' is how to exclude the minors which don't arise from the given block structure. What we can do is to put $$\Lambda:=\Gamma(\gamma_1,\dots,\gamma_n)$$ where $$\Gamma(\gamma_1,\dots,\gamma_n)$$ is the block-diagonal matrix $$\text{diag}(\gamma_1 I_m,\dots, \gamma_n I_m)$$.

The terms we want to retain in our expansion of $$\det(M+\Lambda)$$ are those where either all or none of the indices $$1,2\dots,m$$ occur, and all or none of the indices $$m+1, m+2,\dots ,2m$$ occur, and so on. In other words we must look only at the terms where the power of each $$\gamma_i$$ is divisible by $$m$$.

That is we must "section" the power series (actually polynomial) $$\det(M+\Gamma(\gamma_1,\dots,\gamma_n))$$. This we can do in the old-fashioned way. (Is this baby Fourier theory?) Let $$\omega:=\text{e}^{2\pi\text{i}/n}$$. Then the terms of interest are got by averaging the various $$\det(M+\Gamma(\gamma_1 \omega^{r_1},\dots,\gamma_n \omega^{r_n}))$$.

To be precise we have that the sum of the interesting principal minors is $$\frac{1}{m^n} \sum_{r_1=0}^{m-1}\dots\sum_{r_n=0}^{m-1} \det(M+\Gamma(\omega^{r_1},\dots,\omega^{r_n})).$$

For $$m=1$$ this just recovers the original formula. For $$m=2$$ it gives an expression in terms of $$2^n$$ determinants, so it is no improvement. For larger $$m$$ it does seem to make things worse, although the expression seems to me of theoretical interest.

• The Fourier perspective is nice. I had thought about a vaguely similar idea (for just the $m=2$ case) involving some funky stuff with vectors, but hadn't pursued it much because it was still $2^n$. The Fourier sums though are definitely more nice of a presentation, and shows how it generalizes nicely. Makes me wonder if I could get a good approximation by sampling random sets of r_i's, in e.g. an epsilon net. – Alex Meiburg Aug 21 '19 at 23:25