Compound matrices in systems and control theory

Let $A\in\mathbb{R}^{n\times n}$. Fix $k\in\{1,\dots,n\}$. The $k$-multiplicative and $k$-additive compounds of $A$ play an important role in several fields of applied mathematics. Recently, there is a growing interest in the applications of these compounds, and their generalizations, in systems and control theory (see, e.g. [43, 42, 21, 1, 5, 28, 44, 40, 2, 41, 13, 16, 14, 17, 15]).

This tutorial paper reviews the $k$-compounds, focusing on their geometric interpretations, and surveys some of their recent applications in systems and control theory, including $k$-positive systems, $k$-cooperative systems, and $k$-contracting systems.

The results described here are known, albeit never collected in a single paper. The only exception is the new generalization principle described in Section V.

We use standard notation. For a set $S$, $\operatorname{int}(S)$ is the interior of $S$. For scalars $\lambda_{i}$, $i\in\{1,\dots,n\}$, $\operatorname{diag}(\lambda_{1},\dots,\lambda_{n})$ is the $n\times n$ diagonal matrix with diagonal entries $\lambda_{i}$. Column vectors [matrices] are denoted by small [capital] letters. For a matrix $A$, $A^{T}$ is the transpose of $A$. For a square matrix $B$, $\operatorname{tr}(B)$ [$\det(B)$] is the trace [determinant] of $B$. $B$ is called Metzler if all its off-diagonal entries are non-negative. The positive orthant in $\mathbb{R}^{n}$ is $\mathbb{R}^{n}_{+}=\{x\in\mathbb{R}^{n}:x_{i}\geq 0,\;i=1,\dots,n\}$.

$k$-compound matrices provide information on the evolution of $k$-dimensional polygons subject to a linear time-varying dynamics. To explain this in a simple setting, consider the LTI system:

with $\lambda_{i}\in\mathbb{R}$ and $x:\mathbb{R}_{+}\to\mathbb{R}^{3}$. Let $e^{i}$, $i=1,2,3$, denote the $i$th canonical vector in $\mathbb{R}^{3}$. For $x(0)=e^{i}$ we have $x(t)=\exp(\lambda_{i}t)x(0)$. Thus, $\exp(\lambda_{i}t)$ describes the rate of evolution of the line $e^{i}$ subject to (1). What about 2D areas? Let $S\subset\mathbb{R}^{3}$ denote the square generated by $e^{i}$ and $e^{j}$, with $i\not=j$. Then $S(t):=x(t,S)$ is the rectangle generated by $\exp(\lambda_{i}t)e^{i}$ and $\exp(\lambda_{j}t)e^{j}$, so the area of $S(t)$ is $\exp((\lambda_{i}+\lambda_{j})t)$. Similarly, if $B\subset\mathbb{R}^{3}$ is the 3D box generated by $e^{1},e^{2}$, and $e^{3}$ then the volume of $B(t):=x(t,B)$ is $\exp((\lambda_{1}+\lambda_{2}+\lambda_{3})t)$ (see Fig. 1).

Since $\exp(At)=\operatorname{diag}(\exp(\lambda_{1}t),\exp(\lambda_{2}t),\exp(\lambda_{3}t))$, this discussion suggests that it may be useful to have a $3\times 3$ matrix whose eigenvalues are the sums of any two eigenvalues of $\exp(At)$, and a $1\times 1$ matrix whose eigenvalue is the sum of the three eigenvalues of $\exp(At)$. With this geometric motivation in mind, we turn to recall the notions of the multiplicative and additive compounds of a matrix. For more details and proofs, see e.g. [11, Ch. 6][33].

Let $A\in\mathbb{C}^{n\times m}$. Fix $k\in\{1,\dots,\min\{n,m\}\}$. Let $Q(k,n)$ denote the set of increasing sequences of $k$ integers in $\{1,\dots,n\}$, ordered lexicographically. For example,

For $\alpha\in Q(k,n),\beta\in Q(k,m)$, let $A[\alpha|\beta]$ denote the $k\times k$ submtarix obtained by taking the entries of $A$ in the rows indexed by $\alpha$ and the columns indexed by $\beta$. For example

The minor of $A$ corresponding to $\alpha,\beta$ is $A(\alpha|\beta):=\det(A[\alpha|\beta])$. For example, $Q(n,n)$ includes the single set $\alpha=\{1,\dots,n\}$ and $A(\alpha|\alpha)=\det(A)$.

