# Using Graph-Aware Reinforcement Learning to Identify Winning Strategies in
Diplomacy Games (Student Abstract)

Hansin Ahuja1, Lynnette Hui Xian Ng2, Kokil Jaidka3

###### Abstract

This abstract proposes an approach towards goal-oriented modeling of the
detection and modeling complex social phenomena in multiparty discourse in an
online political strategy game. We developed a two-tier approach that first
encodes sociolinguistic behavior as linguistic features then use reinforcement
learning to estimate the advantage afforded to any player. In the first tier,
sociolinguistic behavior, such as Friendship and Reasoning, that speakers use
to influence others are encoded as linguistic features to identify the
persuasive strategies applied by each player in simultaneous two-party
dialogues. In the second tier, a reinforcement learning approach is used to
estimate a graph-aware reward function to quantify the advantage afforded to
each player based on their standing in this multiparty setup. We apply this
technique to the game Diplomacy, using a dataset comprising of over 15,000
messages exchanged between 78 users. Our graph-aware approach shows robust
performance compared to a context-agnostic setup.

## Introduction

In an increasingly connected world, communication for personal, entertainment
and professional reasons is increasingly online. However, most research on
online communication has focused on personal and professional contexts, while
online coordination in game-based contexts is less understood. For example, in
multiparty online games, players interact through textual, audio, and visual
signals to coordinate game strategies aimed at ultimate victory. This is
partly due to the lack of multimodal datasets to examine the dynamic social
processes at play.

In this work, we study optimal strategies that interlocutors may employ to
maximize chances of success, in a deliberate effort to best other people. This
paper examines a recent dataset (Peskov et. al 2020) collected from
interacting players during ongoing games of Diplomacy, a political strategy
game, as it was played online.

## Approach

We adopt a two-tier methodology in predicting the winner of a Diplomacy chat
thread. First, we relied on sociolinguistic cues from words and word features
to infer persuasive strategies such as Friendship and Reasoning. Next, a
reinforcement learning approach was used to construct a graph-aware reward
function that considers the in-game dynamic between two players and the
interplay of players in a more extensive multiparty setup.

Dataset: The CL-Aff Diplomacy dataset (Jaidka et al. 2021) comprises
additional labels to the Diplomacy dataset (Peskov et. al 2020) identifying
the rhetorical strategies used by the players in their chat messages. The
dataset included four annotated labels about the rhetorical strategies
followed by the players (Friendship, Reasoning, Game Move, and Share
Information), which had a pairwise inter-annotator agreement of at least 60%.
Rather than utterance-level deception, our paper is interested in examining
whether signals of influence and persuasion applied in the game’s early stages
predict ultimate victory.

### Weakly Supervised Labeling of Player Strategies

The first step involved identifying the action space for the players in the
Diplomacy games in terms of the rhetorical strategies that they follow to
influence and persuade each other. However, only 60% of the CL-Aff Diplomacy
dataset had high-quality labeled data. Hence, a weakly supervised approach was
followed to predict the rhetorical strategies for the entire dataset. The
training set comprising the labels from CL-Aff Diplomacy was used to train
binary classifiers on the different rhetorical strategies, such as Friendship
(F), Reasoning (R), Game Move (GM), and Share Information (SI). The best-
performing classifiers (reported in Table 1) were used to predict labels for
the entire dataset.111More results can be found at
https://tinyurl.com/diplomacy-rl/

### Score-Based Inverse Reinforcement Learning

In the second step, we identified the winning player in each conversation as a
function of their rhetorical strategies. We formulate this as an inverse RL
problem and, more specifically, use score-based inverse reinforcement learning
(SBIRL) (El Asri et al. 2016), which allows us to exploit the experiences of
non-expert agents as well.

Each state $s$ of the state space $S$ is encoded using
$\phi:S\rightarrow\mathbb{R}^{d}$. The encoding is done by picking a set of
characteristic features corresponding to that state. Simpler
operationalizations rely only on the player’s score at any given point. On the
other hand, a graph-aware operationalization incorporated the player’s
importance and influence in the textual communication network for the game
through several centrality features. For the reward function, a linear
parameterization was adopted: $r_{\theta}(s)=\theta^{\intercal}\phi(s)$ where
$\theta$ is the set of parameters. Each thread $t$ of conversation is
represented as:

$t=(s_{0},\dots,s_{T})=(s_{j})_{j=0}^{T}$

We extracted the thread-level tuples $(t_{i},f_{i})$, where $t_{i}$ is the
subsequence of states corresponding to the $i^{th}$ player (referred to as a
subthread) and $f_{i}$ is the final score of the $i^{th}$ player at the end of
the thread. For any given subthread and reward, the discounted sum of rewards
can be written as

$\sum_{t=0}^{T}\gamma^{t}r_{\theta}(s_{t})=\theta^{\intercal}\mu(h)\ \
\textrm{with}\ \ \mu(h)=\sum_{t=0}^{T}\gamma^{t}\phi(s_{t})$

Where $\gamma$ is the discounting factor. We regress the final scores $f_{i}$
on the mappings $\mu(h_{i})$ and asymptotically minimise the risk based on the
$\ell_{2}$-loss. A reward function estimator $r_{\theta_{n}}$ is derived after
estimating $\theta_{n}$ by solving:

$\theta_{n}=\operatorname*{argmin}_{\theta\in\mathbb{R}^{d}}\frac{1}{n}\sum_{i=1}^{n}(f_{i}-\theta^{\intercal}\mu(h_{i}))^{2}$

## Preliminary Results

### Weakly Supervised Labeling of Player Strategies

Once the annotation labels were obtained, key player strategies were
identified. At the player level, Reasoning (R), Game move (GM), and Share
Information (SI) all shared a strong pairwise Pearson correlation
($r\in(0.45,0.55)$), while each were strongly anti-correlated with Friendship
(F) ($r\in(\textrm{-}0.61,\textrm{-}0.45)$), both with $p<0.001$. This
suggests that players either acted on a Friendship or a Reasoning strategy and
enabled us to label each utterance as an action under assumptions of mutual
exclusion. When both labels were present, a voting mechanism with the Game
move and Share Information was used to determine the ultimate label.

| F | R | GM | SI
---|---|---|---|---
Logistic regression | 0.633 | 0.508 | 0.695 | 0.541
Gaussian NB | 0.467 | 0.533 | 0.620 | 0.315
Adaboost | 0.642 | 0.448 | 0.696 | 0.623
Gradient boosting | 0.641 | 0.445 | 0.698 | 0.611
C-SVC | 0.673 | 0.526 | 0.692 | 0.570
Table 1: Macro-F1 scores for feature estimators

### Efficacy of the Reward Function

The winner of a chat thread is the player with the higher score at the end of
the thread. The accuracy of the reward function is the fraction of times when
the average estimated reward for the winner was greater than that of the
loser.

First, we encoded only the difference between the game scores of the two
players in our state feature vector. Next, given that each player is engaged
in multiple conversations at the same time, we introduced multiple graph
centrality features, such as authority score and eigen centrality, into the
state representation222Calculated using igraph, https://igraph.org/r/. The
results are reported in Table 2. We note that our graph-aware approach
outperforms the context-agnostic approach, which relies solely on
sociolinguistic cues and ignores interplay between players across multiple
threads. Additionally, we restrict each player to their first $n$ utterances
and perform the same exercise. Fig. 1 shows that the graph-aware approach
achieves modest accuracy with the very first half dozen chat messages.

Approach | Accuracy
---|---
SBIRL | 0.71
Graph-aware SBIRL | 0.79
Table 2: Reward function accuracy, defined as the fraction of times the winner
had a greater average estimated reward Figure 1: Accuracies with number of
utterances restricted

## Conclusion and Future Work

The SBIRL approach shows promising results; however, the environment lacks
counterfactuals. Judging any one action is difficult because the player never
chose the alternate action at that specific point in time, thus making agent-
focussed testing difficult. In future experiments, we will explore:

  * •

Complex, non-linear reward function estimators.

  * •

Bootstrapping the dataset to generate counterfactual data, allowing us to
build and test well-defined agents.

## References

  * El Asri et al. (2016) El Asri, L.; Piot, B.; Geist, M.; Laroche, R.; and Pietquin, O. 2016.  Score-based inverse reinforcement learning.  In _International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016)_.
  * Jaidka et al. (2021) Jaidka, K.; Chhaya, N.; Lyle, U.; Healey, J.; and Sinha, A. 2021.  Editorial for the 4th AAAI-21 Workshop on Affective Content Analysis.  In _Proceedings of the AAAI-21 Workshop on Affective Content Analysis_. New York, USA: AAAI.
  * Peskov et. al (2020) Peskov et. al, D. 2020.  It Takes Two to Lie: One to Lie, and One to Listen.  In _Proceedings of ACL_.

See pages 1- of aaai22-diplomacy-supplementary.pdf


# Linearizations of matrix polynomials viewed as
Rosenbrock’s system matrices

Froilán M. Dopico111Supported by grant PID2019-106362GB-I00 funded by
MCIN/AEI/ 10.13039/501100011033 and by the Madrid Government (Comunidad de
Madrid-Spain) under the Multiannual Agreement with UC3M in the line of
Excellence of University Professors (EPUC3M23), and in the context of the V
PRICIT (Regional Programme of Research and Technological Innovation).
<EMAIL_ADDRESS>Silvia Marcaida222Supported by grant PID2021-124827NB-I00
funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF A way of making Europe”
by the “European Union”, and by grant GIU21/020 funded by UPV/EHU.
<EMAIL_ADDRESS>María C. Quintana333Supported by an Academy of Finland
grant (Suomen Akatemian päätös 331230) and by the Agencia Estatal de
Investigación of Spain through grant PID2019-106362GB-I00 MCIN/
AEI/10.13039/501100011033/<EMAIL_ADDRESS>Paul Van
Dooren.444Supported by an Aalto Science Institute Visitor Programme
<EMAIL_ADDRESS>Departamento de Matemáticas, Universidad Carlos
III de Madrid, Avda. Universidad 30, 28911 Leganés, Spain.  Departamento de
Matemáticas, Universidad del País Vasco UPV/EHU, Apdo. Correos 644, Bilbao
48080, Spain.  Aalto University, Department of Mathematics and Systems
Analysis, P.O. Box 11100, FI-00076, Aalto, Finland.  Department of
Mathematical Engineering, Université catholique de Louvain, Avenue Georges
Lemaître 4, B-1348 Louvain-la-Neuve, Belgium.

###### Abstract

A well known method to solve the Polynomial Eigenvalue Problem (PEP) is via
linearization. That is, transforming the PEP into a generalized linear
eigenvalue problem with the same spectral information and solving such linear
problem with some of the eigenvalue algorithms available in the literature.
Linearizations of matrix polynomials are usually defined using unimodular
transformations. In this paper we establish a connection between the standard
definition of linearization for matrix polynomials introduced by Gohberg,
Lancaster and Rodman and the notion of polynomial system matrix introduced by
Rosenbrock. This connection gives new techniques to show that a matrix pencil
is a linearization of the corresponding matrix polynomial arising in a PEP.

###### keywords:

polynomial matrix , polynomial eigenvalue problem , linearization , polynomial
system matrix AMS subject classifications: 15A22, 15A54, 93B18, 93C05

##  1 Introduction

Let $\mathbb{F}$ be an arbitrary field, and let $\overline{\mathbb{F}}$ be the
algebraic closure of $\mathbb{F}$. $\mathbb{F}[\lambda]$ denotes the ring of
polynomials with coefficients in $\mathbb{F},$ and $\mathbb{F}(\lambda)$ the
field of rational functions over $\mathbb{F}[\lambda]$. The sets of $p\times
m$ matrices with elements in $\mathbb{F},$ $\mathbb{F}[\lambda]$ and
$\mathbb{F}(\lambda)$ are denoted by $\mathbb{F}^{p\times m}$,
$\mathbb{F}[\lambda]^{p\times m}$ and $\mathbb{F}(\lambda)^{p\times m}$,
respectively. The elements of $\mathbb{F}[\lambda]^{p\times m}$ are called
matrix polynomials or polynomial matrices, and the elements of
$\mathbb{F}(\lambda)^{p\times m}$ are called rational matrices.

A polynomial matrix $P(\lambda)\in\mathbb{F}[\lambda]^{p\times m}$ can always
be written in the form

