10
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Alex Meiburg Aug 21 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.