5
$\begingroup$

Is there a formula to compute the determinant of block tridiagonal matrices, when the determinants of the involved matrices are known? In particular, I am interested in the case

$A = \begin{pmatrix} J_n & I_n & 0 & \cdots & \cdots & 0 \\ I_n & J_n & I_n & 0 & \cdots & 0 \\ 0 & I_n & J_n & I_n & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & I_n & J_n & I_n \\ 0 & \cdots & \cdots & \cdots & I_n & J_n \end{pmatrix}$

where $J_n$ is the $n \times n$ tridiagonal matrix whose entries on the sub-, super- and main diagonals are all equal to $1$ and $I_n$ is identity matrix of size $n$.

I have asked this question before on MathStackExchange (see here), where a user came up with an algorithm. Nevertheless, I am interested if there is an explicit formula (or at least, if one can say in which cases the determinant is nonzero).

$\endgroup$
  • $\begingroup$ If you are studying Lights Out, as you mentioned in the linked MSE thread, probably you should be interested in the determinant in $\mathbb{F}_2$, not in $\mathbb{R}$. $\endgroup$ – Federico Poloni Jul 31 '15 at 10:04
  • $\begingroup$ @FedericoPoloni: Yes, this is true when considering the original version of Lights Out. But when considering variants (e.g. more colors), then one needs the determinant over other finite fields, therefore I am interested in the determinant in $\mathbb{R}$. Do you think it would be easier to get the determinant over $\mathbb{F}_2$? $\endgroup$ – Martin Aug 2 '15 at 16:45
  • $\begingroup$ For the determinant it is probably the same. Determining rank and eigenvalues might require a bit more of algebraic machinery, though (nothing too fancy, extensions of finite fields). $\endgroup$ – Federico Poloni Aug 2 '15 at 17:32
5
$\begingroup$

The Kronecker product idea brought up in Algebraic Pavel's comment on the original maths stack exchange question seems like a good way to approach the particular case of interest to you. Specifically, assuming $A$ is $m n \times m n$, i.e., there are $m$ block rows and columns, then $$A = J_m \otimes I_n + I_m \otimes J_n - I_{mn},$$ and the $mn$ eigenvalues of $A$ are given by $$\lambda_{ij} = \Big(1+2 \cos \frac{i \pi}{m+1}\Big) + \Big(1+2 \cos \frac{j \pi}{n+1}\Big) - 1, \qquad 1 \le i \le m, 1 \le j \le n.$$ (I used the formula for the eigenvalues of the $J$ matrices from Denis Serre's answer here.) The determinant is then $$\det A = \prod_{i=1}^m \prod_{j=1}^n \lambda_{ij}.$$ If you're only after characterizing when $A$ is singular, then you need only determine when any of the $\lambda_{ij}$ can be zero, which looks fairly straightforward.

$\endgroup$
  • $\begingroup$ First of all, sorry for the late response. Thank you for your answer, this is really helpful. I have shown for some $n$, that there are $i,j$ s.t. $\lambda_{ij}=0$ but I am not sure yet how to show that this is impossible for certain other values of $n$. Does anyone know a useful formula for the sums of two cosines? The standard formula seems to be of no help here. $\endgroup$ – Martin Aug 2 '15 at 16:42
  • $\begingroup$ I managed to solve the remaining cases now, so thanks again for your help $\endgroup$ – Martin Aug 4 '15 at 9:00
10
$\begingroup$

This is a fair example of the following theorem : let $A_{ij}\in M_r(k)$ be pairwise commuting matrices for $1\le i,j\le d$, and let $A\in M_{dr}(k)$ be the matrix whose $r\times r$ blocks are the $A_{ij}$'s. Then $\det A$ equals the determinant of the matrix $B\in M_r(k)$ obtained by computing the formal determinant of the blocks. Example : $$\det\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}=\det(A_{11}A_{22}-A_{12}A_{21}).$$ Mind that the formula is false if the blocks don't commute.

In your case, that means that $$\det A=\det P_N(J_n),$$ where $P_N(X)$ is the determinant of the tridiagonal matrix whose diagonal entries are $X$ and the sub/super-diagonal entries are ones. This is the monic polynomial whose roots are the numbers $2\cos\frac{k\pi}{N+1}$, $1\le k\le N$.

In particular, the eigenvalues of $J_n$ are the numbers $1+2\cos\frac{j\pi}{n+1}\,$. Hence the formula $$\det A=\prod_{j=1}^nP_N\left(1+2\cos\frac{j\pi}{n+1}\right).$$

$\endgroup$
  • $\begingroup$ First of all, sorry for the late response. Can anything more be said aboute the value of $P_N(1+2\cos \frac{j \pi}{n+1})$? $\endgroup$ – Martin Aug 2 '15 at 16:43

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.