$P(\lambda)=P_{k}\lambda^{k}+P_{k-1}\lambda^{k-1}+\cdots+P_{1}\lambda+P_{0},$
(1)

where $P_{k},\ldots,P_{1},P_{0}\in\mathbb{F}^{p\times m}$ with $P_{k}\neq 0$.
The scalar $k$ is then called the degree of $P(\lambda)$, and it is denoted by
$\deg P(\lambda)$. Polynomial matrices of degree $1$ or $0$, i.e., linear
polynomial matrices, are called pencils.

The (finite) eigenvalues of a polynomial matrix
$P(\lambda)\in\mathbb{F}[\lambda]^{p\times m}$ are defined as the scalars
$\lambda_{0}\in\overline{\mathbb{F}}$ such that

$\mathop{\rm rank}\nolimits
P(\lambda_{0})<\displaystyle\max_{\mu\in\overline{\mathbb{F}}}\mathop{\rm
rank}\nolimits P(\mu).$

The Polynomial Eigenvalue Problem (PEP) consists of finding the eigenvalues of
$P(\lambda).$ If $P(\lambda)\in\mathbb{F}[\lambda]^{m\times m}$ is regular
(i.e., square with $\det P(\lambda)\not\equiv 0$), the PEP is equivalent to
the problem of finding scalars $\lambda_{0}\in\overline{\mathbb{F}}$ such that
there exist nonzero constant vectors $x\in\overline{\mathbb{F}}^{m\times 1}$
and $y\in\overline{\mathbb{F}}^{m\times 1}$ satisfying

$P(\lambda_{0})x=0\quad\mbox{and}\quad y^{T}P(\lambda_{0})=0,$

respectively. The vectors $x$ are called right eigenvectors associated with
$\lambda_{0}$, and the vectors $y$ are called left eigenvectors associated
with $\lambda_{0}$.

To solve the PEP and to develop a theory of regular polynomial matrices,
Gohberg, Lancaster and Rodman [24] introduced in the eighties the notion of
linearization of a matrix polynomial. Given a matrix polynomial $P(\lambda)$
of degree $k>1$, a linearization of $P(\lambda)$ is a pencil
$L(\lambda):=\lambda L_{1}+L_{0}$ such that there exist unimodular matrices
(i.e., square polynomial matrices with nonzero constant determinant)
$U_{1}(\lambda)$ and $V_{1}(\lambda)$ satisfying

$U_{1}(\lambda)L(\lambda)V_{1}(\lambda)=\begin{bmatrix}P(\lambda)&0\\\
0&I_{s}\end{bmatrix},$ (2)

where $I_{s}$ denotes the identity matrix of size an integer $s\geq 0$. It is
known that $L(\lambda)$ has the same finite eigenvalues with the same partial
multiplicities as $P(\lambda)$. $L(\lambda)$ is said to be a strong
linearization of $P(\lambda)$ if, in addition, there exist unimodular matrices
$U_{2}(\lambda)$ and $V_{2}(\lambda)$ satisfying

$U_{2}(\lambda)\operatorname{rev}_{1}L(\lambda)V_{2}(\lambda)=\begin{bmatrix}\operatorname{rev}_{\ell}P(\lambda)&0\\\
0&I_{s}\end{bmatrix},$ (3)

where $\operatorname{rev}_{1}L(\lambda):=\lambda L_{0}+L_{1}$ and
$\operatorname{rev}_{\ell}P(\lambda):=\lambda^{\ell}P(1/\lambda)$ for some
$\ell\geq\deg P(\lambda)$ [23]. In this case, $L(\lambda)$ has the same finite
and infinite eigenvalues with the same partial multiplicities as $P(\lambda)$.
Here we remark that an equivalent definition of strong linearization is
obtained if the matrices $U_{2}(\lambda)$ and $V_{2}(\lambda)$ in (3) are
required to be just rational matrices invertible at $0$ (i.e., $U_{2}(0)$ and
$V_{2}(0)$ are invertible) instead of unimodular (see [4, Section 3] or the
proof of Proposition 3.3). In that case we say that
$\operatorname{rev}_{1}L(\lambda)$ and
$\operatorname{diag}(\operatorname{rev}_{\ell}P(\lambda),I_{s})$ are
equivalent at $0$.

In this paper the terms linearization and strong linearization of a matrix
polynomial always refer to the Gohberg, Lancaster and Rodman’s definitions in
(2) and (3), though other non-equivalent definitions of linearizations are
available in the literature [18, 19]. In the last two decades, definitions (2)
and (3) have been very influential in many families of linearizations that
have been developed with the goal of solving unstructured and structured PEPs
(see, for instance, [3, 5, 7, 10, 11, 15, 25, 26, 27, 28, 30, 36] among many
other references on this topic). In fact, in most of these references, the
proofs that certain families of pencils are linearizations and strong
linearizations of a polynomial matrix $P(\lambda)$ are performed by finding
explicitly the unimodular matrices
$U_{1}(\lambda),V_{1}(\lambda),U_{2}(\lambda)$ and $V_{2}(\lambda)$ in (2) and
(3).555Nevertheless, we emphasize that a recent simple alternative to prove
that a certain pencil is a (strong) linearization of a polynomial matrix is to
prove that such a pencil is one of the (strong) block minimal bases pencils
introduced in [15]. See [9].

However, already in the seventies Rosenbrock [31] introduced the notion of
polynomial system matrix $S(\lambda)$ of a rational matrix
$G(\lambda)\in\mathbb{F}(\lambda)^{p\times m}$. That is, a matrix polynomial
of the form

$S(\lambda):=\begin{bmatrix}A(\lambda)&B(\lambda)\\\
-C(\lambda)&D(\lambda)\end{bmatrix}\in\mathbb{F}[\lambda]^{(n+p)\times(n+m)}$
(4)

with $A(\lambda)\in\mathbb{F}[\lambda]^{n\times n}$ regular, such that its
Schur complement with respect to $A(\lambda)$ is $G(\lambda)$, i.e.,

$G(\lambda)=D(\lambda)+C(\lambda)A(\lambda)^{-1}B(\lambda).$

The rational matrix $G(\lambda)$ is called the transfer function matrix of
$S(\lambda)$ and the matrix polynomial $A(\lambda)$ is called the state matrix
of $S(\lambda).$ Although the state matrix $A(\lambda)$ will appear in the
$(1,1)$-block of $S(\lambda)$ in the theoretical results of this paper, we
emphasize that in practice it can be at any place in $S(\lambda)$. The
important property is that $G(\lambda)$ is the Schur complement of
$A(\lambda)$ in $S(\lambda)$.

The importance of polynomial system matrices is related to the fact that under
the minimality conditions described below, Rosenbrock showed that polynomial
system matrices contain the pole and zero information of their transfer
function matrices [31]. Poles and zeros of rational matrices are defined
through the notion of the Smith–McMillan form, that we state in what follows
(see [29], or [31] for a more recent reference).

######  Definition 1.1 (Smith–McMillan form).

For any rational matrix $G(\lambda)\in\mathbb{F}(\lambda)^{p\times m}$ there
exist unimodular matrices $U_{1}(\lambda)\in\mathbb{F}[\lambda]^{p\times p}$
and $U_{2}(\lambda)\in\mathbb{F}[\lambda]^{m\times m}$ such that

$U_{1}(\lambda)G(\lambda)U_{2}(\lambda)=\left[\begin{array}[]{cc}\operatorname{diag}\left(\dfrac{\epsilon_{1}(\lambda)}{\psi_{1}(\lambda)},\ldots,\dfrac{\epsilon_{r}(\lambda)}{\psi_{r}(\lambda)}\right)&0\\\
0&0_{(p-r)\times(m-r)}\end{array}\right],$ (5)

where $r$ is the normal rank of $G(\lambda)$ and, for $i=1,\ldots,r$,
$\dfrac{\epsilon_{i}(\lambda)}{\psi_{i}(\lambda)}$ are nonzero irreducible
rational functions with $\epsilon_{i}(\lambda)$ and $\psi_{i}(\lambda)$ monic
polynomials (i.e., with leading coefficient equal to 1) that satisfy the
divisibility chains $\epsilon_{1}(\lambda)\mid\cdots\mid\epsilon_{r}(\lambda)$
and $\psi_{r}(\lambda)\mid\cdots\mid\psi_{1}(\lambda)$. The diagonal matrix in
(5) is called the Smith–McMillan form of $G(\lambda)$.

The rational functions $\epsilon_{i}(\lambda)/\psi_{i}(\lambda)$ in (5) are
called the invariant rational functions of $G(\lambda)$ and the finite poles
and zeros of $G(\lambda)$ are the roots in $\overline{\mathbb{F}}$ of the
denominators and numerators of the invariant rational functions, respectively.
In addition, for any $\lambda_{0}\in\overline{\mathbb{F}}$ each numerator
$\epsilon_{i}(\lambda)$ can be factored as
$\epsilon_{i}(\lambda)=(\lambda-\lambda_{0})^{\alpha_{i}}p_{i}(\lambda)$ with
$p_{i}(\lambda_{0})\neq 0$ and $\alpha_{i}\geq 0$. The factors
$(\lambda-\lambda_{0})^{\alpha_{i}}$ with $\alpha_{i}\neq 0$ are called the
zero elementary divisors at the finite zero $\lambda_{0}$. Analogously, for
any $\lambda_{0}\in\overline{\mathbb{F}}$ each denominator $\psi_{i}(\lambda)$
can be factored as
$\psi_{i}(\lambda)=(\lambda-\lambda_{0})^{\beta_{i}}q_{i}(\lambda)$ with
$q_{i}(\lambda_{0})\neq 0$ and $\beta_{i}\geq 0$. The factors
$(\lambda-\lambda_{0})^{\beta_{i}}$ with $\beta_{i}\neq 0$ are called the pole
elementary divisors at the finite pole $\lambda_{0}$. If $G(\lambda)$ is a
polynomial matrix then $\psi_{i}(\lambda)=1,$ for $i=1,\ldots,r$, and the
diagonal matrix in (5) is just called the Smith form of $G(\lambda)$. In this
polynomial case, there are no finite poles, the finite zeros are usually
called finite eigenvalues, and the zero elementary divisors at a finite
eigenvalue are just called elementary divisors at that eigenvalue.

We now introduce the notion of minimality of a polynomial system matrix, in
order to relate its zeros with the poles and zeros of its transfer function
matrix. A polynomial system matrix $S(\lambda)$ as in (4) is said to be
minimal if

$\mathop{\rm
rank}\nolimits\left[\begin{array}[]{ccc}A(\lambda_{0})&B(\lambda_{0})\end{array}\right]=\mathop{\rm
rank}\nolimits\left[\begin{array}[]{ccc}A(\lambda_{0})\\\
-C(\lambda_{0})\end{array}\right]=n$ (6)

for all $\lambda_{0}\in\overline{\mathbb{F}}$. Then, Rosenbrock proved the
following result [31] about the recovery of the pole and zero information of a
rational matrix from a minimal polynomial system matrix.

######  Theorem 1.2.

Let $S(\lambda)$ as in (4) be a minimal polynomial system matrix, with state
matrix $A(\lambda)$, whose transfer function matrix is $G(\lambda).$ Then the
elementary divisors at the finite eigenvalues of $A(\lambda)$ are the pole
elementary divisors at the finite poles of $G(\lambda)$, and the elementary
divisors at the finite eigenvalues of $S(\lambda)$ are the zero elementary
divisors at the finite zeros of $G(\lambda)$.

Theorem 1.2 is the foundation of the algorithms for solving numerically
rational eigenvalue problems via “linearization”, i.e., by constructing linear
minimal polynomial system matrices of a given rational matrix $G(\lambda)$ and
applying generalized eigenvalue algorithms to such system matrices. This
approach is well known at least since the early eighties [34] and has also
been used in the specific case in which $G(\lambda)$ is a polynomial matrix
[35]. However, in these references, as well as in others using that approach,
no attempt was made for relating linear minimal Rosenbrock’s polynomial system
matrices of a polynomial matrix to the definition of linearization given by
Gohberg, Lancaster and Rodman.

In this context a key remark is that in the particular case of $A(\lambda)$ in
(4) being unimodular, $G(\lambda)$ has no finite poles, i.e., $G(\lambda)$ is
a polynomial matrix, and condition (6) is satisfied. In addition, we have the
following unimodular equivalence:

