Structural properties of a symmetric Toeplitz matrix

In this paper, we investigate the properties of a symmetric Toeplitz matrix by studying the components of its graph. To this end, we introduce the notion of "weighted Toeplitz graph", which is a weighted graph whose adjacency matrix is a symmetric Toeplitz matrix and whose weight is the corresponding entry of the matrix. By studying the components of a weighted Toeplitz graph, we show that a Frobenius normal form of a symmetric Toeplitz matrix is a direct sum of symmetric irreducible Toeplitz matrices. We design a linear time algorithm which determines the number of blocks in a Frobenius normal form of a symmetric Toeplitz matrix. In the process of deriving results needed to design the algorithm, we contract the residue classes of a given graph to obtain a simpler graph, which is then studied using number-theoretic techniques.