# 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 (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).

• 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}$. – Federico Poloni Jul 31 '15 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$? – Martin Aug 2 '15 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). – Federico Poloni Aug 2 '15 at 17:32

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. – Martin Aug 2 '15 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})$? – Martin Aug 2 '15 at 16:43