$\underbrace{\begin{bmatrix}C(\lambda)A(\lambda)^{-1}&I_{p}\\\
A(\lambda)^{-1}&0\end{bmatrix}}_{\mbox{unimodular}}\begin{bmatrix}A(\lambda)&B(\lambda)\\\
-C(\lambda)&D(\lambda)\end{bmatrix}\underbrace{\begin{bmatrix}-A(\lambda)^{-1}B(\lambda)&I_{n}\\\
I_{m}&0\end{bmatrix}}_{\mbox{unimodular}}=\begin{bmatrix}G(\lambda)&\\\
&I_{n}\end{bmatrix}.$ (7)

Therefore, if $S(\lambda)$ is a pencil and $A(\lambda)$ is unimodular then
$S(\lambda)$ is a linearization for the matrix polynomial $G(\lambda)$
according to Gohberg, Lancaster and Rodman’s definition.

The purpose of this paper is to show that many of the linearizations for
matrix polynomials in the literature are actually linear polynomial system
matrices with unimodular state matrices of the corresponding matrix
polynomial. Moreover, this property establishes a new tool to determine if a
pencil $L(\lambda)$ is a linearization of a matrix polynomial. Namely, by
computing the transfer function matrix of $L(\lambda)$ (i.e., the Schur
complement) with respect to any unimodular submatrix $A(\lambda)$ that can be
identified in the pencil. We aim to analyze a sufficiently large number of
families of linearizations with this approach to convince the reader of its
interest. However, we remark that it is not always possible to identify a
unimodular submatrix $A(\lambda)$ inside a linearization such that the Schur
complement with respect to $A(\lambda)$ is the corresponding polynomial
matrix. Thus, it is not always possible to use this approach in the study of
linearizations. We also emphasize that we are not stating that the new tool is
better than previous techniques. But sometimes it may be simpler because the
unimodular submatrix can be easily identified and the computation of the
corresponding transfer function matrix is straightforward.

This paper is organized as follows. In Section 2, we first revisit from the
point of view of Rosenbrock’s system matrices the Frobenius companion form or
the (first) companion form [23, 24], that is one of the most classic
linearizations. Section 3 includes some general auxiliary results about
polynomial system matrices of matrix polynomials. Moreover, we discuss in
Section 3 how to recover easily the eigenvectors of a matrix polynomial from
those of a linearization when it is viewed as a polynomial system matrix.
Then, we consider in Section 4 the family of “comrade” linearizations [3, 6,
21], that are particular cases of the CORK linearizations [33] studied in
Section 5. We also analyze the family of (extended) block Kronecker
linearizations [15] in Sections 6 and 7, which includes, modulo permutations,
all the families of Fiedler linearizations [9]. We present a note in Section 8
on how to use the Rosenbrock’s system matrix approach to linearizations of
polynomial matrices to construct easily linearizations for rational matrices,
a task that has not been always easy via other approaches. Finally, some
conclusions and possible lines of future research are presented in Section 9.

##  2 Frobenius companion form

Given a matrix polynomial $P(\lambda)\in\mathbb{F}[\lambda]^{p\times m}$
written in terms of the monomial basis as in (1), the Frobenius companion form
is the following pencil

$C_{1}(\lambda):=\left[\begin{array}[]{ccccc}\lambda
P_{k}+P_{k-1}&P_{k-2}&\cdots&P_{1}&P_{0}\\\ -I_{m}&\lambda I_{m}\\\
&\ddots&\ddots\\\ &&\ddots&\lambda I_{m}\\\ &&&-I_{m}&\lambda
I_{m}\end{array}\right].$

One of the most basic results in the theory of matrix polynomials is that
$C_{1}(\lambda)$ is a strong linearization of $P(\lambda)$ [23]. The classical
proofs of this result proceed by finding the four unimodular matrices that
satisfy (2) and (3). We now show that $C_{1}(\lambda)$ can be seen as a
polynomial system matrix of $P(\lambda)$ with unimodular state matrix, which
in turn implies that $C_{1}(\lambda)$ is a linearization of $P(\lambda)$.

###  2.1 Frobenius companion form as a Rosenbrock’s system matrix

We consider the following partition:

$C_{1}(\lambda)=\left[\begin{array}[]{cccc|c}\lambda
P_{k}+P_{k-1}&P_{k-2}&\cdots&P_{1}&P_{0}\\\ \hline\cr-I_{m}&\lambda
I_{m}&&&\\\ &\ddots&\ddots&&\\\ &&\ddots&\lambda I_{m}&\\\ &&&-I_{m}&\lambda
I_{m}\end{array}\right]=:\begin{bmatrix}-C(\lambda)&D(\lambda)\\\
A(\lambda)&B(\lambda)\end{bmatrix},$ (8)

as a Rosenbrock’s system matrix with state matrix $A(\lambda)$. Then,
$A(\lambda)$ is clearly unimodular and the transfer function matrix is

$\displaystyle
D(\lambda)+C(\lambda)A(\lambda)^{-1}B(\lambda)=P_{0}-\begin{bmatrix}\lambda
P_{k}+P_{k-1}&P_{k-2}&\cdots&P_{1}\end{bmatrix}A(\lambda)^{-1}B(\lambda).$ (9)

To compute (9), we consider the polynomial vector containing the elements of
the monomial basis. Namely,

$\Lambda_{k-1}(\lambda):=\begin{bmatrix}\lambda^{k-1}&\lambda^{k-2}&\cdots&\lambda&1\end{bmatrix}^{T}.$
(10)

Then, observe that

$\begin{bmatrix}A(\lambda)&B(\lambda)\end{bmatrix}(\Lambda_{k-1}(\lambda)\otimes
I_{m})=0.$ (11)

Therefore,
$A(\lambda)\begin{bmatrix}\lambda^{k-1}\,I_{m}&\lambda^{k-2}\,I_{m}&\cdots&\lambda
I_{m}\end{bmatrix}^{T}+B(\lambda)=0$ and

$A(\lambda)^{-1}B(\lambda)=-\begin{bmatrix}\lambda^{k-1}\,I_{m}&\lambda^{k-2}\,I_{m}&\cdots&\lambda
I_{m}\end{bmatrix}^{T}.$ (12)

Finally, by (9) and (12), we obtain that the transfer function matrix of (8)
is $P(\lambda)$.

###  2.2 Reversal of the Frobenius companion form as a Rosenbrock’s system
matrix

Now, we consider the reversal $\operatorname{rev}_{1}C_{1}(\lambda)$ and the
following partition:

$\operatorname{rev}_{1}C_{1}(\lambda)=\left[\begin{array}[]{c|cccc}P_{k}+\lambda
P_{k-1}&\lambda P_{k-2}&\cdots&\lambda P_{1}&\lambda P_{0}\\\
\hline\cr-\lambda I_{m}&I_{m}&&&\\\ &\ddots&\ddots&&\\\ &&\ddots&I_{m}&\\\
&&&-\lambda
I_{m}&I_{m}\end{array}\right]=:\begin{bmatrix}D_{r}(\lambda)&-C_{r}(\lambda)\\\
B_{r}(\lambda)&A_{r}(\lambda)\end{bmatrix}.$ (13)

Then, we have that $A_{r}(\lambda)$ is unimodular, and the transfer function
matrix of $\operatorname{rev}_{1}C_{1}(\lambda)$ with the partition in (13) is

$\displaystyle
D_{r}(\lambda)+C_{r}(\lambda)A_{r}(\lambda)^{-1}B_{r}(\lambda)=P_{k}+\lambda
P_{k-1}-\begin{bmatrix}\lambda P_{k-2}&\cdots&\lambda P_{1}&\lambda
P_{0}\end{bmatrix}A_{r}(\lambda)^{-1}B_{r}(\lambda).$

Taking into account that

$\begin{bmatrix}B_{r}(\lambda)&A_{r}(\lambda)\end{bmatrix}(\operatorname{rev}_{k-1}\Lambda_{k-1}(\lambda)\otimes
I_{m})=0,$ (14)

we obtain that

$A_{r}(\lambda)^{-1}B_{r}(\lambda)=-\begin{bmatrix}\lambda
I_{m}&\cdots&\lambda^{k-2}\,I_{m}&\lambda^{k-1}\,I_{m}\end{bmatrix}^{T}.$

Therefore, the transfer function matrix is

$D_{r}(\lambda)+C_{r}(\lambda)A_{r}(\lambda)^{-1}B_{r}(\lambda)=P_{k}+\lambda
P_{k-1}+\lambda^{2}P_{k-2}+\cdots+\lambda^{k}P_{0}=\operatorname{rev}_{k}P(\lambda).$

It then follows that $C_{1}(\lambda)$ is a strong linearization of
$P(\lambda)$.

Notice that although the expression of the transfer function matrix involves
$A(\lambda)^{-1}$, we computed very easily the transfer functions of
$C_{1}(\lambda)$ and of $\operatorname{rev}_{1}C_{1}(\lambda)$ without
computing explicitly $A(\lambda)^{-1}$. For that, we used the linear relation
of the monomial basis in (11) and (14). We will see that similar linear
relations arise in other linearizations that can also be viewed as linear
polynomial system matrices with unimodular state matrices $A(\lambda)$, and it
allows to compute their transfer function matrices without computing
explicitly $A(\lambda)^{-1}$.

##  3 Auxiliary results: polynomial system matrices of matrix polynomials

The discussion in the introduction around (7) is summarized for the particular
case of linear system matrices in the following Proposition 3.1. The proof
follows from (7).

######  Proposition 3.1.

Let $G(\lambda)\in\mathbb{F}(\lambda)^{p\times m}$ and let

$\mathcal{L}(\lambda)=\left[\begin{array}[]{cc}A_{1}\lambda+A_{0}&B_{1}\lambda+B_{0}\\\
-(C_{1}\lambda+C_{0})&D_{1}\lambda+D_{0}\end{array}\right]\in\mathbb{F}[\lambda]^{(n+p)\times(n+m)}$

be a linear polynomial system matrix of $G(\lambda)$, with state matrix
$A(\lambda):=A_{1}\lambda+A_{0}$. If $A(\lambda)$ is unimodular then
$G(\lambda)$ is a matrix polynomial and $\mathcal{L}(\lambda)$ is a
linearization of $G(\lambda)$.

In the next Proposition 3.2 we give a necessary and sufficient condition for
the state matrix $A(\lambda)$ of a polynomial system matrix to be unimodular.
This result can be useful in problems where the transfer function matrix
$G(\lambda)$ is polynomial and computing $G(\lambda)$ is easier than proving
that $A(\lambda)$ is unimodular.

######  Proposition 3.2.

Let $G(\lambda)\in\mathbb{F}(\lambda)^{p\times m}$ and let

$S(\lambda)=\begin{bmatrix}A(\lambda)&B(\lambda)\\\
-C(\lambda)&D(\lambda)\end{bmatrix}\in\mathbb{F}[\lambda]^{(n+p)\times(n+m)}$

be a polynomial system matrix of $G(\lambda)$, with state matrix $A(\lambda)$.
Then $A(\lambda)$ is unimodular if and only if $S(\lambda)$ is minimal and
$G(\lambda)$ is a matrix polynomial.

###### Proof.

It is clear that if $A(\lambda)$ is unimodular then $G(\lambda)$ is a matrix
polynomial and $S(\lambda)$ is minimal. That is, condition (6) holds.
Conversely, if $G(\lambda)$ is a matrix polynomial and $S(\lambda)$ is minimal
then $A(\lambda)$ has no finite eigenvalues, since the finite eigenvalues of
$A(\lambda)$ would be the finite poles of $G(\lambda)$ by Theorem 1.2. But
$G(\lambda)$ has no finite poles since it is a matrix polynomial. Therefore,
$\det A(\lambda)$ is constant, which implies that $A(\lambda)$ is unimodular.
∎

We could apply Proposition 3.1 to the reversal
$\operatorname{rev}_{1}\mathcal{L}(\lambda)$ to see that a linearization
$\mathcal{L}(\lambda)$ is, in addition, a strong linearization. For that, we
may need to select another submatrix of
$\operatorname{rev}_{1}\mathcal{L}(\lambda)$ as appropriate state matrix, with
a different partition from the one considered in $\mathcal{L}(\lambda)$.
However, selecting a unimodular submatrix in
$\operatorname{rev}_{1}\mathcal{L}(\lambda)$ such that the Schur complement
with respect to it is $\operatorname{rev}_{\ell}P(\lambda)$, for some
$\ell\geq\deg P(\lambda)$, is not always possible. In that case, we can also
try to apply the following Proposition 3.3, which requires milder conditions.

