# 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? – ulead86 Jun 1 '15 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 '15 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). – Algebraic Pavel Jun 1 '15 at 12:38
• @A.P. thank you for mentioning the paper. If I use this result, I need to compute powers of $J$. Is anything known about that? – Martin Jun 1 '15 at 13:59
• @ulead86 This matrix comes up when one tries to find solutions for the puzzle "Lights Out". – Martin Jun 1 '15 at 14:02

Assume that $A\in M_{nk,nk}$. Then let $(P_n)$ be the sequences of matrices defined as follows: $P_1=J_n,P_2={J_n}^2-I,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(vx-u, z, x); u := w end do; Digits := 1150; Q := unapply(v, x); r := 1; for i to n do r := evalf(rQ(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 '15 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? – Martin Jun 2 '15 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. – Martin Jun 4 '15 at 20:35
• The residue mod 30 has nothing to do here. – loup blanc Jun 4 '15 at 21:06