Testing if two 12x12 matrices have the same determinant

An answer to this question on the Scientific Computing Stack Exchange.

Question

I am given a $12 \times 12$ matrix $Q$ that is symmetric, invertible, positive definite and dense. I need to test if $$\det(Q) = \det(12I-Q-J) ; ; (1)$$ where $J$ is the all ones matrix.

I am currently doing this with the armadillo library but it turns out to be too slow. The thing is that I need to do this for a trillion of matrices and it turns out that computing the two determinants is the bottleneck of my program. Hence I have two questions

  1. Is there any trick I could use to compute the determinant faster given that I known their size? Is perhaps a messy expansion for $12 \times12$ matrices that could work in this case?

  2. Is there any other efficient way to test the equality $(1)$

Edit. To answer the comments. I need to compute all connected non self-complementary graphs $G$ of order $13$ such that $G$ and $\overline{G}$ have the same number of spanning trees. The motivation for this can be found in this mathoverflow post. As for the machine I am running this on a 8 core 3.4GHh machine in parallel.

Edit. I was able to reduce the expected running time by 50% by making a C program for specifically computing the determinant of a $12 \times 12$ matrix. Suggestions are still welcome.

Answer

If you have a structured way of enumerating the graphs you wish to calculate the determinants of, perhaps you could find low-rank updates which transfer you from one graph to another.

If so, then you could use the matrix determinant lemma to cheaply calculate the determinant of the subsequent graph to be enumerated using your knowledge of the current graph's determinant.

That is, for a matrix $A$ and vectors $u,v$: $$\det(A+uv^T)=(1+v^T A^{-1} u)\det(A)$$ This can be generalized if U and V are $n \times m$ matrices and $A$ is $n \times n$: $$\det(A+UV^T)=\det(I_m + V^TA^{-1}U)\det(A)$$

To efficiently calculate the inverse, you can use the Sherman-Morrison formula to obtain the inverse of the subsequent matrix from the current one: $$(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1} uv^T A^{-1}}{1+v^T A^{-1} u}$$