######  Proposition 3.3.

Let $\mathcal{L}(\lambda)$ be a linearization of a polynomial matrix
$P(\lambda)\in\mathbb{F}[\lambda]^{p\times m}$. Assume that we can write

$\operatorname{rev}_{1}\mathcal{L}(\lambda)=\left[\begin{array}[]{cc}\widetilde{A}_{1}\lambda+\widetilde{A}_{0}&\widetilde{B}_{1}\lambda+\widetilde{B}_{0}\\\
-(\widetilde{C}_{1}\lambda+\widetilde{C}_{0})&\widetilde{D}_{1}\lambda+\widetilde{D}_{0}\end{array}\right]\in\mathbb{F}[\lambda]^{(n+p)\times(n+m)}$

as a linear polynomial system matrix with state matrix
$\widetilde{A}(\lambda):=\widetilde{A}_{1}\lambda+\widetilde{A}_{0}$. If
$\widetilde{A}(\lambda)$ is invertible at $0$, i.e., if $\widetilde{A}_{0}$ is
invertible, and the transfer function matrix of
$\operatorname{rev}_{1}\mathcal{L}(\lambda)$ is equivalent at $0$ to
$\operatorname{rev}_{\ell}P(\lambda)$, for some $\ell\geq\deg P(\lambda)$,
then $\mathcal{L}(\lambda)$ is a strong linearization of $P(\lambda)$.

###### Proof.

Since $\mathcal{L}(\lambda)$ is a linearization of $P(\lambda)$, we know by
[12, Theorem 4.1] that

  * (a)

$\dim\mathcal{N}_{r}(P)=\dim\mathcal{N}_{r}(\mathcal{L})$ and
$\dim\mathcal{N}_{\ell}(P)=\dim\mathcal{N}_{\ell}(\mathcal{L})$, where
$\mathcal{N}_{r}(\cdot)$ and $\mathcal{N}_{\ell}(\cdot)$ stand for right and
left rational null spaces, respectively.

  * (b)

$\mathcal{L}(\lambda)$ and $P(\lambda)$ have exactly the same finite
eigenvalues with the same elementary divisors.

Moreover, taking into account that $\widetilde{A}_{0}$ is invertible and that
the transfer function matrix of $\operatorname{rev}_{1}\mathcal{L}(\lambda)$
is equivalent at $0$ to $\operatorname{rev}_{\ell}P(\lambda)$, we have by [17,
Theorem 3.5] that the elementary divisors at $0$ of
$\operatorname{rev}_{1}\mathcal{L}(\lambda)$ and
$\operatorname{rev}_{\ell}P(\lambda)$ are the same or, equivalently, that

  * (c)

$\mathcal{L}(\lambda)$ and $P(\lambda)$ have exactly the same elementary
divisors at infinity.

Statements $\rm(a)$, $\rm(b)$ and $\rm(c)$ imply by [12, Theorem 4.1] that
$\mathcal{L}(\lambda)$ is a strong linearization of $P(\lambda)$. ∎

###  3.1 Recovery of eigenvectors

An advantage of considering linearizations of matrix polynomials as
Rosenbrock’s system matrices with unimodular state matrix is that the
eigenvectors associated with an eigenvalue $\lambda_{0}$ can be recovered
always in the same way. Given $\lambda_{0}\in\overline{\mathbb{F}}$ and a
polynomial matrix $P(\lambda)\in\mathbb{F}[\lambda]^{p\times m}$, we consider
the following vector spaces over $\overline{\mathbb{F}}$:

$\begin{array}[]{l}\mathcal{N}_{r}(P(\lambda_{0}))=\\{x\in\overline{\mathbb{F}}^{m\times
1}:P(\lambda_{0})x=0\\},\text{ and}\\\
\mathcal{N}_{\ell}(P(\lambda_{0}))=\\{y^{T}\in\overline{\mathbb{F}}^{1\times
p}:y^{T}P(\lambda_{0})=0\\},\end{array}$

which are called, respectively, the right and left nullspaces over
$\overline{\mathbb{F}}$ of $P(\lambda_{0})$. If $\lambda_{0}$ is an eigenvalue
of a regular $P(\lambda)$, then $\mathcal{N}_{r}(P(\lambda_{0}))$ and
$\mathcal{N}_{\ell}(P(\lambda_{0}))$ are non trivial and contain,
respectively, the right and left eigenvectors of $P(\lambda)$ associated with
$\lambda_{0}.$

In the following Proposition 3.4 we state the relation between the right and
left nullspaces of a polynomial system matrix with unimodular state matrix and
those of its polynomial transfer function matrix $P(\lambda)$. This is a
particular case of the results from [16, Proposition 5.1] and [16, Proposition
5.2]. Then, in the particular case of $P(\lambda)$ being regular, Proposition
3.4 can be used to recover the right and left eigenvectors of $P(\lambda)$
from those of a polynomial system matrix of it with unimodular state matrix.

######  Proposition 3.4.

Let $S(\lambda)$ be a polynomial system matrix as in Proposition 3.2 with
$A(\lambda)$ unimodular, and let $P(\lambda)\in\mathbb{F}[\lambda]^{p\times
m}$ be its transfer function matrix. Let
$\lambda_{0}\in\overline{\mathbb{F}}$. Then, the following statements hold:

  * (a)

The linear map

$\displaystyle E_{r}\,:\,\mathcal{N}_{r}(P(\lambda_{0}))$
$\displaystyle\longrightarrow\mathcal{N}_{r}(S(\lambda_{0}))$ $\displaystyle
x$
$\displaystyle\longmapsto\begin{bmatrix}-A(\lambda_{0})^{-1}B(\lambda_{0})\\\
I_{m}\end{bmatrix}x$

is a bijection between the right nullspaces over $\overline{\mathbb{F}}$ of
$P(\lambda_{0})$ and $S(\lambda_{0})$.

  * (b)

The linear map

$\displaystyle E_{\ell}\,:\,\mathcal{N}_{\ell}(P(\lambda_{0}))$
$\displaystyle\longrightarrow\mathcal{N}_{\ell}(S(\lambda_{0}))$
$\displaystyle y^{T}$ $\displaystyle\longmapsto
y^{T}\begin{bmatrix}C(\lambda_{0})A(\lambda_{0})^{-1}&I_{p}\end{bmatrix}$

is a bijection between the left nullspaces over $\overline{\mathbb{F}}$ of
$P(\lambda_{0})$ and $S(\lambda_{0})$.

We can see that, in particular, right and left eigenvectors of a polynomial
matrix $P(\lambda)$ can be directly recovered from the last block of the right
and left eigenvectors of its polynomial system matrix $S(\lambda)$. In some
cases, we can also recover the right or the left eigenvectors of $P(\lambda)$
from other blocks of the right or the left eigenvectors of $S(\lambda)$. This
is illustrated for right eigenvectors in the following example.

######  Example 3.5.

Recall the Frobenius companion form $C_{1}(\lambda)$ in Section 2 and the
partition as a polynomial system matrix in (8). By (12), we have that, for any
$\lambda_{0}\in\overline{\mathbb{F}}$,

$-A(\lambda_{0})^{-1}B(\lambda_{0})=\begin{bmatrix}\lambda_{0}^{k-1}\,I_{m}&\lambda_{0}^{k-2}\,I_{m}&\cdots&\lambda_{0}I_{m}\end{bmatrix}^{T}.$

Therefore, by Proposition 3.4, the linear map

$\displaystyle F_{r}\,:\,\mathcal{N}_{r}(P(\lambda_{0}))$
$\displaystyle\longrightarrow\mathcal{N}_{r}(C_{1}(\lambda_{0}))$
$\displaystyle x$
$\displaystyle\longmapsto\begin{bmatrix}\lambda_{0}^{k-1}\,I_{m}&\lambda_{0}^{k-2}\,I_{m}&\cdots&\lambda_{0}I_{m}&I_{m}\end{bmatrix}^{T}x$

is a bijection between the right nullspaces over $\overline{\mathbb{F}}$ of
$P(\lambda_{0})$ and $C_{1}(\lambda_{0})$.

##  4 Comrade linearizations

Consider a polynomial matrix

$P(\lambda)=P_{k}\phi_{k}(\lambda)+P_{k-1}\phi_{k-1}(\lambda)+\cdots+P_{1}\phi_{1}(\lambda)+P_{0}\phi_{0}(\lambda)\in\mathbb{F}[\lambda]^{p\times
m},$

written in terms of a polynomial basis satisfying a three-term recurrence
relation of the form:

$\alpha_{j}\phi_{j+1}(\lambda)=(\lambda-\beta_{j})\phi_{j}(\lambda)-\gamma_{j}\phi_{j-1}(\lambda)\quad
j\geq 0$

where $\alpha_{j},\beta_{j},\gamma_{j}\in\mathbb{F},$ $\alpha_{j}\neq 0,$
$\phi_{-1}(\lambda)=0,$ and $\phi_{0}(\lambda)=1.$ It is “well-known” that the
following “comrade” companion matrix introduced in [6, Chapter 5]

${\small
C_{\phi}(\lambda)=\left[\begin{array}[]{cccccc}\dfrac{(\lambda-\beta_{k-1})}{\alpha_{k-1}}P_{k}+P_{k-1}&P_{k-2}-\dfrac{\gamma_{k-1}}{\alpha_{k-1}}P_{k}&P_{k-3}&\cdots&P_{1}&P_{0}\\\
-\alpha_{k-2}I&(\lambda-\beta_{k-2})I&-\gamma_{k-2}I&&&\\\
&-\alpha_{k-3}I&(\lambda-\beta_{k-3})I&-\gamma_{k-3}I&&\\\
&&\ddots&\ddots&\ddots&\\\
&&&-\alpha_{1}I&(\lambda-\beta_{1})I&-\gamma_{1}I\\\
&&&&-\alpha_{0}I&(\lambda-\beta_{0})I\end{array}\right]}$

is a strong linearization of $P(\lambda)$. Different proofs of this fact can
be found in [3, 16, 21]. As we discuss in this section, this can also be
proved via Rosenbrock’s system matrices.

###  4.1 Comrade linearizations as Rosenbrock’s system matrices

With the following partition:

$\displaystyle C_{\phi}(\lambda)$
$\displaystyle=\left[\begin{array}[]{ccccc|c}\dfrac{(\lambda-\beta_{k-1})}{\alpha_{k-1}}P_{k}+P_{k-1}&P_{k-2}-\dfrac{\gamma_{k-1}}{\alpha_{k-1}}P_{k}&P_{k-3}&\cdots&P_{1}&P_{0}\\\
\hline\cr-\alpha_{k-2}I&(\lambda-\beta_{k-2})I&-\gamma_{k-2}I&&&\\\
&-\alpha_{k-3}I&(\lambda-\beta_{k-3})I&-\gamma_{k-3}I&&\\\
&&\ddots&\ddots&\ddots&\\\
&&&-\alpha_{1}I&(\lambda-\beta_{1})I&-\gamma_{1}I\\\
&&&&-\alpha_{0}I&(\lambda-\beta_{0})I\end{array}\right]$
$\displaystyle=:\begin{bmatrix}-C(\lambda)&D(\lambda)\\\
A(\lambda)&B(\lambda)\end{bmatrix},$

we get that $C_{\phi}(\lambda)$ is a linear polynomial system matrix with
unimodular state matrix $A(\lambda)$ and transfer function matrix
$P(\lambda)$. Then $C_{\phi}(\lambda)$ is a linearization of $P(\lambda)$ by
Proposition 3.1. Notice that comrade linearizations are constructed by
considering the recurrence relation satisfied by the polynomial basis. They
are particular cases of the more general notion of CORK linearizations,
described in Section 5. The computation of the transfer function matrix of
$C_{\phi}(\lambda)$ is a particular case of the computation in the proof of
Theorem 5.1. Therefore, we omit the details here and just emphasize that such
computation is based on the identity

$\begin{bmatrix}A(\lambda)&B(\lambda)\end{bmatrix}\,\left(\begin{bmatrix}\phi_{k-1}(\lambda)\\\
\phi_{k-2}(\lambda)\\\ \vdots\\\ \phi_{0}(\lambda)\\\ \end{bmatrix}\otimes
I_{m}\right)=0\,.$

