Complementary Triangular Forms of Upper Triangular Toeplitz Matrices

The problem considered is the following. Given two upper triangular Toeplitz matrices A and Z, when does there exist an invertible matrix S such that S -1 AS is upper triangular and S -1 ZS is lower triangular ? The motivation for considering simultaneous reduction to complementary triangular forms of pairs of matrices comes from systems theory. For upper triangular Toeplitz matrices, a complete answer is given. The argument involves a detailed analysis of a certain directed graph associated with A and Z. Along the way information is obtained about the structure of the similarity S. The results actually hold for a class of matrices strictly larger than that consisting of the upper triangular Toeplitz matrices.