Determinant of block tridiagonal matrices

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

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.