###  4.2 Reversal of comrade linearizations as Rosenbrock’s system matrices

To see that $C_{\phi}(\lambda)$ is a strong linearization, it is not possible
to identify a unimodular submatrix of
$\operatorname{rev}_{1}C_{\phi}(\lambda)$ such that the transfer function
matrix is $\operatorname{rev}_{k}P(\lambda)$. However, we can use Proposition
3.3. For that, we consider the following partition:

$\displaystyle\operatorname{rev}_{1}C_{\phi}(\lambda)$
$\displaystyle=\left[\begin{array}[]{c|ccccc}\dfrac{(1-\lambda\beta_{k-1})}{\alpha_{k-1}}P_{k}+\lambda
P_{k-1}&\lambda P_{k-2}-\lambda\dfrac{\gamma_{k-1}}{\alpha_{k-1}}P_{k}&\lambda
P_{k-3}&\cdots&\lambda P_{1}&\lambda P_{0}\\\
\hline\cr-\lambda\alpha_{k-2}I&(1-\lambda\beta_{k-2})I&-\lambda\gamma_{k-2}I&&&\\\
&-\lambda\alpha_{k-3}I&(1-\lambda\beta_{k-3})I&-\lambda\gamma_{k-3}I&&\\\
&&\ddots&\ddots&\ddots&\\\
&&&-\lambda\alpha_{1}I&(1-\lambda\beta_{1})I&-\lambda\gamma_{1}I\\\
&&&&-\lambda\alpha_{0}I&(1-\lambda\beta_{0})I\end{array}\right]$
$\displaystyle=:\begin{bmatrix}\widetilde{D}(\lambda)&-\widetilde{C}(\lambda)\\\
\widetilde{B}(\lambda)&\widetilde{A}(\lambda)\end{bmatrix},$

so that $\operatorname{rev}_{1}C_{\phi}(\lambda)$ is a linear polynomial
system matrix of $\dfrac{1}{f(\lambda)}\operatorname{rev}_{k}P(\lambda)$, with
$f(\lambda):=\lambda^{k-1}\phi_{k-1}(1/\lambda)$, and state matrix
$\widetilde{A}(\lambda)$. In addition, $\widetilde{A}(\lambda)$ is invertible
at $0$ and $f(0)\neq 0$ since $\deg\phi_{k-1}(\lambda)=k-1$. The computation
of the transfer function matrix of $\operatorname{rev}_{1}C_{\phi}(\lambda)$
is a particular case of the computation given in the proof of Theorem 5.2.
Therefore, we omit the details here.

##  5 CORK linearizations

In this section we consider polynomial matrices $P(\lambda)$ written as

$P(\lambda)=\displaystyle\sum_{i=0}^{k-1}(A_{i}-\lambda
B_{i})p_{i}(\lambda)\in\mathbb{F}[\lambda]^{p\times m},$ (15)

where $p_{i}(\lambda)$ are scalar polynomials with $p_{0}(\lambda)\equiv 1$
and $A_{i}$, $B_{i}\in\mathbb{F}^{p\times m}$. Define the polynomial vector

$p(\lambda):=[p_{k-1}(\lambda)\quad\cdots\quad p_{0}(\lambda)]^{T},$

and assume that the polynomials $p_{i}(\lambda)$ satisfy a linear relation

$(X-\lambda Y)p(\lambda)=0,$ (16)

where $\mathop{\rm rank}\nolimits(X-\lambda_{0}Y)=k-1\text{ for all
}\lambda_{0}\in\overline{\mathbb{F}},$ and $X-\lambda Y$ has size $(k-1)\times
k.$ Then the matrix pencil

$C(\lambda)=\left[\begin{array}[]{c}\begin{array}[]{ccc}A_{k-1}-\lambda
B_{k-1}&\cdots&A_{0}-\lambda B_{0}\end{array}\\\
\hdashline[2pt/2pt]\phantom{\Big{|}}(X-\lambda Y)\otimes
I_{m}\end{array}\right]$ (17)

is called a CORK linearization of $P(\lambda)$ [33]. CORK linearizations have
played a fundamental role in the development of the Compact Rational Krylov
(CORK) algorithm [33] for solving numerically large scale PEPs that arise as
approximations of other nonlinear eigenvalue problems coming from real-world
applications. Such PEPs may have large degrees and the advantage of the CORK
algorithm over previous methods are that its computational and memory costs
are essentially independent of the degree of the PEP.

We show in the following subsection that the CORK linearization $C(\lambda)$
can be seen as a linear polynomial system matrix of $P(\lambda)$ with
unimodular state matrix.

###  5.1 CORK linearizations as Rosenbrock’s system matrices

######  Theorem 5.1.

Let $P(\lambda)$ be a matrix polynomial as in (15) and consider the matrix
pencil $C(\lambda)$ in (17). Consider the following partition

$C(\lambda)=\left[\begin{array}[]{c|c}\begin{array}[]{ccc}A_{k-1}-\lambda
B_{k-1}&\cdots&A_{1}-\lambda B_{1}\end{array}&A_{0}-\lambda B_{0}\\\
\hline\cr\phantom{\Big{|}}X_{1}(\lambda)&\begin{array}[]{c}X_{2}(\lambda)\end{array}\end{array}\right],$

where $(X-\lambda Y)\otimes
I_{m}=:\begin{bmatrix}X_{1}(\lambda)&X_{2}(\lambda)\end{bmatrix}$ and
$X_{1}(\lambda)$ has size $(k-1)m\times(k-1)m$. Then, $C(\lambda)$ is a linear
polynomial system matrix with state matrix $X_{1}(\lambda)$ and transfer
function matrix $P(\lambda)$. In addition, $X_{1}(\lambda)$ is unimodular.

###### Proof.

By (16), we have that
$\begin{bmatrix}X_{1}(\lambda)&X_{2}(\lambda)\end{bmatrix}(p(\lambda)\otimes
I_{m})=0$ and, thus,

$X_{1}(\lambda)[p_{k-1}(\lambda)I_{m}\quad\cdots\quad
p_{1}(\lambda)I_{m}]^{T}+X_{2}(\lambda)=0,$ (18)

taking into account that $p_{0}(\lambda)=1$. From (18) it follows that
$X_{1}(\lambda)$ is regular. By contradiction, if $X_{1}(\lambda)$ is singular
there exists a nonzero polynomial vector $w(\lambda)$ such that
$w(\lambda)^{T}X_{1}(\lambda)=0$ and, therefore,
$w(\lambda)^{T}X_{2}(\lambda)=0$ by (18). Thus,
$w(\lambda)^{T}\begin{bmatrix}X_{1}(\lambda)&X_{2}(\lambda)\end{bmatrix}=0$.
But this is a contradiction since
$\begin{bmatrix}X_{1}(\lambda)&X_{2}(\lambda)\end{bmatrix}$ has full row
normal rank. Then $C(\lambda)$ is a linear polynomial system matrix with state
matrix $X_{1}(\lambda)$ and its transfer function matrix is

$A_{0}-\lambda B_{0}-\begin{bmatrix}A_{k-1}-\lambda
B_{k-1}&\cdots&A_{1}-\lambda
B_{1}\end{bmatrix}X_{1}(\lambda)^{-1}X_{2}(\lambda).$ (19)

By (18), we have that

$X_{1}(\lambda)^{-1}X_{2}(\lambda)=-[p_{k-1}(\lambda)I_{m}\quad\cdots\quad
p_{1}(\lambda)I_{m}]^{T},$ (20)

and, by (19) and (20), we obtain that the transfer function matrix is

$A_{0}-\lambda B_{0}+\begin{bmatrix}A_{k-1}-\lambda
B_{k-1}&\cdots&A_{1}-\lambda
B_{1}\end{bmatrix}\begin{bmatrix}p_{k-1}(\lambda)I_{m}\\\ \vdots\\\
p_{1}(\lambda)I_{m}\end{bmatrix}=P(\lambda).$

In addition, the state matrix $X_{1}(\lambda)$ is unimodular. To see this, we
consider the following pencil

$X(\lambda):=\begin{bmatrix}X_{1}(\lambda)&X_{2}(\lambda)\\\
I_{(k-1)m}&0\end{bmatrix}$

as a polynomial system matrix with state matrix $X_{1}(\lambda)$. Then we have
that $X(\lambda)$ is minimal, since $\mathop{\rm
rank}\nolimits(X-\lambda_{0}Y)=k-1\text{ for all
}\lambda_{0}\in\overline{\mathbb{F}},$ and the transfer function matrix (i.e.,
$-X_{1}(\lambda)^{-1}X_{2}(\lambda)$) is a polynomial matrix by (20). Then, by
Proposition 3.2, $X_{1}(\lambda)$ is unimodular. ∎

Theorem 5.1 together with Proposition 3.1 implies that $C(\lambda)$ is a
linearization of $P(\lambda)$.

###  5.2 Reversal of CORK linearizations as Rosenbrock’s system matrices

By assuming extra conditions in (16), it follows from Proposition 3.3 and the
next Theorem 5.2 that $C(\lambda)$ is, in addition, a strong linearization by
considering $\operatorname{rev}_{1}C(\lambda)$ as a Rosenbrock’s system
matrix.

######  Theorem 5.2.

Let $P(\lambda)$ be a matrix polynomial as in (15) and consider the matrix
pencil $C(\lambda)$ in (17). Assume that the $(k-1)\times k$ matrix $Y$ in
(17) satisfies $\mathop{\rm rank}\nolimits Y=k-1$ and that $\deg
p_{k-1}(\lambda)=k-1$. Consider the following partition for
$\operatorname{rev}_{1}C(\lambda)$:

$\operatorname{rev}_{1}C(\lambda)=\left[\begin{array}[]{c|c}\lambda
A_{k-1}-B_{k-1}&\begin{array}[]{ccc}\lambda A_{k-2}-B_{k-2}&\cdots&\lambda
A_{0}-B_{0}\end{array}\\\
\hline\cr\phantom{\Big{|}}\operatorname{rev}_{1}Y_{1}(\lambda)&\operatorname{rev}_{1}Y_{2}(\lambda)\end{array}\right].$

Then $\operatorname{rev}_{1}C(\lambda)$ is a linear polynomial system matrix
with state matrix $\operatorname{rev}_{1}Y_{2}(\lambda)$ of size
$(k-1)m\times(k-1)m$ and transfer function matrix
$\dfrac{1}{q(\lambda)}\operatorname{rev}_{k}P(\lambda)$, where
$q(\lambda):=\operatorname{rev}_{k-1}p_{k-1}(\lambda)$ and $q(0)\neq 0$. In
addition, $\operatorname{rev}_{1}Y_{2}(\lambda)$ is invertible at $0$.

###### Proof.

First, taking into account that
$\begin{bmatrix}Y_{1}(\lambda)&Y_{2}(\lambda)\end{bmatrix}(p(\lambda)\otimes
I_{m})=0$, we have that
$\begin{bmatrix}\operatorname{rev}_{1}Y_{1}(\lambda)&\operatorname{rev}_{1}Y_{2}(\lambda)\end{bmatrix}(\lambda^{k-1}p(1/\lambda)\otimes
I_{m})=0$ and, thus,

$q(\lambda)\operatorname{rev}_{1}Y_{1}(\lambda)+\operatorname{rev}_{1}Y_{2}(\lambda)[\lambda^{k-1}p_{k-2}(1/\lambda)I_{m}\quad\cdots\quad\lambda^{k-1}p_{0}(1/\lambda)I_{m}]^{T}=0,$
(21)

where
$q(\lambda):=\operatorname{rev}_{k-1}p_{k-1}(\lambda)=\lambda^{k-1}p_{k-1}(1/\lambda)$.
From (21), and the fact that the matrix
$\begin{bmatrix}\operatorname{rev}_{1}Y_{1}(0)&\operatorname{rev}_{1}Y_{2}(0)\end{bmatrix}$
has full row rank since $Y$ has full row rank, it follows that
$\operatorname{rev}_{1}Y_{2}(\lambda)$ is invertible at $0$, i.e., that
$\operatorname{rev}_{1}Y_{2}(0)$ is invertible. By contradiction, if
$\operatorname{rev}_{1}Y_{2}(0)$ is not invertible, there exists a constant
vector $w$ such that $w^{T}\operatorname{rev}_{1}Y_{2}(0)=0$ and, by (21),
$w^{T}\operatorname{rev}_{1}Y_{1}(0)=0$ since $q(0)\neq 0$. Therefore,
$w^{T}\begin{bmatrix}\operatorname{rev}_{1}Y_{1}(0)&\operatorname{rev}_{1}Y_{2}(0)\end{bmatrix}=0$
and this is a contradiction since
$\begin{bmatrix}\operatorname{rev}_{1}Y_{1}(0)&\operatorname{rev}_{1}Y_{2}(0)\end{bmatrix}$
has full row rank.

