Characterization of discrete linear shift-invariant systems

Linear time-invariant (LTI) systems are of fundamental importance in classical digital signal processing. LTI systems are linear operators commuting with the time-shift operator. For N-periodic discrete time series the time-shift operator is a circulant N × N permutation matrix. Sandryhaila and Moura developed a linear discrete signal processing framework and corresponding tools for datasets arising from social, biological, and physical networks. In their framework, the circulant permutation matrix is replaced by a network-specific N × N matrix A, called a shift matrix, and the linear shift-invariant (LSI) systems are all N × N matrices H over C commuting with the shift matrix: HA = AH. Sandryhaila and Moura described all those H for the non-degenerate case, in which all eigenspaces of A are one-dimensional. Then the authors reduced the degenerate case to the non-degenerate one. As we show in this paper this reduction does, however, not generally hold, leaving open one gap in the proposed argument. In this paper we are able to close this gap and propose a complete characterization of all (i.e., degenerate and non-degenerate) LSI systems. Finally, we describe the corresponding spectral decompositions.