On solving the Lyapunov and Stein equations for a companion matrix

When the matrix A is in companion form, the essential step in solving the Lyapunov equation PA + A^TP = −Q involves a linear n × n system for the first column of the solution matrix P. The complex dependence on the data matrices A and Q renders this system unsuitable for actual computation. In this paper we derive an equivalent system which exhibits simpler dependence on A and Q as well as improved complexity and robustness characteristics. A similar results is obtained also for the Stein equation P − A^TPA = Q.