We now compute the transfer function matrix of
$\operatorname{rev}_{1}C(\lambda)$ as a linear polynomial system matrix with
state matrix $\operatorname{rev}_{1}Y_{2}(\lambda)$. That is,

$T(\lambda):=\lambda A_{k-1}-B_{k-1}-\begin{bmatrix}\lambda
A_{k-2}-B_{k-2}&\cdots&\lambda
A_{0}-B_{0}\end{bmatrix}(\operatorname{rev}_{1}Y_{2}(\lambda))^{-1}\operatorname{rev}_{1}Y_{1}(\lambda).$
(22)

By (21), we know that

$(\operatorname{rev}_{1}Y_{2}(\lambda))^{-1}\operatorname{rev}_{1}Y_{1}(\lambda)=-\frac{1}{p_{k-1}(1/\lambda)}[p_{k-2}(1/\lambda)I_{m}\quad\cdots\quad
p_{0}(1/\lambda)I_{m}]^{T}.$ (23)

Combining (22) and (23), we obtain

$T(\lambda):=\lambda
A_{k-1}-B_{k-1}+\frac{1}{p_{k-1}(1/\lambda)}\begin{bmatrix}\lambda
A_{k-2}-B_{k-2}&\cdots&\lambda
A_{0}-B_{0}\end{bmatrix}\begin{bmatrix}p_{k-2}(1/\lambda)I_{m}\\\ \vdots\\\
p_{0}(1/\lambda)I_{m}\end{bmatrix}.$ (24)

Multiplying $T(\lambda)$ by $q(\lambda)$ we obtain

$q(\lambda)T(\lambda)=\displaystyle\sum_{i=0}^{k-1}(\lambda
A_{i}-B_{i})(\lambda^{k-1}p_{i}(1/\lambda))=\operatorname{rev}_{k}P(\lambda).$

∎

##  6 Block Kronecker linearizations

In this section, we consider the block Kronecker pencils introduced in [15]
and show that they can also be seen as Rosenbrock’s system matrices with
unimodular state matrix. Block Kronecker pencils are a wide family of pencils
that contains, among many other pencils, the Frobenius companion form and,
modulo permutations, the Fiedler pencils originally introduced in [22] for
scalar polynomials and extended in [5, 11] to matrix polynomials. They also
include, modulo permutations, the generalized Fiedler pencils introduced in
[5]. These inclusions were studied in [9]. Block Kronecker pencils are
particular cases of a much wider class of pencils that are called strong block
minimal bases pencils [15]. Block Kronecker pencils have excellent properties.
For instance, they can be used for solving numerically PEPs in a structurally
backward stable manner [15].

######  Definition 6.1.

Let $\lambda M_{1}+M_{0}$ be an arbitrary pencil. Any pencil of the form

$C_{K}(\lambda)=\left[\begin{array}[]{c|c}\lambda
M_{1}+M_{0}&L_{\eta}(\lambda)^{T}\otimes I_{p}\\\ \hline\cr
L_{\epsilon}(\lambda)\otimes I_{m}&0\end{array}\right]\>,$

is called a block Kronecker pencil, where

$L_{k}(\lambda):=\begin{bmatrix}-1&\lambda\\\ &-1&\lambda\\\
&&\ddots&\ddots\\\ &&&-1&\lambda\\\
\end{bmatrix}\in\mathbb{F}[\lambda]^{k\times(k+1)}.$

The one-block row and one-block column cases are included, i.e., the second
block row or the second block column can be empty.

It was proved in [15, Theorem 4.2] that any block Kronecker pencil is a strong
linearization of the polynomial matrix

$P(\lambda):=(\Lambda_{\eta}(\lambda)^{T}\otimes I_{p})(\lambda
M_{1}+M_{0})(\Lambda_{\epsilon}(\lambda)\otimes
I_{m})\,\in\mathbb{F}[\lambda]^{p\times m},$ (25)

where $\Lambda_{k}(\lambda)$ was defined in (10). The proof in [15] is a
corollary of the theory of strong block minimal bases pencils. We will see in
this section that another proof easily follows from the approach via
Rosenbrock’s system matrices.

###  6.1 Block Kronecker linearizations as Rosenbrock’s system matrices

Observe that we can write

$L_{\epsilon}(\lambda)\otimes
I_{m}=\left[\begin{array}[]{cccc|c}-I_{m}&\lambda I_{m}&&&\\\ &-I_{m}&\lambda
I_{m}&&\\\ &&\ddots&\ddots\\\ &&&-I_{m}&\lambda
I_{m}\end{array}\right]=:\left[\begin{array}[]{c|c}A_{\epsilon,m}(\lambda)&B_{\epsilon,m}(\lambda)\end{array}\right],$
(26)

and $A_{\epsilon,m}(\lambda)$ is unimodular. Analogously,

$L_{\eta}(\lambda)\otimes I_{p}=\left[\begin{array}[]{cccc|c}-I_{p}&\lambda
I_{p}&&&\\\ &-I_{p}&\lambda I_{p}&&\\\ &&\ddots&\ddots\\\ &&&-I_{p}&\lambda
I_{p}\end{array}\right]=:\left[\begin{array}[]{c|c}A_{\eta,p}(\lambda)&B_{\eta,p}(\lambda)\end{array}\right],$
(27)

and $A_{\eta,p}(\lambda)$ is unimodular. Then, $C_{K}(\lambda)$ can be
partitioned as:

$C_{K}(\lambda)=\left[\begin{array}[]{c;{2pt/2pt}c|c}M_{11}(\lambda)&M_{12}(\lambda)&A_{\eta,p}(\lambda)^{T}\\\
\hdashline[2pt/2pt]M_{21}(\lambda)&M_{22}(\lambda)&B_{\eta,p}(\lambda)^{T}\\\
\hline\cr
A_{\epsilon,m}(\lambda)&B_{\epsilon,m}(\lambda)&0\end{array}\right],$

and we set

$\displaystyle A(\lambda)$
$\displaystyle:=\begin{bmatrix}M_{11}(\lambda)&A_{\eta,p}(\lambda)^{T}\\\
A_{\epsilon,m}(\lambda)&0\end{bmatrix},\quad
B(\lambda):=\begin{bmatrix}M_{12}(\lambda)\\\
B_{\epsilon,m}(\lambda)\end{bmatrix},$ (28) $\displaystyle C(\lambda)$
$\displaystyle:=-\begin{bmatrix}M_{21}(\lambda)&B_{\eta,p}(\lambda)^{T}\end{bmatrix},\quad\text{and}\quad
D(\lambda):=M_{22}(\lambda).$ (29)

Notice that $A(\lambda)$ is unimodular for any $M_{11}(\lambda)$. With the
partition above, we prove in Theorem 6.2 that $C_{K}(\lambda)$ is a linear
polynomial system matrix with unimodular state matrix $A(\lambda)$ and whose
transfer function matrix is the matrix polynomial $P(\lambda)$ in (25).

######  Theorem 6.2.

Let $C_{K}(\lambda)$ be a block Kronecker pencil as in Definition 6.1. Then,
the following statements hold:

  * (a)

The submatrix $A(\lambda)$ of $C_{K}(\lambda)$ as in (28) is unimodular.

  * (b)

The Schur complement of $A(\lambda)$ in $C_{K}(\lambda)$ is the polynomial
matrix $P(\lambda)$ in (25).

  * (c)

$C_{K}(\lambda)$ is a linearization of $P(\lambda)$.

###### Proof.

Statement $\rm(c)$ follows from $\rm(a)$ and $\rm(b)$ and Proposition 3.1.
Since (a) is obvious, it only remains to prove $\rm(b)$. First, we write

$\displaystyle A(\lambda)^{-1}$
$\displaystyle:=\begin{bmatrix}0&A_{\epsilon,m}(\lambda)^{-1}\\\
A_{\eta,p}(\lambda)^{-T}&-A_{\eta,p}(\lambda)^{-T}M_{11}(\lambda)A_{\epsilon,m}(\lambda)^{-1}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}I_{\epsilon m}&0\\\
0&A_{\eta,p}(\lambda)^{-T}\end{bmatrix}\begin{bmatrix}0&I_{\epsilon m}\\\
I_{\eta p}&-M_{11}(\lambda)\end{bmatrix}\begin{bmatrix}I_{\eta p}&0\\\
0&A_{\epsilon,m}(\lambda)^{-1}\end{bmatrix}.$

Now, observe that
$\begin{bmatrix}A_{\epsilon,m}(\lambda)&B_{\epsilon,m}(\lambda)\end{bmatrix}(\Lambda_{\epsilon}(\lambda)\otimes
I_{m})=0$ and, thus,

$A_{\epsilon,m}(\lambda)(\lambda\Lambda_{\epsilon-1}(\lambda)\otimes
I_{m})+B_{\epsilon,m}(\lambda)=0.$

Therefore,

$A_{\epsilon,m}(\lambda)^{-1}B_{\epsilon,m}(\lambda)=-(\lambda\Lambda_{\epsilon-1}(\lambda)\otimes
I_{m}).$

Analogously,

$B_{\eta,p}(\lambda)^{T}A_{\eta,p}(\lambda)^{-T}=-(\lambda\Lambda_{\eta-1}(\lambda)^{T}\otimes
I_{p}).$

Thus, the transfer function matrix of $C_{K}(\lambda)$ with $A(\lambda)$ as
state matrix is, taking into account (28) and (29),

$\displaystyle D(\lambda)+C(\lambda)A(\lambda)^{-1}B(\lambda)$
$\displaystyle=M_{22}(\lambda)-\begin{bmatrix}M_{21}(\lambda)&B_{\eta,p}(\lambda)^{T}\end{bmatrix}\begin{bmatrix}I_{\epsilon,m}&0\\\
0&A_{\eta,p}(\lambda)^{-T}\end{bmatrix}\begin{bmatrix}0&I_{\epsilon m}\\\
I_{\eta p}&-M_{11}(\lambda)\end{bmatrix}\begin{bmatrix}I_{\eta p}&0\\\
0&A_{\epsilon,m}(\lambda)^{-1}\end{bmatrix}\begin{bmatrix}M_{12}(\lambda)\\\
B_{\epsilon,m}(\lambda)\end{bmatrix}$
$\displaystyle=M_{22}(\lambda)-\begin{bmatrix}M_{21}(\lambda)&-(\lambda\Lambda_{\eta-1}(\lambda)^{T}\otimes
I_{p})\end{bmatrix}\begin{bmatrix}0&I_{\epsilon m}\\\ I_{\eta
p}&-M_{11}(\lambda)\end{bmatrix}\begin{bmatrix}M_{12}(\lambda)\\\
-(\lambda\Lambda_{\epsilon-1}(\lambda)\otimes I_{m})\end{bmatrix}$
$\displaystyle=M_{22}(\lambda)+(\lambda\Lambda_{\eta-1}(\lambda)^{T}\otimes
I_{p})M_{12}(\lambda)+M_{21}(\lambda)(\lambda\Lambda_{\epsilon-1}(\lambda)\otimes
I_{m})+(\lambda\Lambda_{\eta-1}(\lambda)^{T}\otimes
I_{p})M_{11}(\lambda)(\lambda\Lambda_{\epsilon-1}(\lambda)\otimes I_{m})$
$\displaystyle=(\Lambda_{\eta}(\lambda)^{T}\otimes
I_{p})\begin{bmatrix}M_{11}(\lambda)&M_{12}(\lambda)\\\
M_{21}(\lambda)&M_{22}(\lambda)\end{bmatrix}(\Lambda_{\epsilon}(\lambda)\otimes
I_{m})=P(\lambda).$

∎

###  6.2 Reversal of block Kronecker linearizations as Rosenbrock’s system
matrices

We can consider the following partition for
$\operatorname{rev}_{1}C_{K}(\lambda):$

