  Trellises provide a graphical representation for the row space of a matrix.
The product construction of Kschischang and Sorokine builds minimal
conventional trellises from matrices in minimal span form. Koetter and Vardy
showed that minimal tail-biting trellises can be obtained by applying the
product construction to submatrices of a characteristic matrix.
  We introduce the unique reduced minimal span form of a matrix and we obtain
an expression for the unique reduced characteristic matrix. Among new
properties of characteristic matrices we prove that characteristic matrices are
in duality if and only if they have orthogonal column spaces, and that the
transpose of a characteristic matrix is again a characteristic matrix if and
only if the characteristic matrix is reduced. These properties have clear
interpretations for the unwrapped unit memory convolutional code of a
tail-biting trellis, they explain the duality for the class of Koetter and
Vardy trellises, and they give a natural relation between the characteristic
matrix based Koetter-Vardy construction and the displacement matrix based
Nori-Shankar construction.
  For a pair of reduced characteristic matrices in duality, one is
lexicographically first in a forward direction and the other is
lexicographically first in the reverse direction. This confirms a conjecture by
Koetter and Vardy after taking into account the different directions for the
lexicographical ordering.
