# Determinant of block tridiagonal Toeplitz 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$$.

• Interesting question. How did you get this kind of matrices? Jun 1, 2015 at 11:22
• You may be interested in this related paper. Otherwise, you can probably adapt the recurrence relation used to compute the determinant of tridiagonal matrices.
– A.P.
Jun 1, 2015 at 12:23
• Is $A$ an $n^2\times n^2$ matrix or is the number of blocks in $A$ somehow parameterized ($kn\times kn$)? In the first case, you can use the Kronecker product: $A=I_n\otimes K_n+K_n\otimes I_n+I_{n^2}$, where $K_n=J_n-I_n$. There is an analytic expressions for the eigenvalues of $K_n$ (Toeplitz tridiagonal matrix). Jun 1, 2015 at 12:38
• @ulead86 This matrix comes up when one tries to find solutions for the puzzle "Lights Out". Jun 1, 2015 at 14:02
• Cross-posted to MO: Determinant of block tridiagonal matrices Sep 21, 2015 at 22:13

Assume that $$A \in M_{nk,nk}$$. Then let $$(P_n)$$ be the sequences of matrices defined as follows

$$P_1=J_n, \qquad P_2={J_n}^2-I, \qquad P_q=J_nP_{q-1}-P_{q-2}$$

Then $$\det(A)=\det(P_k)$$.

EDIT. The eigenvalues of $$J_n$$ are the $$(1+2\cos(\pi \dfrac{p}{n+1})),p=1\cdots n$$; thus, if $$Q$$ is any polynomial, then we can calculate approximations of the eigenvalues of $$Q(J_n)$$, and then, an approximation of $$\det(A)$$. When we have enough significant digits, we deduce the true result -because this one is an integer-. Finally, we do not need to calculate any product of matrices. That follows calculates -using Maple- $$\det(A)$$ when $$n=k=100$$ (duration of the calculation: $$1$$"). First step. You choose Digits:=30. You see that the result has $$1076$$ digits. Second step. You choose Digits:=1150 and that works (see the sequence of zeros (or eventually of $$9$$) that appears at the end of the development of the obtained decimal number).

restart; with(LinearAlgebra):
k := 100; n := 100; d := time(); B := Matrix(n, n); for i to n do B[i, i] := 1 end do; for i to n-1 do B[i, i+1] := 1; B[i+1, i] := 1 end do;
z := CharacteristicPolynomial(B, x); u := x; v := x^2-1; for i from 3 to k do w := v; v := rem(v*x-u, z, x); u := w end do; Digits := 1150;
Q := unapply(v, x); r := 1; for i to n do r := evalf(r*Q(1+2*cos(i*Pi/(n+1)))) end do; print(r); time()-d;


$$2.44387846087090290145607732170537391377490420405227812708050615\\ 28277319341932844677382952399933460059814926416716644013099963\\ 42708968356667589737763656457680692376518632271970928028188495\\ 28837548232087652163820090152818313133799717624970641029956038\\ 21298982012250961831581518578716473316074214193004344884914447\\ 80091522565037919891219503197811771573350002012798682732589728\\ 91073456252754229360553614557394171698663316722024355474750138\\ 99058808405660398400447542745412413310559180910765198835081950\\ 16753460456828320406836683930343030087726159407318434195928328\\ 91168720495008933297278988838511004283717390785348840943983494\\ 94573265138514209244141811048121198105502888315873129747553394\\ 28745956498781145738030840450505861505489488623215771119102138\\ 24860932438498432031584839888927118146735452787049842756602723\\ 13071431049603803135820994521439844817046772204723218141987299\\ 65625418270767015593634878034477052797174424114584736827230518\\ 99846006803088990947026408309411889789175194098825709435984858\\ 82242334251648224773936990898407542151092941240200527201190067\\ 27465966535881736354100000000000000000000000000000000143203220\\ 133487059755244617410791395080\times 10^{1075}$$

• Is there a way to compute the determinant of $P_n$ if the determinants of $P_k$ are known for $1 \leq k < n$? In other words: does this give a recursive formula for $\det(A)$?
– A.P.
Jun 2, 2015 at 15:01
• This recursion is essentially the same as in the paper mentioned by A.P. So again one has to compute (sums of) powers of $J_n$. Do you know anything about these powers? Jun 2, 2015 at 16:19
• Thanks for your edit. This is a good start for me :) However, a closed formula for $\det(A)$ would be nice. (It seems, that it depends only on the residue class of $n$ modulo $30$ if $\det(A)$ is nonzero). So if anyone knows something more, i would be grateful. Jun 4, 2015 at 20:35
• The residue mod 30 has nothing to do here.
– user91684
Jun 4, 2015 at 21:06
• @Martin Sorry to disturb you. I see that $\det(A)=0$ if $n+1$ is divisible by $5$ or $6$ because $\cos \dfrac{2\pi}{5} + \cos \dfrac{4\pi}{5} = -\dfrac{1}{2}$, $\cos \dfrac{3\pi}{6} + \cos \dfrac{4\pi}{6} = -\dfrac{1}{2}$. But can $\cos\dfrac{i\pi}{n+1} + \cos\dfrac{j\pi}{n+1} = -\dfrac{1}{2}$ for any other case? I asked because I saw you claiming in the MO link that you had solved this problem :) Feb 24 at 17:03