For example, if $n=m=3$ and $k=2$ then

In particular, Definition 1 implies that $A^{(1)}=A$, and if $n=m$ then $A^{(n)}=\det(A)$.

Let $A\in\mathbb{C}^{n\times m},\;B\in\mathbb{C}^{m\times p}$. The Cauchy-Binet Formula (see e.g. [12]) asserts that for any $k\in\{1,\dots,\min\{n,m,p\}\}$,

Hence the term multiplicative compound. Note that for $n=m=p$, Eq. (2) with $k=n$ reduces to the familiar formula $\det(AB)=\det(A)\det(B)$.

Let $I_{s}$ denote the $s\times s$ identity matrix. Definition 1 implies that $I_{n}^{(k)}=I_{r}$, where $r:=\binom{n}{k}$. Hence, if $A\in\mathbb{R}^{n\times n}$ is non-singular then $(AA^{-1})^{(k)}=I_{r}$ and combining this with (2) yields $(A^{-1})^{(k)}=(A^{(k)})^{-1}$. In particular, if $A$ is non-singular then so is $A^{(k)}$.

The $k$-multiplicative compound has an important spectral property. For $A\in\mathbb{C}^{n\times n}$, let $\lambda_{i}$, $i=1,\dots,n$, denote the eigenvalues of $A$. Then the eigenvalues of $A^{(k)}$ are all the products

For example, suppose that $n=3$ and $A=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\ 0&a_{22}&a_{23}\\ 0&0&a_{33}\end{bmatrix}.$ Then a calculation gives

so, clearly, the eigenvalues of $A^{(2)}$ are of the form (3).

Note that this implies that $A^{[k]}=\frac{d}{d\epsilon}(\exp(A\epsilon))^{(k)}|_{\epsilon=0}$, and also that

In other words, $A^{[k]}$ is the first-order term in the Taylor expansion of $(I+\epsilon A)^{(k)}$.

Let $\lambda_{i}$, $i=1,\dots,n$, denote the eigenvalues of $A$. Then the eigenvalues of $(I+\epsilon A)^{(k)}$ are the products $\prod_{\ell=1}^{k}(1+\epsilon\lambda_{i_{\ell}})$, and (4) implies that the eigenvalues of $A^{[k]}$ are all the sums

Another important implication of the definitions above is that for any $A,B\in\mathbb{C}^{n\times n}$ we have

This justifies the term additive compound. Moreover, the mapping $A\to A^{[k]}$ is linear.

The following result gives a useful explicit formula for $A^{[k]}$ in terms of the entries $a_{ij}$ of $A$. Recall that any entry of $A^{(k)}$ is a minor $A(\alpha|\beta)$. Thus, it is natural to index the entries of $A^{(k)}$ and $A^{[k]}$ using $\alpha,\beta\in Q(k,n)$.

Note that Prop. 1 implies in particular that $A^{[n]}=\operatorname{tr}(A)$.

The next section describes applications of compound matrices for dynamical systems described by ODEs. For more details and proofs, see [33, 29].

Fix an interval $[a,b]\in\mathbb{R}$. Let $A:[a,b]\to\mathbb{R}^{n\times n}$ be a continuous matrix function, and consider the LTV system:

The solution is given by $x(t)=\Phi(t,a)x(a)$, where $\Phi(t,a)$ is the solution at time $t$ of the matrix differential equation

Fix $k\in\{1,\dots,n\}$ and let $r:=\binom{n}{k}$. A natural question is: how do the $k$-order minors of $\Phi(t)$ evolve in time? The next result provides a beautiful formula for the evolution of $\Phi^{(k)}(t):=(\Phi(t))^{(k)}$.

Thus, the $k\times k$ minors of $\Phi$ also satisfy an LTV. In particular, if $A(t)\equiv A$ and $a=0$ then $\Phi(t)=\exp(At)$ so $\Phi^{(k)}(t)=(\exp(At))^{(k)}$ and (7) gives

Note also that for $k=n$, Prop. 2 yields

which is the Abel-Jacobi-Liouville identity.

Roughly speaking, Prop. 2 implies that under the LTV dynamics (5), $k$-dimensional polygons evolve according to the dynamics (7).