$\operatorname{rev}_{1}C_{K}(\lambda)=\left[\begin{array}[]{c|cc}\widehat{M}_{11}(\lambda)&\widehat{M}_{12}(\lambda)&\widehat{B}_{\eta,p}(\lambda)^{T}\\\
\hline\cr\widehat{M}_{21}(\lambda)&\widehat{M}_{22}(\lambda)&\widehat{A}_{\eta,p}(\lambda)^{T}\\\
\widehat{B}_{\epsilon,m}(\lambda)&\widehat{A}_{\epsilon,m}(\lambda)&0\end{array}\right]:=\begin{bmatrix}D_{r}(\lambda)&-C_{r}(\lambda)\\\
B_{r}(\lambda)&A_{r}(\lambda)\end{bmatrix},$ (30)

as a linear polynomial system matrix with state matrix $A_{r}(\lambda)$, where

$\operatorname{rev}_{1}L_{\epsilon}(\lambda)\otimes
I_{m}=\left[\begin{array}[]{c|cccc}-\lambda I_{m}&I_{m}\\\ &-\lambda
I_{m}&I_{m}\\\ &&\ddots&\ddots\\\ &&&-\lambda I_{m}&I_{m}\\\
\end{array}\right]=:\left[\begin{array}[]{cc}\widehat{B}_{\epsilon,m}(\lambda)&\widehat{A}_{\epsilon,m}(\lambda)\end{array}\right],$
(31)

and

$\operatorname{rev}_{1}L_{\eta}(\lambda)\otimes
I_{p}=\left[\begin{array}[]{c|cccc}-\lambda I_{p}&I_{p}\\\ &-\lambda
I_{p}&I_{p}\\\ &&\ddots&\ddots\\\ &&&-\lambda I_{p}&I_{p}\\\
\end{array}\right]=:\left[\begin{array}[]{cc}\widehat{B}_{\eta,p}(\lambda)&\widehat{A}_{\eta,p}(\lambda)\end{array}\right].$
(32)

Then, we have the following result, whose proof is completely analogous to
that of Theorem 6.2 and, so, is omitted.

######  Theorem 6.3.

Let $C_{K}(\lambda)$ be a block Kronecker pencil as in Definition 6.1 and
$P(\lambda)$ be the polynomial matrix in (25). Then, the following statements
hold:

  * (a)

The submatrix $A_{r}(\lambda)$ of $\operatorname{rev}_{1}C_{K}(\lambda)$ as in
(30) is unimodular.

  * (b)

The Schur complement of $A_{r}(\lambda)$ in
$\operatorname{rev}_{1}C_{K}(\lambda)$ is
$\operatorname{rev}_{\eta+\epsilon+1}P(\lambda).$

  * (c)

$C_{K}(\lambda)$ is a strong linearization of $P(\lambda)$.

##  7 Extended block Kronecker linearizations

In this section we consider a more general version of the notion of block
Kronecker linearization [9].

######  Definition 7.1.

Let $\lambda M_{1}+M_{0}$ be an arbitrary pencil and
$Y\in\mathbb{F}^{\varepsilon m\times\varepsilon m}$ and $Z\in\mathbb{F}^{\eta
p\times\eta p}$ be arbitrary constant matrices. Then any pencil of the form

$C_{EK}(\lambda)=\left[\begin{array}[]{c|c}\lambda
M_{1}+M_{0}&(Z(L_{\eta}(\lambda)\otimes I_{p}))^{T}\\\ \hline\cr
Y(L_{\epsilon}(\lambda)\otimes I_{m})&0\end{array}\right]\>$

is called an extended block Kronecker pencil. The one-block row and one-block
column cases are also included, i.e., the second block row or the second block
column can be empty. Note that if $Z=I_{\eta p}$ and $Y=I_{\varepsilon m}$
then $C_{EK}(\lambda)$ is just a block Kronecker pencil.

Extended block Kronecker pencils were introduced in [9, Section 3.3] because
though the family of block Kronecker pencils contains, modulo permutations,
Fiedler pencils [5, 11, 22] and generalized Fiedler pencils [5], it is not
large enough to include the other families of Fiedler-like pencils (Fiedler
pencils with repetition [36] and generalized Fiedler pencils with repetition
[8]). It was proved in [9] that all the Fiedler-like linearizations available
in the literature are included modulo permutations in the family of extended
block Kronecker pencils (which in turn is included in the much wider family of
strong block minimal bases pencils [15]). The proofs of these results require
to choose highly structured matrices $Y$ and $Z$ in $C_{EK}(\lambda)$
depending on the coefficients of the polynomial matrix to be linearized. The
details can be found in [9].

Note that $C_{EK}(\lambda)$ in Definition 7.1 can be written as

$C_{EK}(\lambda)=\mathrm{diag}(I,Y)\,C_{K}(\lambda)\,\mathrm{diag}(I,Z^{T}),$

where $C_{K}(\lambda)$ is a block Kronecker pencil as in Definition 6.1. Thus,
if $Y$ and $Z$ are nonsigular, then we get immediately that $C_{EK}(\lambda)$
is a strong linearization of exactly the same matrix polynomial $P(\lambda)$
in (25) as $C_{K}(\lambda)$. Our purpose in this section is to prove that we
can also write $C_{EK}(\lambda)$ as a polynomial system matrix with unimodular
state matrix and transfer function matrix (25).

###  7.1 Extended block Kronecker linearizations as Rosenbrock’s system
matrices

Recall (26) and (27), and observe that

$Y(L_{\epsilon}(\lambda)\otimes
I_{m})=\left[\begin{array}[]{c|c}YA_{\epsilon,m}(\lambda)&YB_{\epsilon,m}(\lambda)\end{array}\right],$

and $YA_{\epsilon,m}(\lambda)$ is unimodular if $Y$ is invertible.
Analogously,

$Z(L_{\eta}(\lambda)\otimes
I_{p})=\left[\begin{array}[]{c|c}ZA_{\eta,p}(\lambda)&ZB_{\eta,p}(\lambda)\end{array}\right],$

and $ZA_{\eta,p}(\lambda)$ is unimodular if $Z$ is invertible. Then,
$C_{EK}(\lambda)$ can be partitioned as:

$C_{EK}(\lambda)=\left[\begin{array}[]{c;{2pt/2pt}c|c}M_{11}(\lambda)&M_{12}(\lambda)&A_{\eta,p}(\lambda)^{T}
Z^{T}\\\
\hdashline[2pt/2pt]M_{21}(\lambda)&M_{22}(\lambda)&B_{\eta,p}(\lambda)^{T}
Z^{T}\\\ \hline\cr YA_{\epsilon,m}(\lambda)&Y
B_{\epsilon,m}(\lambda)&0\end{array}\right],$

and we set

$\displaystyle\widetilde{A}(\lambda)$
$\displaystyle:=\begin{bmatrix}M_{11}(\lambda)&A_{\eta,p}(\lambda)^{T}Z^{T}\\\
YA_{\epsilon,m}(\lambda)&0\end{bmatrix},\quad\widetilde{B}(\lambda):=\begin{bmatrix}M_{12}(\lambda)\\\
YB_{\epsilon,m}(\lambda)\end{bmatrix},$ (33)
$\displaystyle\widetilde{C}(\lambda)$
$\displaystyle:=-\begin{bmatrix}M_{21}(\lambda)&B_{\eta,p}(\lambda)^{T}Z^{T}\end{bmatrix},\quad\text{and}\quad\widetilde{D}(\lambda):=M_{22}(\lambda).$
(34)

Notice that $\widetilde{A}(\lambda)$ is unimodular if $Y$ and $Z$ are
invertible, for any $M_{11}(\lambda)$. With the partition above, we prove in
Theorem 7.2 that $C_{EK}(\lambda)$ is a linear polynomial system matrix with
unimodular state matrix $\widetilde{A}(\lambda)$ and whose transfer function
matrix is $P(\lambda)$ in (25).

######  Theorem 7.2.

Let $C_{EK}(\lambda)$ be an extended block Kronecker pencil as in Definition
7.1. Assume that $Y$ and $Z$ are invertible. Then, the following statements
hold:

  * (a)

The submatrix $\widetilde{A}(\lambda)$ of $C_{EK}(\lambda)$ as in (33) is
unimodular.

  * (b)

The Schur complement of $\widetilde{A}(\lambda)$ in $C_{EK}(\lambda)$ is the
polynomial matrix $P(\lambda)$ in (25).

  * (c)

$C_{EK}(\lambda)$ is a linearization of $P(\lambda)$.

###### Proof.

Statement $\rm(c)$ follows from $\rm(a)$ and $\rm(b)$ and Proposition 3.1.
Since (a) is obvious, it only remains to prove $\rm(b)$. For that, we write
the matrices in (33) as follows:

$\displaystyle\widetilde{A}(\lambda)$ $\displaystyle=\begin{bmatrix}I_{\eta
p}&0\\\ 0&Y\end{bmatrix}A(\lambda)\begin{bmatrix}I_{\epsilon m}&0\\\
0&Z^{T}\end{bmatrix},\quad\widetilde{B}(\lambda)=\begin{bmatrix}I_{\eta
p}&0\\\ 0&Y\end{bmatrix}B(\lambda),$ $\displaystyle\widetilde{C}(\lambda)$
$\displaystyle=C(\lambda)\begin{bmatrix}I_{\epsilon m}&0\\\
0&Z^{T}\end{bmatrix},\quad\text{and}\quad\widetilde{D}(\lambda)=D(\lambda),$

where $A(\lambda)$, $B(\lambda)$, $C(\lambda)$ and $D(\lambda)$ are as in (28)
and (29). Then, the transfer function matrix of $C_{EK}(\lambda)$ with
$\widetilde{A}(\lambda)$ as state matrix is:

$\displaystyle\widetilde{D}(\lambda)+\widetilde{C}(\lambda)\widetilde{A}(\lambda)^{-1}\widetilde{B}(\lambda)$
$\displaystyle=D(\lambda)+C(\lambda)\begin{bmatrix}I_{\epsilon m}&0\\\
0&Z^{T}\end{bmatrix}\begin{bmatrix}I_{\epsilon m}&0\\\
0&Z^{-T}\end{bmatrix}A(\lambda)^{-1}\begin{bmatrix}I_{\eta p}&0\\\
0&Y^{-1}\end{bmatrix}\begin{bmatrix}I_{\eta p}&0\\\
0&Y\end{bmatrix}B(\lambda)$
$\displaystyle=D(\lambda)+C(\lambda)A(\lambda)^{-1}B(\lambda)=P(\lambda),$

as in the proof of Theorem 6.2. ∎

###  7.2 Reversal of extended block Kronecker linearizations as Rosenbrock’s
system matrices

We can consider the following partition for
$\operatorname{rev}_{1}C_{EK}(\lambda):$

$\operatorname{rev}_{1}C_{EK}(\lambda)=\left[\begin{array}[]{c|cc}\widehat{M}_{11}(\lambda)&\widehat{M}_{12}(\lambda)&\widehat{B}_{\eta,p}(\lambda)^{T}Z^{T}\\\
\hline\cr\widehat{M}_{21}(\lambda)&\widehat{M}_{22}(\lambda)&\widehat{A}_{\eta,p}(\lambda)^{T}Z^{T}\\\
Y\widehat{B}_{\epsilon,m}(\lambda)&Y\widehat{A}_{\epsilon,m}(\lambda)&0\end{array}\right]:=\begin{bmatrix}\widetilde{D}_{r}(\lambda)&-\widetilde{C}_{r}(\lambda)\\\
\widetilde{B}_{r}(\lambda)&\widetilde{A}_{r}(\lambda)\end{bmatrix},$ (35)

as a linear polynomial system matrix with state matrix
$\widetilde{A}_{r}(\lambda)$, where

$Y(\operatorname{rev}_{1}L_{\epsilon}(\lambda)\otimes
I_{m})=\left[\begin{array}[]{cc}Y\widehat{B}_{\epsilon,m}(\lambda)&Y\widehat{A}_{\epsilon,m}(\lambda)\end{array}\right],$

and

$Z(\operatorname{rev}_{1}L_{\eta}(\lambda)\otimes
I_{p})=\left[\begin{array}[]{cc}Z\widehat{B}_{\eta,p}(\lambda)&Z\widehat{A}_{\eta,p}(\lambda)\end{array}\right],$

by using the notation in (31) and (32), respectively. Then, we have the
following result, whose proof is omitted since it easily follows from Theorem
6.3.

######  Theorem 7.3.

