Lomonaco and Kauffman developed a knot mosaic system to introduce a precise and workable definition of a quantum knot system. This definition is intended to represent an actual physical quantum system. A knot $$(m,n)$$ ( m , n ) -mosaic is an $$m \times n$$ m × n matrix of mosaic tiles ( $$T_0$$ T 0 through $$T_{10}$$ T 10 depicted in the introduction) representing a knot or a link by adjoining properly that is called suitably connected. $$D^{(m,n)}$$ D ( m , n ) is the total number of all knot $$(m,n)$$ ( m , n ) -mosaics. This value indicates the dimension of the Hilbert space of these quantum knot system. $$D^{(m,n)}$$ D ( m , n ) is already found for $$m,n \le 6$$ m , n ≤ 6 by the authors. In this paper, we construct an algorithm producing the precise value of $$D^{(m,n)}$$ D ( m , n ) for $$m,n \ge 2$$ m , n ≥ 2 that uses recurrence relations of state matrices that turn out to be remarkably efficient to count knot mosaics. $$\begin{aligned} D^{(m,n)} = 2 \, \Vert (X_{m-2}+O_{m-2})^{n-2} \Vert \end{aligned}$$ D ( m , n ) = 2 ‖ ( X m - 2 + O m - 2 ) n - 2 ‖ where $$2^{m-2} \times 2^{m-2}$$ 2 m - 2 × 2 m - 2 matrices $$X_{m-2}$$ X m - 2 and $$O_{m-2}$$ O m - 2 are defined by $$\begin{aligned} X_{k+1} = \begin{bmatrix} X_k&O_k \\ O_k&X_k \end{bmatrix} \ \hbox {and } \ O_{k+1} = \begin{bmatrix} O_k&X_k \\ X_k&4 \, O_k \end{bmatrix} \end{aligned}$$ X k + 1 = X k O k O k X k and O k + 1 = O k X k X k 4 O k for $$k=0,1, \cdots , m-3$$ k = 0 , 1 , ⋯ , m - 3 , with $$1 \times 1$$ 1 × 1 matrices $$X_0 = \begin{bmatrix} 1 \end{bmatrix}$$ X 0 = 1 and $$O_0 = \begin{bmatrix} 1 \end{bmatrix}$$ O 0 = 1 . Here $$\Vert N\Vert $$ ‖ N ‖ denotes the sum of all entries of a matrix $$N$$ N . For $$n=2$$ n = 2 , $$(X_{m-2}+O_{m-2})^0$$ ( X m - 2 + O m - 2 ) 0 means the identity matrix of size $$2^{m-2} \times 2^{m-2}$$ 2 m - 2 × 2 m - 2 .