I am not sure whether I understood the question correctly. First of all any $2\times2$ Hermitian matrix $A$ can be written as a real linear combination of the Pauli matrices and they form the basis. To see this, notice that the inner product is given by the trace, and the coefficient $x_s$ of $\sigma_s$ will be $\mathrm{Tr}(A\cdot\sigma_s)$ where $s=0,x,y,z$.
After this you can simply use the fact that for two vector spaces $V_1,~V_2$ with basis $\{e_i\}$ and $\{f_j\}$ respectively, the tensor product $V_1\otimes V_2$ is a vector space with basis elements are given by $\{e_i\otimes f_j\}$.
Let me give a partial answer to your very interesting question. One can effectively decide whether the semigroup generated by a finite set of matrices with coefficients in $\mathbb{Z}$ (or even in $\mathbb{Q}$) is finite or not.
The reference is [1] (or [2]) and this is a nontrivial result.
It is also known that the semigroup is finite if and only if every of its elements generate a finite semigroup (that is, have finitely many distinct powers), see [4]. Note that this condition does not suffice to decide whether the semigroup is finite.
You will also find some detailed information on the corresponding problem for groups of matrices in [3].
[1] Jacob, Gérard. Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. (French) Theoret. Comput. Sci. 5 (1977/78), no. 2, 183--204.
Abstract: Let $S$ be a finite set of matrices over a commutative field $K$. We give here an algorithm which decides whether the matrix semigroup $H$ generated by $S$ is finite; and in that case, our algorithm computes the cardinality of $H$.
[2] Jacob, Gérard. La finitude des représentations linéaires des semi-groupes est décidable. (French) J. Algebra 52 (1978), no. 2, 437--459.
[3] Kuzmanovich, James and Pavlichenkov, Andrey, Finite Groups of Matrices Whose Entries Are Integers, The American Mathematical Monthly, 109, No. 2 (Feb., 2002), 173--186.
[4] McNaughton, Robert; Zalcstein, Yechezkel. The Burnside problem for semigroups. J. Algebra 34 (1975), 292--299.
Best Answer
If $M=\pmatrix{r&s\\t&u}$ is a nonsingular matrix with nonnegative integer matrices, then $AM=\pmatrix{r+t&s+u\\t&u}$ so the first row minus the second row of $AM$ is a nonnegative nonzero row vector. Similarly taking the first row minus the second row of $BM$ gives a non-positive row vector. Therefore in a product of $A$s and $B$s we can detect uniquely whether the first matrix is $A$ or $B$. Cancelling that and repeating, then we can determine uniquely the entire sequence of $A$s and $B$s.