The trivial example is
$$
\pmatrix{0 & 0 \\ 0 & 0}.
$$
Or you could consider:
$$
\pmatrix{1 & 1 \\ 1 & 1} \quad\text{or} \quad\pmatrix{1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1}.
$$
Otherwise if you only want non-zero entries of the diagonals, then how about
$$
\pmatrix{1 & a & 0 \\ a & 1 & a \\ 0 & a & 1}
$$
where $a = \frac{1}{\sqrt{2}}$.
Since you ask, I don't know if this might work, but try to consider
$$
\pmatrix{1 & a & 0 & 0\\ a & 1 & a & 0\\ 0 & a & 1& a \\ 0 & 0 & a & 1}
$$
and find the determinant of this matrix. This will be an expression in $a$. Can this ever equal zero? If this doesn't work, maybe this will give you an idea to something that would.
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}$
Best Answer
Use Laplace expansion with respect to the first row we have
$$\begin{aligned} A_{n} &= \det\begin{bmatrix} 2 & 1 & 0 & \cdots & 0 \\ 3 & 2 & 1 & \cdots & 0 \\ 0 & 3 & \ddots & \ddots & \vdots \\ \vdots& \vdots & \ddots & \ddots & 1 \\ 0 & 0 & \cdots & 3 & 2 \end{bmatrix} \\ &=2A_{n-1} - \det\begin{bmatrix} 3 & 1 & \cdots & 0 \\ 0 & 2 & \cdots & 0 \\ \vdots& \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & 2 \end{bmatrix} \\ &=2A_{n-1}-3A_{n-2}.\\ \end{aligned}$$