Cross-posted from stackoverflow, where there seemed to be no interest: https://stackoverflow.com/questions/22329233/matlab-how-make-a-list-of-words-in-matrices
Given two n by n invertible matrices A and B, I'd like to create a list of all non-trivial words (multiplied out) of bounded length N in A,B, and their inverses. How would I do this in matlab?
To clarify, a word is a sequence of A,B,A^-1,B^-1 in any order, and non-trivial means that we don't have a subsequence like A,A^-1 or B^-1,B and we ignore the empty sequence. 'Multiplied out' means that I want to evaluate a sequence like A,B,A^-1 as ABA^-1, to get a matrix.
Example: The list of (multiplied out) non-trivial words of length at most 2 is
A,B,A^-1,B^-1,AA,AB,AB^-1, BA,BA^-1,BB
The non-trivial words of length 1 are $$ \mathcal{W}_1 =\left\{A,B,A^{-1},B^{-1}\right\} \text{.} $$ If $\mathcal{W}_n$ is the set of non-trivial words $\omega = \omega_1\ldots\omega_n$ of length $n$, then the set of non-trivial words of length $n+1$ is\begin{eqnarray} \mathcal{W}_{n+1} &=& \left\{\omega A \,:\, \omega \in \mathcal{W_n}, \omega_n \neq A^{-1}\right\} \\ &\cup& \left\{\omega B \,:\, \omega \in \mathcal{W_n}, \omega_n \neq B^{-1}\right\} \\ &\cup& \left\{\omega A^{-1} \,:\, \omega \in \mathcal{W_n}, \omega_n \neq A\right\} \\ &\cup& \left\{\omega B^{-1} \,:\, \omega \in \mathcal{W_n}, \omega_n \neq B\right\} \text{.} \end{eqnarray}
From that it follows that the total number of non-trivial words in of length $n+1$ is $$ \left|\mathcal{W}_{n+1}\right| = 4\left(\frac{3}{4}\left|\mathcal{W}_{n}\right|\right) = 3\left|\mathcal{W}_{n}\right| = 3^{n}\left|\mathcal{W}_{1}\right| = 4\cdot 3^n \text{.} $$
Using this, it should be pretty straight-forward to write a recursive MATLAB procedure that produces $\mathcal{W}_n$.