We now turn to consider the nonlinear system:

For the sake of simplicity, we assume that the initial time is zero, and that the system admits a convex and compact state-space $\Omega$. We also assume that $f\in C^{1}$. The Jacobian of the vector field $f$ is $J(t,x):=\frac{\partial}{\partial x}f(t,x)$.

Compound matrices can be used to analyze (8) by using an LTV called the variational equation associated with (8). To define it, fix $a,b\in\Omega$. Let $z(t):=x(t,a)-x(t,b)$, and for $s\in[0,1]$, let $\gamma(s):=sx(t,a)+(1-s)x(t,b)$, i.e. the line connecting $x(t,a)$ and $x(t,b)$. Then

and this gives the variational equation:

where

We can use the results above to describe a powerful approach for deriving useful “$k$-generalizations” of important classes of dynamical systems including cooperative systems [36], contracting systems [3, 24], and diagonally stable systems [20].

Consider the LTV (5). Suppose that $A(t)$ satisfies a specific property, e.g. property may be that $A(t)$ is Metzler for all $t$ (so the LTV is positive) or that $\mu(A(t))\leq-\eta<0$ for all $t$, where $\mu:\mathbb{R}^{n\times n}\to\mathbb{R}$ is a matrix measure (so the LTV is contracting). Fix $k\in\{1,\dots,n\}$. We say that the LTV satisfies $k$-property if $A^{[k]}$ (rather than $A$) satisfies property. For example, the LTV is $k$-positive if $A^{[k]}(t)$ is Metzler for all $t$; the LTV is $k$-contracting if $\mu(A^{[k]}(t))\leq-\eta<0$ for all $t$, and so on.

This generalization approach makes sense for two reasons. First, when $k=1$, $A^{[k]}$ reduces to $A^{[1]}=A$, so $k$-property is clearly a generalization of property. Second, we know that $A^{[k]}$ has a clear geometric meaning, as it describes the evolution of $k$-dimensional polygons along the dynamics.

The same idea can be applied to the nonlinear system (8) using the variational equation (9). For example, if $\mu(J(t,x))\leq-\eta<0$ for all $t\geq 0$ and $x\in\Omega$ then (8) is contracting: the distance between any two solutions (in the norm that induced $\mu$) decays at an exponential rate. If we replace this by the condition $\mu(J^{[k]}(t,x))\leq-\eta<0$ for all $t\geq 0$ and $x\in\Omega$ then (8) is called $k$-contracting. Roughly speaking, this means that the volume of $k$-dimensional polygons decays to zero exponentially along the flow of the nonlinear system. We now turn to describe several such $k$-generalizations.

$k$-contracting systems were introduced in [42] (see also the unpublished preprint [26] for some preliminary ideas). For $k=1$ these reduce to contracting systems. This generalization was motivated in part by the seminal work of Muldowney [29] who considered nonlinear systems that, in the new terminology, are $2$-contracting. He derived several interesting results for time-invariant $2$-contracting systems. For example, every bounded trajectory of a time-invariant, nonlinear, $2$-contracting system converges to an equilibrium (but, unlike in the case of contracting systems, the equilibrium is not necessarily unique).

For the sake of simplicity, we introduce the ideas in the context of an LTV system. The analysis of nonlinear systems is based on assuming that their variational equation is a $k$-contracting LTV.

Recall that a vector norm $|\cdot|:\mathbb{R}^{n}\to\mathbb{R}_{+}$ induces a matrix norm $||\cdot||:\mathbb{R}^{n\times n}\to\mathbb{R}_{+}$ by:

and a matrix measure $\mu(\cdot):\mathbb{R}^{n\times n}\to\mathbb{R}$ by:

For $p\in\{1,2,\infty\}$, let $|\cdot|_{p}:\mathbb{R}^{n}\to\mathbb{R}_{+}$ denote the $L_{p}$ vector norm, that is, $|x|_{1}:=\sum_{i=1}^{n}|x_{i}|$, $|x|_{2}:=\sqrt{x^{T}x}$, and $|x|_{\infty}:=\max_{i\in\{1,\dots,n\}}|x_{i}|$. The induced matrix measures are [39]:

where $\lambda_{i}(S)$ denotes the $i$-th largest eigenvalue of the symmetric matrix $S$, that is,

