# Determinant of block tridiagonal matrices

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, 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).

• 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}$. Commented Jul 31, 2015 at 10:04
• @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$? Commented Aug 2, 2015 at 16:45
• 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). Commented Aug 2, 2015 at 17:32
• Yes, for the "Lights Out" problem, one has to determine when $\det(A)$ is even. To determine when $\det(A)=0$ looks ok, but to find the parity of a product of cosines is a disaster. Commented Feb 24, 2023 at 16:44
• More difficult it seems is to find the rank of $A$ in $\mathbb{F}_2$, which is the $\log_2$ of the number of states that can be reached Commented Feb 24, 2023 at 17:10

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.
• 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. Commented Aug 2, 2015 at 16:42
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).$$
• 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})$? Commented Aug 2, 2015 at 16:43