Given a matrix in companion form over , whose characteristic polynomial is irreducible, a tridiagonal matrix, similar to the original one, is found, by constructing the similarity transformation. The theoretical basis is founded on the Lanczos tridiagonalization method, valid in the Complex domain. A variant of the Lanczos method, based on LU decomposition requirements, is modified to apply in the finite field . The work is derived from an application in VLSI design, where the matrices in companion form and in tridiagonal form represent two similar linear finite state machines, used for pseudo-random pattern generation and digital circuit testing. The construction of the similarity transformation between the matrices makes it possible to obtain directly the separate implementation of the two corresponding machines.