Note that for $k=1$ condition (12) reduces to the standard infinitesimal condition for contraction [3]. For the $L_{p}$ norms, with $p\in\{1,2,\infty\}$, this condition is easy to check using the explicit expressions for $\mu_{1}$, $\mu_{2}$, and $\mu_{\infty}$. This carries over to $k$-contraction, as combining Prop. 1 with (11) gives [29]:

For $k=n$, $A^{[n]}$ is the scalar $\operatorname{tr}(A)$, so condition (12) becomes $\operatorname{tr}(A(t))\leq-\eta<0$ for all $t\geq 0$.

Combining Coppel’s inequality [6] with (7) yields the following result.

Geometrically, this means that under the LTV dynamics the volume of $k$-dimensional polygons converges to zero exponentially. The next example illustrates this.

As noted above, time-invariant $2$-contracting systems have a “well-odered” asymptotic behaviour [29, 23], and this has been used to derive a global analysis of important models from epidemiology (see, e.g. [22]). A recent paper [30] extended some of these results to systems that are not necessarily $2$-contracting, but can be represented as the serial interconnections of $k$-contracting systems, with $k\in\{1,2\}$.

A recent paper [44] defined a generalizations called the $\alpha$-multiplicative compound and $\alpha$-additive compound of a matrix, where $\alpha$ is a real number. Let $A\in\mathbb{C}^{n\times n}$ be non-singular. If $\alpha=k+s$, where $k\in\{1,\dots,n-1\}$ and $s\in(0,1)$ then the $\alpha$-multiplicative of $A$ is defined by:

where $\otimes$ denotes the Kronecker product. This is a kind of “multiplicative interpolation” between $A^{(k)}$ and $A^{(k+1)}$. For example, $A^{(2.1)}=(A^{(2)})^{0.9}\otimes(A^{(3)})^{0.1}$. The $\alpha$-additive compound is defined just like the $k$-additive compound, that is,

and it was shown in [44] that this yields

where $\oplus$ denotes the Kronecker sum.

The system (8) is called $\alpha$-contracting w.r.t. the norm $|\cdot|$ if

for all $t\geq 0$ and all $x$ in the state space [44].

Using this notion, it is possible to restate the seminal results of Douady and Oesterlé [7] as follows.

Roughly speaking, the dynamics contracts sets with a larger Hausdorff dimension.

The next example, adapted from [44], shows how these notions can be used to “de-chaotify” a nonlinear dynamical system by feedback.

Ref. [40] introduced the notions of $k$-positive and $k$-cooperative systems. The LTV (5) is called $k$-positive if $A^{[k]}(t)$ is Metzler for all $t$. For $k=1$ this reduces to requiring that $A(t)$ is Metzler for all $t$. In this case the system is positive i.e. the flow maps $\mathbb{R}^{n}_{+}$ to $\mathbb{R}^{n}_{+}$ (and also $\mathbb{R}^{n}_{-}:=-\mathbb{R}^{n}_{+}$ to $\mathbb{R}^{n}_{-}$) [10]. In other words, the flow maps the set of vectors with zero sign variations to itself.

$k$-positive systems map the set of vectors with up to $k-1$ sign variations to itself. To explain this, we recall some definitions and results from the theory of totally positive (TP) matrices, that is, matrices whose minors are all positive [9, 31].

For a vector $x\in\mathbb{R}^{n}\setminus\{0\}$, let $s^{-}(x)$ denote the number of sign variations in $x$ after deleting all its zero entries. For example, $s^{-}(\begin{bmatrix}-1&0&0&2&-3\end{bmatrix}^{T})=2$. We define $s^{-}(0):=0$. For a vector $x\in\mathbb{R}^{n}$, let $s^{+}(x)$ denote the maximal possible number of sign variations in $x$ after setting every zero entry in $x$ to either $-1$ or $+1$. For example, $s^{+}(\begin{bmatrix}-1&0&0&2&-3\end{bmatrix}^{T})=4$. These definitions imply that $0\leq s^{-}(x)\leq s^{+}(x)\leq n-1$, for all $x\in\mathbb{R}^{n}.$

For any $k\in\{1,\dots,n\}$, define the sets

In other words, these are the sets of all vectors with up to $k-1$ sign variations. Then $P_{-}^{k}$ is closed, and it can be shown that $P_{+}^{k}=\operatorname{int}(P_{-}^{k})$. For example,