Let $C_{EK}(\lambda)$ be an extended block Kronecker pencil as in Definition
7.1 and $P(\lambda)$ be the polynomial matrix in (25). Assume that $Y$ and $Z$
are invertible. Then, the following statements hold:

  * (a)

The submatrix $\widetilde{A}_{r}(\lambda)$ of
$\operatorname{rev}_{1}C_{EK}(\lambda)$ as in (35) is unimodular.

  * (b)

The Schur complement of $\widetilde{A}_{r}(\lambda)$ in
$\operatorname{rev}_{1}C_{EK}(\lambda)$ is
$\operatorname{rev}_{\eta+\epsilon+1}P(\lambda)$.

  * (c)

$C_{EK}(\lambda)$ is a strong linearization of $P(\lambda)$.

##  8 A note on the construction of linearizations for rational matrices from
linear system matrices of their polynomial parts

By the division algorithm for polynomials, any scalar rational function
$r(\lambda)$ can be uniquely written as
$r(\lambda)=p(\lambda)+r_{sp}(\lambda),$ where $p(\lambda)$ is a polynomial
and $r_{sp}(\lambda)$ is a strictly proper rational function. That is, the
degree of the denominator of $r_{sp}(\lambda)$ is strictly larger than the
degree of its numerator. Therefore, any rational matrix $R(\lambda)$ can be
expressed uniquely as

$R(\lambda)=P(\lambda)+R_{sp}(\lambda),$ (36)

where $P(\lambda)$ is a polynomial matrix and $R_{sp}(\lambda)$ is a strictly
proper rational matrix. That is, the entries of $R_{sp}(\lambda)$ are strictly
proper rational functions.

Recently, several papers have investigated the problem of constructing a
linearization of a rational matrix $R(\lambda)$ from a linearization of
$P(\lambda)$ and a minimal state-space realization of $R_{sp}(\lambda)$ [31].
See, for instance, [1, 2, 4, 16, 32] among other references on this topic.
Often, the development of such constructions has required considerable
theoretical work, since it was not obvious how to merge the linearization of
$P(\lambda)$ with the minimal state-space realization of $R_{sp}(\lambda)$. In
contrast, if one considers linearizations of $P(\lambda)$ that are
Rosenbrock’s system matrices with unimodular state matrices and transfer
function matrices equal to $P(\lambda)$, the construction is very easy. For
this purpose, we consider on the one hand a linear Rosenbrock’s system matrix

$L(\lambda)=\begin{bmatrix}A(\lambda)&B(\lambda)\\\
-C(\lambda)&D(\lambda)\end{bmatrix},$

with unimodular state matrix $A(\lambda)$, and transfer function matrix equal
to $P(\lambda)$. That is,

$P(\lambda)=D(\lambda)+C(\lambda)A(\lambda)^{-1}B(\lambda).$

On the other hand, we consider a minimal state-space realization

$R_{sp}(\lambda)=C_{s}(\lambda I_{s}-A_{s})^{-1}B_{s}$

of the strictly proper part $R_{sp}(\lambda)$. Then, we construct the
following pencil:

$\mathcal{L}(\lambda)=\left[\begin{array}[]{cc|c}(\lambda
I_{s}-A_{s})&0&B_{s}\\\ 0&A(\lambda)&B(\lambda)\\\ \hline\cr-
C_{s}&-C(\lambda)&D(\lambda)\end{array}\right].$

We obtain that $\mathcal{L}(\lambda)$ is a linear minimal polynomial system
matrix of $R(\lambda)$ in (36), with state matrix
$\left[\begin{smallmatrix}(\lambda I_{s}-A_{s})&0\\\
0&A(\lambda)\end{smallmatrix}\right]$. Thus, by Theorem 1.2,
$\mathcal{L}(\lambda)$ contains the information about finite poles and zeros
of $R(\lambda)$, and is a linearization of $R(\lambda)$ in the sense of [4,
Definition 3.2]. More information about different definitions of
linearizations of rational matrices and how to construct linear polynomial
system matrices that also preserve the pole and zero information at infinity,
i.e., the pole and zero information at $0$ of $R(1/\lambda)$, can be found,
for instance, in [4, 17, 18, 19].

##  9 Conclusions and lines of future research

The main message of this paper in that in the analysis of a pencil
$L(\lambda)$ that may be a linearization of a matrix polynomial, it is worth
looking for a unimodular submatrix $A(\lambda)$ of $L(\lambda)$ and viewing
$L(\lambda)$ as a Rosenbrock’s system matrix with state matrix $A(\lambda)$.
In the first place, this allows to identify a matrix polynomial $P(\lambda)$
for which $L(\lambda)$ is a linearization just by computing the Schur
complement of $A(\lambda)$ in $L(\lambda)$. Other advantages of this approach
are that it may yield simplified alternative proofs that certain well known
linearizations are indeed linearizations, it gives rise to simple recovery
rules for eigenvectors and to simple constructions of linearizations of
rational matrices whose polynomial part is $P(\lambda)$. This approach applied
to the reversal of $L(\lambda)$ can also be used to prove that $L(\lambda)$ is
a strong linearization of $P(\lambda)$, though it usually requires to identify
a different submatrix in $\operatorname{rev}_{1}L(\lambda)$. One possible line
of future research in this context is to apply the Rosenbrock’s system matrix
approach in the study of $\ell$-ifications of polynomial matrices [12, 13, 14,
20]. Another connected problem that deserves to be investigated is that it may
be possible to identify in a pencil several unimodular submatrices, possibly
with different sizes (think, for instance, in the Frobenius companion form),
which will give rise to several different matrix polynomials with the same
eigenvalue information. Finally, we emphasize that this paper has connected
two very important historical tools in the theory of rational and polynomial
matrices: Rosenbrock’s system matrices and Gohberg, Lancaster and Rodman’s
linearizations and strong linearizations.

## References

  * [1] R. Alam, N. Behera, Linearizations for rational matrix functions and Rosenbrock system polynomials, SIAM J. Matrix Anal. Appl. 37 (2016) 354–380.
  * [2] R. Alam, N. Behera, Generalized Fiedler pencils for rational matrix functions, SIAM J. Matrix Anal. Appl. 39 (2018) 587–610.
  * [3] A. Amiraslani, R.M. Corless, P. Lancaster, Linearization of matrix polynomials expressed in polynomial bases, IMA J. Numer. Anal. 29 (2009) 141–157.
  * [4] A. Amparan, F. M. Dopico, S. Marcaida, I. Zaballa, Strong linearizations of rational matrices, SIAM J. Matrix Anal. Appl. 39 (2018) 1670–1700.
  * [5] E. N. Antoniou, S. Vologiannidis, A new family of companion forms of polynomial matrices, Electron. J. Linear Algebra 11 (2004) 78–87.
  * [6] S. Barnett, Polynomials and Linear Control Systems, Marcel Dekker Inc., New York (1983).
  * [7] M. I. Bueno, K. Curlett, S. Furtado, Structured strong linearizations from Fiedler pencils with repetition I, Linear Algebra Appl. 460 (2014) 51–80.
  * [8] M. I. Bueno, F. M. Dopico, S. Furtado, M. Rychnovsky, Large vector spaces of block-symmetric strong linearizations of matrix polynomials, Linear Algebra Appl. 477 (2015) 165–210.
  * [9] M. I. Bueno, F. M. Dopico, J. Pérez, R. Saavedra, B. Zykoski, A simplified approach to Fiedler-like pencils via block minimal bases pencils, Linear Algebra Appl. 547 (2018) 45–104.
  * [10] M. I. Bueno, S. Furtado, Structured strong linearizations from Fiedler pencils with repetition II, Linear Algebra Appl. 463 (2014) 282–321.
  * [11] F. De Terán, F. M. Dopico, D. S. Mackey, Fiedler companion linearizations and the recovery of minimal indices, SIAM J. Matrix Anal. Appl. 31 (2010) 2181–2204.
  * [12] F. De Terán, F. M. Dopico, D. S. Mackey, Spectral equivalence of matrix polynomials and the index sum theorem, Linear Algebra Appl. 459 (2014) 264–333.
  * [13] F. De Terán, F. M. Dopico, P. Van Dooren, Constructing strong $\ell$-ifications from dual minimal bases, Linear Algebra Appl. 495 (2016) 344-372.
  * [14] F. De Terán, C. Hernando, J. Pérez, Structured strong $\ell$-ifications for structured matrix polynomials in the monomial basis, Electron. J. Linear Algebra 37 (2021) 35-71.
  * [15] F. M. Dopico, P. W. Lawrence, J. Pérez, P. Van Dooren, Block Kronecker linearizations of matrix polynomials and their backward errors, Numer. Math. 140 (2018) 373–426. Extended version available as MIMS EPrint 2016.34, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, 2016.
  * [16] F. M. Dopico, S. Marcaida, M. C. Quintana, Strong linearizations of rational matrices with polynomial part expressed in an orthogonal basis, Linear Algebra Appl. 570 (2019) 1–45.
  * [17] F. M. Dopico, S. Marcaida, M. C. Quintana, P. Van Dooren,  Local linearizations of rational matrices with application to rational approximations of nonlinear eigenvalue problems, Linear Algebra Appl. 604 (2020) 441–475.
  * [18] F. M. Dopico, M. C. Quintana, P. Van Dooren, Linear system matrices of rational transfer functions, “Realization and Model Reduction of Dynamical Systems, A Festschrift in honor of the 70th birthday of Thanos Antoulas”, Springer (2022) 95–113.
  * [19] F. M. Dopico, M. C. Quintana P. Van Dooren, Strongly minimal self-conjugate linearizations for polynomial and rational matrices, SIAM J. Matrix Anal. Appl. 43 (2022) 1354-1381.
  * [20] F. M. Dopico, J. Pérez, P. Van Dooren, Block minimal bases $\ell$-ifications of matrix polynomials, Linear Algebra Appl. 562 (2019) 163-204.
  * [21] H. Faßbender, P. Saltenberger, On vector spaces of linearizations for matrix polynomials in orthogonal bases, Linear Algebra Appl. 525 (2017) 59–83.
  * [22] M. Fiedler, A note on companion matrices, Linear Algebra Appl. 372 (2003) 325–331.
  * [23] I. Gohberg, M. A. Kaashoek, P. Lancaster,  General theory of regular matrix polynomials and band Toeplitz operators,  Integral Equations and Operator Theory 11 (1988) 776–882.
  * [24] I. Gohberg, P. Lancaster, L. Rodman,  Matrix Polynomials,  SIAM Publications, 2009.  Originally published: Academic Press, New York, 1982.
  * [25] N. J. Higham, D. S. Mackey, N. Mackey, F. Tisseur, Symmetric linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl. 29 (2006) 143–159.
  * [26] P. Lawrence, J. Pérez, Constructing strong linearizations of matrix polynomials expressed in the Chebyshev bases, SIAM. J. Matrix Anal. Appl. 38 (2017) 683–709.
  * [27] D. S. Mackey, N. Mackey, C. Mehl, V. Mehrmann, Vectors spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl. 28 (2006) 971–1004.
  * [28] D. S. Mackey, N. Mackey, C. Mehl, V. Mehrmann, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl. 28 (2006) 1029–1051.
  * [29] B. McMillan, Introduction to formal realizability theory II, Bell System Tech. J. 31 (1952) 541–600.
  * [30] V. Noferini, J. Pérez, Fiedler-comrade and Fiedler–Chebyshev pencils, SIAM J. Matrix Anal. Appl. 37 (2016) 1600–1624.
  * [31] H. H. Rosenbrock, State-space and Multivariable Theory, Thomas Nelson and Sons, London, 1970.
  * [32] Y. Su, Z. Bai, Solving rational eigenvalue problems via linearization, SIAM J. Matrix Anal. Appl. 32 (2011) 201–216.
  * [33] R. Van Beeumen, K. Meerbergen, W. Michiels,  Compact rational Krylov methods for nonlinear eigenvalue problems, SIAM J. Matrix Anal Appl. 36 (2015) 820–838.
  * [34] P. Van Dooren, The generalized eigenstructure problem in linear system theory, IEEE Trans. Aut. Contr. 26(1) (1981) 111–129.
  * [35] P. Van Dooren, P. Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983) 545–579.
  * [36] S. Vologiannidis, E. N. Antoniou, A permuted factors approach for the linearization of polynomial matrices, Math. Control Signals Syst. 22 (2011) 317–342.