Determinant of block tridiagonal matrices

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.

This is a fair example of the following theorem : let $A_{ij}in M_r(k)$ be pairwise commuting matrices for $1le i,jle d$, and let $Ain M_{dr}(k)$ be the matrix whose $rtimes r$ blocks are the $A_{ij}$'s. Then $det A$ equals the determinant of the matrix $Bin M_r(k)$ obtained by computing the formal determinant of the blocks. Example : $$detbegin{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 $2cosfrac{kpi}{N+1}$, $1le kle N$.

In particular, the eigenvalues of $J_n$ are the numbers $1+2cosfrac{jpi}{n+1},$. Hence the formula $$det A=prod_{j=1}^nP_Nleft(1+2cosfrac{jpi}{n+1}right).$$