General de Bruijn matrix

Thus there are both factorizations and sum decompositions for the de Bruijn matrix, all readily obtained in a way that indicates many more representations are possible, none quite as symmetrical as the ones shown. For k>2 there are additional permutation matrices which participate in the decompositions, and the blocks in the matrix U are correspondingly larger. The factored forms show that the determinant of any de Bruijn matrix is zero, but it is not difficult to obtain the entire minimal equation, which is

nor is it difficult to verify that

 

for all values of n. This is the count of loops of length n, wherein each loop is weighted by the number of nodes it contains. It must be borne in mind that all loops are counted, including the degenerate cases where the same cycle of nodes is traversed several times.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx