Определение сложности, данное для конечных автоматов, вообще говоря, может быть распространено на случай конечномерных линейных систем посредством несколько искусственной алгебраической конструкции полугруппы линейной системы. Основным недостатком такого представления является то обстоятельство, что полугрупповая «реализация» линейной системы лишь случайно может оказаться минимальной (т. е. канонической). Да это и неудивительно, так как теория Крона – Роудза дает теоремы существования для последовательно-параллельных реализаций, которые, как правило, не минимальны. Математически наиболее элегантный путь – это использовать теорию модулей, которая, как было отмечено выше, всегда приводит к минимальной реализации. Однако для этого потребуется привлечение значительного алгебраического аппарата теории модулей. Подойдем к вопросу о сложности конечномерных линейных систем с позиций полиномиальной и линейной алгебры.

Для общего обоснования вида функции сложности обратимся к рис. 3.7, изображающему общую структуру линейной системы, и теореме реализации (гл. 3). Было показано, что любая линейная динамическая система $\Sigma$ может быть представлена как прямая сумма подсистем $\Sigma_{i} ; \Sigma_{i}$ определяется $i$-м нетривиальным фактором матрицы
\[
\psi_{\mathrm{W}} W(z),
\]

где $W(z)$ – передаточная функция системы $\Sigma$, а $\psi_{w}$ – ее характеристический многочлен. Компоненты $\Sigma_{i}$ представляют неприводимые составные блоки системы $\Sigma$, поэтому определив меру сложности для каждого из них, получим меру сложности системы $\Sigma$.

Так как инвариантные факторы $\psi_{w} W(z)$ однозначно описывают структуру системы $\Sigma$, возьмем в качестве меры ее сложности
\[
\zeta(\Sigma)=\sum_{i=1}^{q}\left(n-\operatorname{deg} \psi_{i}+1\right) \log \left(n-\operatorname{deg} \psi_{i}+1\right),
\]

где $n=\operatorname{dim} \Sigma$, а $\psi_{i}-i$-й нетривиальный инвариантный фактор $\psi_{\mathrm{w}} W(z)$. Достаточно просто проверить, что мера $\xi$ удовлетворяет вышеприведенным аксиомам. При этом системой, сложность которой равна 0 , является циклическая система. Вполне закономерно, что мера $\xi$ очень похожа на меру информации, содержащейся в строке символов, так как аксиомы сложности тесно связаны с «естественными» аксиомами для меры энтропии.

Заметим, что, хотя мера $\xi$ основана на степенях $\psi_{i}$, размерность пространства состояний также играет в ней существенную роль. Например, для двух систем с подобной циклической структурой система большей размерности будет и более сложной, что отвечаёт нашему интуитивному пониманию меры $\xi$.

Рассмотрим две системы, описываемые передаточными матрицами
\[
W_{2}(z)=\left[\begin{array}{ccc}
\frac{1}{z}+\frac{1}{z^{2}} & \frac{1}{z}+\frac{1}{z^{2}} & \frac{1}{z} \\
0 & 0 & \frac{1}{z}
\end{array}\right] .
\]

Легко показать, что матрица $\psi_{w} W_{1}(z)$ имеет единственный инвариантный фактор
\[
\psi_{1}^{1}=(z+1)(z+2)(z+3) .
\]

Следовательно,
\[
\zeta\left(\Sigma_{1}\right)=0 .
\]

Матрица $\psi_{\text {w }_{2}} W_{2}(z)$ имеет два инвариантных фактора $\psi_{1}^{2}=z$, $\psi_{2}^{2}=z^{2}$. Таким образом, сложность $\varepsilon_{2}$ системы $\Sigma_{2}$ равна
\[
\begin{aligned}
\zeta\left(\Sigma_{2}\right) & =\sum_{i=1}^{2}\left(n-\operatorname{deg} \psi_{i}+1\right) \log \left(n-\operatorname{deg} \psi_{i}+1\right) \\
& =(3-1+1) \log (3-1+1)+(3-2+1) \log (3-2+1) \\
& =3 \log 3+2 \log 2 .
\end{aligned}
\]

Как и следовало ожидать, нетривиальная циклическая структура системы $\Sigma_{2}$ делает ее значительно более сложной, чем система $\Sigma_{1}$.