So the only way in which vectors in $\{(w_W^j, w_{\dot{W}}^{j+1}), j = 0, 1, 2, \dots, k-1\}$ can be linearly combined to yield a vector of the kind $(f_W, g_{\dot{W}})$, with $f_W \in \mathcal{Y}_W^{com}$, is through the trivial linear combination, which means that $g_{\dot{W}} \in (\mathcal{Y}_W^{com})_{\dot{W}}$.

Therefore, $\mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W} \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$. By the definition of $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$, this means $\mathcal{Y}_W^{com} = (\mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W})_W$.

It is LSG since $\mathcal{Y}_{\dot{W}\dot{W}}^{start} \times W \supseteq \mathcal{Y}_W^{com} = (\mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W})_W$.

Thus $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$ is a genop with $\mathcal{Y}_W = \mathcal{Y}_{\dot{W}\dot{W}}^{start} \circ W \supseteq (\mathcal{Y}_{\dot{W}\dot{W}}^{start} \circ \dot{W})_W, (\mathcal{Y}_{\dot{W}\dot{W}}^{start} \times W)_{\dot{W}} \supseteq \mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W} = (\mathcal{Y}_W^{com})_{\dot{W}}$.

**Definition 80.** The basic sequence $\{w_W^j, j = 0, 1, 2, \dots, k\}$ output by the algorithm is referred to as a basic sequence for the genop $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$ contained in the genaut $\mathcal{Y}_{\dot{W}\dot{W}}^u$, while the genop $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$ ($\equiv \text{sp}\{(w_W^j, w_{\dot{W}}^{j+1}), j = 0, 1, 2, \dots, k-1\} + (\mathcal{Y}_W^{com} \oplus (\mathcal{Y}_W^{com})_{\dot{W}})$) is the unique genop contained in the genaut $\mathcal{Y}_{\dot{W}\dot{W}}^u$ for which $\{w_W^j, j = 0, 1, 2, \dots, k\}$ is a basic sequence. We will refer to this genop as the genop of the basic sequence.

**Remark 7.** Every genop does not have a basic sequence. A genop having a basic sequence is analogous to a matrix $A$ for which there exists a vector $w$ in its domain whose minimal annihilating polynomial is the minimal annihilating polynomial of $A$.

**Claim:** Let $w_W^k + d_1 w_W^{k-1} + \dots + d_k w_W^0 \in \mathcal{Y}_W^{com}$ and let $w_W^t \notin \text{sp}\{w_W^{t-1}, \dots, w_W^0\} + \mathcal{Y}_W^{com}, t < k$. Then the polynomial $p_{\text{start}}(s) = s^k + d_1 s^{k-1} + \dots + d_k$ is the minimal annihilating polynomial for $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$.

To prove the claim, we need to show that

$p_{\text{start}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) := (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k)} +_{\dot{w}} d_1^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k-1)} +_{\dot{w}} \dots +_{\dot{w}} d_{k-1}^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) +_{\dot{w}} d_k^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)}$ is decoupled and if $p'(s)$ has degree lower than that of $p_{\text{start}}(s)$, then $p'(\mathcal{Y}_{\dot{W}\dot{W}}^{start})$ is not decoupled.

Since $\mathcal{Y}_{\dot{W}\dot{W}}^{start}$ is a genop, by Lemma 66, we have that for any polynomial $p(s)$,
$$p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \circ W = \mathcal{Y}_{\dot{W}\dot{W}}^{start} \circ W = \mathcal{Y}_W, \quad p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \times \dot{W} = \mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W} = (\mathcal{Y}_W^{com})_{\dot{W}}.$$

This means that $p(\mathcal{Y}_{\dot{W}\dot{W}}^{start})$ is decoupled iff
$$p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \circ W \leftrightarrow p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) = \mathcal{Y}_W \leftrightarrow p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \subseteq p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \times \dot{W} = \mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W} = (\mathcal{Y}_W^{com})_{\dot{W}}.$$ Now $\mathcal{Y}_W = \text{sp}\{w_W^j, j = 0, 1, 2, \dots, k-1\} + \mathcal{Y}_W^{com}$. Therefore, we need to show $\mathcal{Y}_W^{com} \leftrightarrow p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$ and $w_W^j \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}, j = 0, 1, 2, \dots, k-1$.

Now $\mathcal{Y}_W^{com} \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(j)} \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}, j > 0$, since $\mathcal{Y}_W^{com} \leftrightarrow \mathcal{Y}_{\dot{W}\dot{W}}^{start} \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$ and $\mathcal{Y}_W^{com} \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)} = \mathcal{Y}_W^{com} \leftrightarrow (I_{\dot{W}\dot{W}} +_{\dot{w}} (\mathcal{Y}_{\dot{W}\dot{W}} \circ W \oplus (\mathcal{Y}_W^{com})_{\dot{W}})) \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$. Therefore $\mathcal{Y}_W^{com} \leftrightarrow p(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$.

We next show that for any vector $w_W$, that is a linear combination of vectors $w_W^j$, $j = 0, 1, \dots, k-1$, we must have

$$w_W \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}.$$

Note that

$w_W \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) = w_W \leftrightarrow [(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k)} +_{\dot{w}} d_1^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k-1)} +_{\dot{w}} \dots +_{\dot{w}} d_{k-1}^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start}) +_{\dot{w}} d_k^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)}] = (w_W \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k)}) + (w_W \leftrightarrow d_1^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(k-1)}) + \dots + (w_W \leftrightarrow d_{k-1}^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})) + (w_W \leftrightarrow d_k^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)}), \text{ for any } w_W \text{ (by the definition of intersection-sum).}$$

We remind the reader that $(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)} \equiv I_{\dot{W}\dot{W}} +_{\dot{w}} (\mathcal{Y}_{\dot{W}\dot{W}} \circ W \oplus (\mathcal{Y}_W^{com})_{\dot{W}})$ so that $w_W \leftrightarrow d_k^{\dot{w}}(\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(0)} = d_k(w_W)_{\dot{W}} + \mathcal{Y}_{\dot{W}\dot{W}}^{start} \times \dot{W} = d_k(w_W)_{\dot{W}} + (\mathcal{Y}_W^{com})_{\dot{W}}$.

We have $w_W^0 \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start}) = w_{\dot{W}}^1 + (\mathcal{Y}_W^{com})_{\dot{W}}$.

$w_W^0 \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(j)} = (w_W^0 \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start})^{(j-1)})_W \leftrightarrow (\mathcal{Y}_{\dot{W}\dot{W}}^{start}) = (w_{\dot{W}}^{j-1} + (\mathcal{Y}_W^{com})_{\dot{W}})_W \leftrightarrow \mathcal{Y}_{\dot{W}\dot{W}}^{start}$
$$= w_{\dot{W}}^j + (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}} \text{ so that } w_W^0 \leftrightarrow d_{k-j} (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)}$$

$$= (d_{k-j} w_W^j)_{\dot{W}} + (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}.$$

$$\text{Thus } w_W^0 \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) = (w_W^k + d_1 w_W^{k-1} + \dots + d_k w_W^0 + \mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}} \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}.$$

$$\text{We have } w_W^j \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) = p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \leftrightarrow w_W^j$$

$$\subseteq p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \leftrightarrow ((\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)} \leftrightarrow w_W^0)_{\dot{W}}$$

$$= (p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) * (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)}) \leftrightarrow w_W^0 = [(\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)} * p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}})] \leftrightarrow w_W^0$$

$$= (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)} \leftrightarrow [p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \leftrightarrow w_W^0]_{\dot{W}} \subseteq (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(j)} \leftrightarrow \mathcal{Y}_{\dot{W}}^{\text{com}} \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$$

(where we have used the fact that for a genop $\mathcal{Y}_{\dot{W}}^{\text{start}}$ and polynomials $p_1(s), p_2(s), p(s) \coloneqq p_1(s) * p_2(s)$, we must have $p(\mathcal{Y}_{\dot{W}}^{\text{start}}) = p_1(\mathcal{Y}_{\dot{W}}^{\text{start}}) * p_2(\mathcal{Y}_{\dot{W}}^{\text{start}})$ (Theorem 65)).

Since every $w_W^j, j = 0, \dots, k-1$, satisfies $w_W^j \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$, it follows that for every linear combination $w_W$ of these vectors we must have that $w_W \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$. We have already seen that $\mathcal{Y}_{\dot{W}}^{\text{com}} \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$. Therefore $\mathcal{Y}_{\dot{W}} \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$. Thus $[p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \circ W] \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) = \mathcal{Y}_{\dot{W}} \leftrightarrow p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \subseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}} = p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \times \dot{W}$, i.e, $p(\mathcal{Y}_{\dot{W}}^{\text{start}}) = p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \circ W \oplus p_{\text{start}}(\mathcal{Y}_{\dot{W}}^{\text{start}}) \times \dot{W}$, i.e., $p_{\text{start}}(s)$ annihilates $\mathcal{Y}_{\dot{W}}^{\text{start}}$.

Next, we show that if $p'(s)$ has degree lower than that of $p'_{\text{start}}(s)$, then $p'(\mathcal{Y}_{\dot{W}}^{\text{start}})$ is not decoupled. Let $p'(s) = \sum_{i=0}^t c_{t-i}s^i$ and let $t \le k-1$. We have, $w_W^t \notin \text{sp}\{w_W^0, w_W^1, \dots, w_W^{t-1}\} + \mathcal{Y}_{\dot{W}}^{\text{com}}$. Now $w_{\dot{W}}^t \in (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t)} \leftrightarrow w_W^0$. Therefore $(\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t)} \leftrightarrow w_W^0 \supseteq (\text{sp}\{w_W^0, w_W^1, \dots, w_W^{t-1}\} + \mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}$. It follows that

$$((\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t)} + \dot{c}_1^\dot{w} (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t-1)} + \dot{c}_\dot{w}^\dot{w} + \dots + \dot{c}_t^\dot{w} (\mathcal{Y}_{\dot{W}}^{\text{start}}) + \dot{c}_t^\dot{w} (\mathcal{Y}_{\dot{W}}^{\text{start}})^{(0)}) \leftrightarrow w_W^0 \\ = ((\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t)} \leftrightarrow w_W^0) + c_1((\mathcal{Y}_{\dot{W}}^{\text{start}})^{(t-1)} \leftrightarrow w_W^0) + \dots + c_{t-1}((\mathcal{Y}_{\dot{W}}^{\text{start}}) \leftrightarrow w_W^0) + c_t((\mathcal{Y}_{\dot{W}}^{\text{start}})^{(0)} \leftrightarrow w_W^0) \supseteq (\mathcal{Y}_{\dot{W}}^{\text{com}})_{\dot{W}}.$$

$$\text{Thus } p'(s) \equiv \sum_{i=0}^t c_{t-i}s^i \text{ does not annihilate } \mathcal{Y}_{\dot{W}}^{\text{start}}.$$

It follows that $p_{\text{start}}(s)$ is a polynomial of minimal degree that annihilates $\mathcal{Y}_{\dot{W}}^{\text{start}}$. This proves the claim.

### 16.1.2. Building the genop $\mathcal{Y}_{\dot{W}}^{\text{end}}$ with desired $p_{\text{end}}(s)$ as its minimal annihilating polynomial

Let $p_{\text{end}}(s) = s^k + b_1 s^{k-1} + \dots + b_k$, be a specified polynomial. We will show how to modify $\mathcal{Y}_{\dot{W}}^{\text{start}}$ to $\mathcal{Y}_{\dot{W}}^{\text{end}}$ so that the latter has $p_{\text{end}}(s)$ as its minimal annihilating polynomial. We do this by building a basic sequence for $\mathcal{Y}_{\dot{W}}^{\text{end}}$.

Let $v_W^0, v_W^1, \dots, v_W^k$ be defined through

$$\begin{align}
v_W^0 &= \lambda_0 w_W^0 (\lambda_0 \neq 0) \nonumber \\
v_W^1 &= \lambda_0 w_W^1 + \lambda_1 w_W^0 \nonumber \\
&\vdots \tag{59}
\end{align}$$

$$v_W^k = \lambda_0 w_W^k + \lambda_1 w_W^k + \dots + \lambda_k w_W^0$$

This can be rewritten as

$$(v_W^0 \quad v_W^1 \quad \dots \quad v_W^k) = (w_W^0 \quad w_W^1 \quad \dots \quad w_W^k) \begin{bmatrix} \lambda_0 & \lambda_1 & \dots & \lambda_k \\ 0 & \lambda_0 & \dots & \lambda_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \lambda_0 \end{bmatrix} \quad (60)$$

We will adjust the $\lambda_i$ so that we have

$$b_k v_W^0 + b_{k-1} v_W^1 + \dots + v_W^k = d_k w_W^0 + d_{k-1} w_W^1 + \dots + w_W^k,$$
i.e.,

$$ (v_W^0 \ v_W^1 \ \dots \ v_W^k) \begin{pmatrix} b_k \\ b_{k-1} \\ \vdots \\ 1 \end{pmatrix} = (w_W^0 \ w_W^1 \ \dots \ w_W^k) \begin{pmatrix} d_k \\ d_{k-1} \\ \vdots \\ 1 \end{pmatrix} \quad (61) $$

By Equation 60, this happens if

$$ \begin{pmatrix} d_k \\ d_{k-1} \\ \vdots \\ 1 \end{pmatrix} = \begin{bmatrix} \lambda_0 & \lambda_1 & \cdots & \lambda_k \\ 0 & \lambda_0 & \cdots & \lambda_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_0 \end{bmatrix} \begin{pmatrix} b_k \\ b_{k-1} \\ \vdots \\ 1 \end{pmatrix} \quad (62) $$

Equivalently, this happens if

$$ \begin{pmatrix} d_k \\ d_{k-1} \\ \vdots \\ 1 \end{pmatrix} = \begin{bmatrix} 1 & b_1 & \cdots & b_k \\ 0 & 1 & \cdots & b_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \begin{pmatrix} \lambda_k \\ \lambda_{k-1} \\ \vdots \\ \lambda_0 \end{pmatrix} \quad (63) $$

If we choose the $\lambda_i$ such that Equation 63 is satisfied, and use this vector $(\lambda_0, \dots, \lambda_k)$ in Equation 59, the resulting basic sequence $v_W^0, v_W^1, \dots, v_W^k$ would define the genop $\mathcal{Y}_{W\dot{W}}^{end}$ through

$$ \mathcal{Y}_{W\dot{W}}^{end} = sp\{(v_W^j, v_{\dot{W}}^{j+1}), j = 0, 1, 2, \dots, k-1\} + (\mathcal{Y}_W^{com} \oplus (\mathcal{Y}_W^{com})_{\dot{W}}). $$

Since $v_W^k + b_1 v_W^{k-1} + \dots + b_k v_W^0 \in \mathcal{Y}_W^{com}$, the polynomial $p_{end}(s) = s^k + b_1 s^{k-1} + \dots + b_k$, annihilates $\mathcal{Y}_{W\dot{W}}^{end}$. It is the minimal annihilating polynomial for $\mathcal{Y}_{W\dot{W}}^{end}$ since $p_{start}(s)$ is the minimal annihilating polynomial for $\mathcal{Y}_{W\dot{W}}^{start}$.

We summarize the above procedure to construct a genop with the desired minimal annihilating polynomial in the following algorithm.

## Algorithm VI

### Algorithm Annihilating polynomial to genop

**Input:** A genop $\mathcal{Y}_{W\dot{W}}^{start} \subseteq \mathcal{Y}_{W\dot{W}}^{u}$ with minimal annihilating polynomial $p_{start}(s) = \sum_{i=0}^{k} d_{k-i}s^i$, and a desired minimal annihilating polynomial $\sum_{i=0}^{k} b_{k-i}s^i$.

**Output:** A genop $\mathcal{Y}_{W\dot{W}}^{end} \subseteq \mathcal{Y}_{W\dot{W}}^{u}$ with minimal annihilating polynomial $p_{end}(s) = \sum_{i=0}^{k} b_{k-i}s^i$.

**Step 1.** Compute $\lambda_i, i = 0, \dots, k$ from $p_{start}(s), p_{end}(s)$ using Equation 63.

**Step 2.** Compute the basic sequence $v_W^0, \dots, v_W^k$ from a basic sequence $w_W^0, \dots, w_W^k$ of $\mathcal{Y}_{W\dot{W}}^{start}$ using Equation 59.

**Step 3.** $\mathcal{Y}_{W\dot{W}}^{end} \leftarrow sp\{(v_W^j, v_{\dot{W}}^{j+1}), j = 0, 1, 2, \dots, k-1\} + (\mathcal{Y}_W^{com} \oplus (\mathcal{Y}_W^{com})_{\dot{W}})$.

**Algorithm Ends.**

### 16.1.3. Building the genop $\mathcal{Y}_{W\dot{W}}^{new}$ with desired $p_u(s)p_{end}(s)$ as its annihilating polynomial

**Problem 81.** Let $\mathcal{Y}_{W\dot{W}UY}$ be an RDS and let $\mathcal{Y}_{W\dot{W}}^{u} \equiv \mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}$. Let $\mathcal{Y}_W$ be the minimal invariant space of $\mathcal{Y}_{W\dot{W}}^{u}$ containing $(\mathcal{Y}_{W\dot{W}}^{u} \times \dot{W})_W$ and let $\mathcal{Y}_W^{com} \equiv \mathcal{Y}_{W\dot{W}}^{u} \times W \cap (\mathcal{Y}_{W\dot{W}}^{u} \times \dot{W})_W$. Let $p_2(s)$ be any
polynomial of degree equal to $r(\mathcal{Y}_W) - r(\mathcal{Y}_W^{com})$. We saw in Problem 78, that for every genop $\mathcal{Y}_{W\dot{W}}$ such that $\mathcal{Y}_{W\dot{W}} \subseteq \mathcal{Y}_{W\dot{W}}^u$, $\mathcal{Y}_{W\dot{W}} \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W$, we must have the annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ contain the minimal annihilating polynomial $p_u(s)$ of the genop $\mathcal{Y}_{W\dot{W}}^u + (\mathcal{Y}_W)_{\dot{W}}$ as a factor. We saw in Problem 80, that $p_2(s)$ can be made into the minimal annihilating polynomial of the genop $\mathcal{Y}_{W\dot{W}} \cap \mathcal{Y}_W$. Show that $p_u(s)p_2(s)$ annihilates $\mathcal{Y}_{W\dot{W}}$ and that the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ contains $p_u(s), p_2(s)$ as factors. Further, show that $\mathcal{Y}_{W\dot{W}}$ satisfies

$$ \mathcal{Y}_{W\dot{W}} \subseteq \mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}, \mathcal{Y}_{W\dot{W}} \times \dot{W} \supseteq \mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}U \times \dot{W} \text{ and therefore by Theorem 39,} $$

$$ \mathcal{Y}_{W\dot{W}} = (\mathcal{Y}_{W\dot{W}UY} \cap \mathcal{Y}_{WU}) \circ W\dot{W}, \text{ where } \mathcal{Y}_{WU} = (\mathcal{Y}_{W\dot{W}UY} \cap \mathcal{Y}_{W\dot{W}}) \circ WU. $$

Answer

We can grow $\mathcal{Y}_{W\dot{W}}^{end}$ of Subsection 16.1.2, to a genop $\mathcal{Y}_{W\dot{W}}^{new}$, where $\mathcal{Y}_{W\dot{W}}^{new} \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W$. For this we use the following algorithm which starts with a basic sequence in $\mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W$ and outputs $\mathcal{Y}_{W\dot{W}}^{new}$.

## Algorithm VII

### Algorithm Basic2genop

Input: A genop $\mathcal{Y}_{W\dot{W}}^{end} \subseteq \mathcal{Y}_{W\dot{W}}^u$.

Output: A genop $\mathcal{Y}_{W\dot{W}}^{new}$, where $\mathcal{Y}_{W\dot{W}}^{new} \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W$ and $\mathcal{Y}_{W\dot{W}}^{new} \supseteq \mathcal{Y}_{W\dot{W}}^{end}$.

Step 1. Let $t = r(\mathcal{Y}_{W\dot{W}}^u \circ W) - r(\mathcal{Y}_{W\dot{W}}^{end} \circ W)$. Construct a sequence of vectors $u_W^1, u_W^2, \dots, u_W^t$ from $\mathcal{Y}_{W\dot{W}}^u \circ W$, which are independent modulo $\mathcal{Y}_W \equiv \mathcal{Y}_{W\dot{W}}^{end} \circ W$.

(Thus if $sp\{v_W^0, v_W^1, \dots, v_W^k\} + \mathcal{Y}_W^{com} = \mathcal{Y}_{W\dot{W}}^{end} \circ W$, then

$$ sp\{v_W^0, v_W^1, \dots, v_W^k, u_W^1, u_W^2, \dots, u_W^t\} + \mathcal{Y}_W^{com} = \mathcal{Y}_{W\dot{W}}^u \circ W. $$

Step 2. Pick vectors $v_W^1, v_W^2, \dots, v_W^t$ such that $(u_W^1, v_W^2), \dots, (u_W^t, v_W^t) \in \mathcal{Y}_{W\dot{W}}^u$.

Step 3. $\mathcal{Y}_{W\dot{W}}^{new} \leftarrow sp\{(u_W^1, v_W^1), \dots, (u_W^t, v_W^t)\} + sp\{(v_W^j, v_W^{j+1}), j = 0, 1, 2, \dots, k-1\} + (\mathcal{Y}_W^{com} \oplus (\mathcal{Y}_W^{com})_{\dot{W}})$.

Algorithm ends.

16.1.4. Proof that $\mathcal{Y}_{W\dot{W}}^{new}$ is a genop with minimal annihilating polynomial which has $p_u(s), p_{end}(s)$ as factors

We will now show that $\mathcal{Y}_{W\dot{W}}^{new}$ is a genop and has as an annihilating polynomial $p_u(s)p_{end}(s)$, where $p_u(s)$ is the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^u + (\mathcal{Y}_W)_{\dot{W}}$ and $p_{end}(s) \equiv s^k + c_1s^{k-1} + \dots + c_k$, the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^{end}$.

We know that

$$ \mathcal{Y}_{W\dot{W}}^{new} \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W \supseteq (\mathcal{Y}_{W\dot{W}}^u \circ \dot{W})_W \supseteq (\mathcal{Y}_{W\dot{W}}^{new} \circ \dot{W})_W. $$

Next, the vectors $v_W^0, v_W^1, \dots, v_W^k, u_W^1, u_W^2, \dots, u_W^t$ are independent modulo $\mathcal{Y}_W^{com}$. So the only way in which vectors in

$$ \{(v_W^j, v_W^{j+1}), j = 0, 1, 2, \dots, k-1\} \cup \{(u_W^1, v_W^1), \dots, (u_W^t, v_W^t)\} $$

can be linearly combined to yield a vector of the kind $(f_W, g_{\dot{W}})$, with $f_W \in \mathcal{Y}_W^{com}$ is through the trivial linear combination, which means that

$$ g_{\dot{W}} \in (\mathcal{Y}_W^{com})_{\dot{W}}. $$
Therefore, $\mathcal{Y}_{W\dot{W}}^{new} \times \dot{W} \subseteq (\mathcal{Y}_W^{com})_{\dot{W}}$. We already know that $\mathcal{Y}_{W\dot{W}}^{new} \times \dot{W} \supseteq (\mathcal{Y}_W^{com})_{\dot{W}}$, so that we must have

$$ \mathcal{Y}_{W\dot{W}}^{new} \times \dot{W} = (\mathcal{Y}_W^{com})_{\dot{W}}. $$

It is clear that $\mathcal{Y}_{W\dot{W}}^{new} \times W \supseteq \mathcal{Y}_W^{com}$. Thus we conclude

$$ \mathcal{Y}_{W\dot{W}}^{new} \times W \supseteq (\mathcal{Y}_{W\dot{W}}^{new} \times \dot{W})_W. $$

Hence $\mathcal{Y}_{W\dot{W}}^{new}$ is a genop. Now $\mathcal{Y}_{W\dot{W}}^{new} \subseteq \mathcal{Y}_{W\dot{W}}^{u}$ is a genop such that $\mathcal{Y}_{W\dot{W}}^{u} \circ W = \mathcal{Y}_{W\dot{W}}^{new} \circ W$ and $\mathcal{Y}_W$ is invariant in $\mathcal{Y}_{W\dot{W}}^{u}$. By Lemma 56, we have that $\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W, \mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_W)_{\dot{W}}$ are genops and $\mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_W)_{\dot{W}} = \mathcal{Y}_{W\dot{W}}^{u} + (\mathcal{Y}_W)_{\dot{W}}$. By Theorem 69, the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^{new}$ contains as factors the minimal annihilating polynomials $p_u(s), p_{end}(s)$ respectively of $\mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_W)_{\dot{W}}$ and $\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W$. Further, $p_u(s)p_{end}(s)$ annihilates $\mathcal{Y}_{W\dot{W}}^{new}$. The polynomial $p_u(s)p_{end}(s)$ is a minimal annihilating polynomial for $\mathcal{Y}_{W\dot{W}}$ if $p_u(s), p_{end}(s)$ have no common roots.

### 16.1.5. Proof that $\mathcal{Y}_{W\dot{W}}^{new}$ can be obtained from the regular dynamical system $\mathcal{Y}_{W\dot{W}UY}$ by $(W,U)$- feedback

By Theorem 39, any generalized autonomous system $\mathcal{Y}_{W\dot{W}}$ that satisfies

$$ 1. \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W} \supseteq \mathcal{Y}_{W\dot{W}}^{u}, $$

$$ 2. \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \times \dot{W} \subseteq \mathcal{Y}_{W\dot{W}} \times \dot{W}, $$

can be realized by $(W,U)$- feedback through $\mathcal{Y}_{WU} \equiv (\mathcal{Y}_{W\dot{W}UY} \cap \mathcal{Y}_{W\dot{W}}) \circ WU$, i.e.,
$$ \mathcal{Y}_{W\dot{W}} = (\mathcal{Y}_{W\dot{W}UY} \cap \mathcal{Y}_{WU}) \circ W \dot{W}. $$

Now $\mathcal{Y}_{W\dot{W}}^{u} := \mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}$. The first condition states simply that $\mathcal{Y}_{W\dot{W}}^{u} \supseteq \mathcal{Y}_{W\dot{W}}$. This is clearly satisfied by the genop $\mathcal{Y}_{W\dot{W}}^{new}$ constructed by the Algorithm VII. The second condition is satisfied because (using regularity of $\mathcal{Y}_{W\dot{W}UY}$)
$$ (\mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \times \dot{W})_W \subseteq \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \times W \subseteq \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \circ W \dot{W} \times W = \mathcal{Y}_{W\dot{W}}^{u} \times W \text{ and} $$
$$ \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \times \dot{W} \subseteq \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \circ W \dot{W} \times \dot{W} = \mathcal{Y}_{W\dot{W}}^{u} \times \dot{W}, \text{ i.e., } \mathcal{Y}_{W\dot{W}UY} \circ W \dot{W}U \times \dot{W} \subseteq (\mathcal{Y}_{W\dot{W}}^{u} \times W)_{\dot{W}} \cap \mathcal{Y}_{W\dot{W}}^{u} \times \dot{W} = \mathcal{Y}_{W\dot{W}}^{com} = \mathcal{Y}_{W\dot{W}}^{new} \times \dot{W}. $$

Thus we see that $p_u(s)p_2(s)$, where $p_u(s)$ is the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^{u} + (\mathcal{Y}_W)_{\dot{W}}$, and $p_2(s)$ is a polynomial of degree equal to $r(\mathcal{Y}_W) - r(\mathcal{Y}_W^{com})$, can be made into the annihilating polynomial of a genop $\mathcal{Y}_{W\dot{W}}$ which can be obtained as $\mathcal{Y}_{W\dot{W}}^{u} \cap \mathcal{Y}_{WU}$ for some $\mathcal{Y}_{WU}$. Further, the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ will have $p_u(s), p_2(s)$, as factors.

The foregoing algorithms can be used indirectly to do pole placement for $m_y\dot{w}$- injection. One does this by simply going to the adjoint and using the algorithms of the previous subsections to obtain suitable genops, taking their adjoints and returning to the primal dynamical system. It would, however, be of some interest to recast the algorithm in such a manner that they can be line by line dualized. This we do in [14].

We now address the question: "What polynomials can be made into minimal annihilating polynomials for genops obtainable by $(\dot{W},Y)$- injection from the RDS $\mathcal{Y}_{W\dot{W}UY}$?"

**Problem 82.** When $\mathcal{Y}_{W\dot{W}UY}$ is of the state-input-output form defined by $\dot{w} = Aw + Bu, y = Cw$, and $\mathcal{Y}_W$ is its unobservable subspace we know that the minimal annihilating polynomial of $A|_{\mathcal{Y}_W}$ has to be a factor of every annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ obtained by output injection from $\mathcal{Y}_{W\dot{W}UY}$. We translate this idea to our notation below.
Let $\mathcal{Y}_{W\dot{W}UY}$ be an RDS and let $\mathcal{Y}_{W\dot{W}}^l \equiv \mathcal{Y}_{W\dot{W}UY} \times W\dot{W}$. Let $\mathcal{Y}_W$ be the maximal invariant space of $\mathcal{Y}_{W\dot{W}}^l$ contained in $\mathcal{Y}_{W\dot{W}}^l \circ W$. Let $\mathcal{Y}_{W\dot{W}} := (\mathcal{Y}_{W\dot{W}}^l + \mathcal{Y}_{\dot{W}Y}) \times W\dot{W}$ be a genop with $\mathcal{Y}_{\dot{W}Y}$ such that $\mathcal{Y}_{\dot{W}Y} \times \dot{W} = \mathcal{Y}_{W\dot{W}}^l \times \dot{W}$ (equivalently, let $\mathcal{Y}_{W\dot{W}}$ be a genop such that $\mathcal{Y}_{W\dot{W}} \supseteq \mathcal{Y}_{W\dot{W}}^l$, $\mathcal{Y}_{W\dot{W}} \times \dot{W} = \mathcal{Y}_{W\dot{W}}^l \times \dot{W}$). Show that every annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ contains as a factor, the minimal annihilating polynomial $p_l(s)$ of the genop $\mathcal{Y}_{W\dot{W}}^l \cap \mathcal{Y}_W$.

Answer

The solution to this problem follows by duality from the solution to Problem 78.

We remind the reader that $(\mathcal{Y}_{W\dot{W}UY})^a := (\mathcal{Y}_{W\dot{W}UY}^{\perp})_{(-\dot{W})W(-Y)U}, (\mathcal{Y}_{W\dot{W}}^a) := (\mathcal{Y}_{W\dot{W}}^{\perp})_{(-\dot{W})W}$. We proceed as in Problem 47. We use the following facts:

$$ \bullet \left( (\mathcal{Y}_{W\dot{W}UY})^a \right)^a = \mathcal{Y}_{W\dot{W}UY}, \left( (\mathcal{Y}_{W\dot{W}}^a) \right)^a = \mathcal{Y}_{W\dot{W}}. $$

$$ \bullet \quad \begin{aligned} \mathcal{Y}_{W\dot{W}} \circ W \supseteq (\mathcal{Y}_{W\dot{W}} \circ \dot{W})_W, \mathcal{Y}_{W\dot{W}} \times W \supseteq (\mathcal{Y}_{W\dot{W}} \times \dot{W})_W, \text{ iff} \\ (\mathcal{Y}_{W\dot{W}}^{\perp})_{(-\dot{W})W} \circ W \supseteq ((\mathcal{Y}_{W\dot{W}}^{\perp})_{(-\dot{W})W} \circ \dot{W})_W, (\mathcal{Y}_{W\dot{W}}^{\perp})_{(-\dot{W})W} \times W \supseteq ((\mathcal{Y}_{W\dot{W}}^{\perp})_{(-\dot{W})W} \times \dot{W})_W. \text{ So} \\ \mathcal{Y}_{W\dot{W}} \text{ is a genop iff its adjoint is one.} \end{aligned} $$

$$ \bullet \quad \begin{aligned} \text{For any polynomial } p(s) \text{ and genaut } \mathcal{Y}_{W\dot{W}}, \text{ we have } (p(\mathcal{Y}_{W\dot{W}}))^a = p((\mathcal{Y}_{W\dot{W}})^a) \text{ (Problem 71). } & (\mathcal{Y}_W^1 \oplus \\ & \mathcal{Y}_W^2)^a = ((\mathcal{Y}_W^2)^\perp)_W \oplus ((\mathcal{Y}_W^1)^\perp)_W \text{ so that a genaut is decoupled iff its adjoint is decoupled. Therefore} \\ p(s) \text{ annihilates } \mathcal{Y}_{W\dot{W}}, \text{ iff } p(s) \text{ annihilates } (\mathcal{Y}_{W\dot{W}})^a. \end{aligned} $$

Using these facts we infer the following.

$$ \text{1. (primal) } \mathcal{Y}_{W\dot{W}}^l = \mathcal{Y}_{W\dot{W}UY} \times W\dot{W} \text{ iff (dual) } (\mathcal{Y}_{W\dot{W}}^l)^a = (\mathcal{Y}_{W\dot{W}UY})^a \circ W\dot{W}. $$

$$ \text{2. (primal) } \mathcal{Y}_W \text{ is the maximal invariant space of } \mathcal{Y}_{W\dot{W}}^l \text{ contained in } \mathcal{Y}_{W\dot{W}}^l \circ W \text{ iff (dual) } \mathcal{Y}_W^\perp \text{ is the minimal invariant space of } (\mathcal{Y}_{W\dot{W}}^l)^a \text{ containing } (\mathcal{Y}_{W\dot{W}}^l \times \dot{W})_W. $$

$$ \text{3. (primal) } \mathcal{Y}_{W\dot{W}} = \mathcal{Y}_{W\dot{W}}^l + \mathcal{Y}_{\dot{W}Y} \text{ iff (dual) } (\mathcal{Y}_{W\dot{W}}^a)^a = (\mathcal{Y}_{W\dot{W}}^l)^a \cap (\mathcal{Y}_{\dot{W}Y}^\perp)_{WU}. $$

$$ \text{4. (primal) every annihilating polynomial of } \mathcal{Y}_{W\dot{W}} \text{ contains as a factor, the minimal annihilating polynomial } p_l(s) \text{ of the genop } \mathcal{Y}_{W\dot{W}}^l \cap \mathcal{Y}_W \text{ iff (dual) every annihilating polynomial of } (\mathcal{Y}_{W\dot{W}}^a)^a \text{ contains as a factor, the minimal annihilating polynomial } p_u(s) \text{ of the genop } (\mathcal{Y}_{W\dot{W}}^l)^a + (\mathcal{Y}_{W\dot{W}}^\perp)^a \text{.} $$

The statements marked (dual) in 1.,2.,3., above imply the statement marked (dual) in 4. Therefore the statements marked (primal) in 1.,2.,3., above imply the statement marked (primal) in 4.

**Problem 83.** When $\mathcal{Y}_{W\dot{W}UY}$ is of the state-input-output form defined by $\dot{w} = Aw + Bu, y = Cw$, and $\mathcal{Y}_W$ is its unobservable subspace we know that through some output injection $\dot{w} = Gy$, we can make $(A - GC)/\mathcal{Y}_W$ have any desired minimal annihilating polynomial $p_2(s)$ of degree equal to the size of $A$ minus the dimension of $\mathcal{Y}_W$ and if $p_l(s)$ is the minimal annihilating polynomial of $A|_{\mathcal{Y}_W}$, we can make $(A - GC)$ have $p_l(s)p_2(s)$ as an annihilating polynomial with its minimal annihilating polynomial having $p_l(s), p_2(s)$, as factors. We translate this idea to our notation below.

Let $\mathcal{Y}_{W\dot{W}UY}$ be an RDS and let $\mathcal{Y}_{W\dot{W}}^l \equiv \mathcal{Y}_{W\dot{W}UY} \times W\dot{W}$. Let $\mathcal{Y}_W$ be the maximal invariant space of $\mathcal{Y}_{W\dot{W}}^l$ contained in $\mathcal{Y}_{W\dot{W}}^l \circ W$ and let $\mathcal{Y}_W^{\text{sum}} \equiv \mathcal{Y}_{W\dot{W}}^l \circ W + (\mathcal{Y}_{W\dot{W}}^l \circ \dot{W})_W$. We saw in Problem 82, that for every genop $\mathcal{Y}_{W\dot{W}}$ such that $\mathcal{Y}_{W\dot{W}} \supseteq \mathcal{Y}_{W\dot{W}}^l$, $\mathcal{Y}_{W\dot{W}} \times \dot{W} = \mathcal{Y}_{W\dot{W}}^l \times \dot{W}$, we must have the annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ contain the minimal annihilating polynomial $p_l(s)$ of the genop $\mathcal{Y}_{W\dot{W}}^l \cap \mathcal{Y}_W$ as a factor. Let $p_2(s)$ be any polynomial of degree equal to $(r(\mathcal{Y}_W^{\text{sum}}) - r(\mathcal{Y}_W))$. Show that $p_2(s)$ can be made into the minimal annihilating polynomial of the genop $\mathcal{Y}_{W\dot{W}} + (\mathcal{Y}_W)_{\dot{W}}$, that $p_l(s)p_2(s)$ annihilates $\mathcal{Y}_{W\dot{W}}$ and that the
minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}$ contains $p_1(s), p_2(s)$ as factors. Further, show that $\mathcal{Y}_{W\dot{W}}$ satisfies
$$ \mathcal{Y}_{W\dot{W}} \supseteq \mathcal{Y}_{W\dot{W}UY} \times W\dot{W}, \mathcal{Y}_{W\dot{W}} \circ W \subseteq \mathcal{Y}_{W\dot{W}UY} \times W\dot{W}Y \circ W \text{ and therefore by Theorem 41,} $$
$$ \mathcal{Y}_{W\dot{W}} = (\mathcal{Y}_{W\dot{W}UY} + \mathcal{Y}_{\dot{W}Y}) \times W\dot{W}, \text{ where } \mathcal{Y}_{\dot{W}Y} \equiv (\mathcal{Y}_{W\dot{W}UY} + \mathcal{Y}_{W\dot{W}}) \times \dot{W}Y. $$

Answer

This problem is dual to Problem 81 and can be solved by solving the dual problem for the adjoint and dualizing the result.

For the adjoint the problem will appear as follows:

"Let $(\mathcal{Y}_{W\dot{W}UY})^a$ be an RDS and let $(\mathcal{Y}_{W\dot{W}}^l)^a \equiv (\mathcal{Y}_{W\dot{W}UY})^a \circ W\dot{W}$. Let $\mathcal{Y}_W^\perp$ be the minimal invariant space of $(\mathcal{Y}_{W\dot{W}}^l)^a$ containing $((\mathcal{Y}_{W\dot{W}}^l)^a \times \dot{W})_W$ and let $(\mathcal{Y}_W^{sum})^\perp \equiv (\mathcal{Y}_{W\dot{W}}^l)^a \times W \cap ((\mathcal{Y}_{W\dot{W}}^l)^a \times \dot{W})_W$. Let $p_2(s)$ be any polynomial of degree equal to $r(\mathcal{Y}_W^\perp) - r((\mathcal{Y}_W^{sum})^\perp)$. For every genop $\mathcal{Y}_{W\dot{W}}^a$ such that $\mathcal{Y}_{W\dot{W}}^a \subseteq (\mathcal{Y}_{W\dot{W}}^l)^a$, $\mathcal{Y}_{W\dot{W}}^a \circ W = (\mathcal{Y}_{W\dot{W}}^l)^a \circ W$, we must have the annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^a$ contain the minimal annihilating polynomial $p_1(s)$ of the genop $(\mathcal{Y}_{W\dot{W}}^l)^a + (\mathcal{Y}_{\dot{W}}^\perp)_{\dot{W}}$ as a factor. Hence show that $p_1(s)p_2(s)$ is an annihilating polynomial of genop $\mathcal{Y}_{W\dot{W}}^a$ which equals $((\mathcal{Y}_{W\dot{W}}^l)^a \cap (\mathcal{Y}_{\dot{W}Y}^\perp)_{\dot{W}U}) \circ W\dot{W}$, where $(\mathcal{Y}_{\dot{W}Y}^\perp)_{\dot{W}U} = ((\mathcal{Y}_{W\dot{W}}^l)^a \cap \mathcal{Y}_{W\dot{W}}^a) \circ WU$. Show that the minimal annihilating polynomial of genop $\mathcal{Y}_{W\dot{W}}^a$ contains $p_1(s), p_2(s)$, as factors. Further, show that $\mathcal{Y}_{W\dot{W}}^a$ satisfies $\mathcal{Y}_{W\dot{W}}^a \subseteq (\mathcal{Y}_{W\dot{W}UY})^a \circ W\dot{W}$, $\mathcal{Y}_{W\dot{W}}^a \times \dot{W} \supseteq (\mathcal{Y}_{W\dot{W}UY})^a \circ W\dot{W}U \times \dot{W}$ and therefore by Theorem 39, $\mathcal{Y}_{W\dot{W}}^a = ((\mathcal{Y}_{W\dot{W}UY})^a \cap (\mathcal{Y}_{\dot{W}Y}^\perp)_{\dot{W}U}) \circ W\dot{W}$, where $(\mathcal{Y}_{\dot{W}Y}^\perp)_{\dot{W}U} \equiv (\mathcal{Y}_{W\dot{W}UY} \cap \mathcal{Y}_{W\dot{W}}^a) \circ WU$."

We solve the above problem for the adjoint $\mathcal{Y}_{W\dot{W}}^a$ as in the solution to Problem 81. This would solve the problem of computing $\mathcal{Y}_{W\dot{W}} = (\mathcal{Y}_{W\dot{W}}^a)$ with annihilating polynomial $p_1(s)p_2(s)$, where $p_1(s)$ is the minimal annihilating polynomial of $\mathcal{Y}_{W\dot{W}}^l \cap \mathcal{Y}_W$. The minimal annihilating polynomial of genop $\mathcal{Y}_{W\dot{W}}$ will contain $p_1(s), p_2(s)$, as factors. Further, $\mathcal{Y}_{W\dot{W}}$ can be obtained as $(\mathcal{Y}_{W\dot{W}}^l + \mathcal{Y}_{\dot{W}Y}) \times W\dot{W}$, where $\mathcal{Y}_{\dot{W}Y} \equiv (\mathcal{Y}_{W\dot{W}UY} + \mathcal{Y}_{W\dot{W}}^l) \times \dot{W}Y$.

**Problem 84.** One way of looking at the solution of the pole placement by state feedback problem is to recognize that the USG $\mathcal{Y}_{W\dot{W}}^u$ has the property that $\mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W$ can be annihilated by any polynomial of appropriate degree. Dually the LSG $\mathcal{Y}_{W\dot{W}}^l$ has the property that $\mathcal{Y}_{W\dot{W}}^l + (\mathcal{Y}_W^u)_{\dot{W}}$ can be annihilated by any polynomial of appropriate degree.

Prove the following primal-dual pair by proving the primal.

1. (primal) Let $\mathcal{Y}_W$ be the minimal invariant space of a USG $\mathcal{Y}_{W\dot{W}}^u$ containing $(\mathcal{Y}_{W\dot{W}}^u \times \dot{W})_W$. Let $k \equiv r(\mathcal{Y}_W) - r(\mathcal{Y}_{W\dot{W}}^u \times W \cap (\mathcal{Y}_{W\dot{W}}^u \times \dot{W})_W)$. Let $p_u(s)$ be the minimal annihilating polynomial of the genop $\mathcal{Y}_{W\dot{W}}^u + (\mathcal{Y}_W^u)_{\dot{W}}$. Show that $\mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W$ can be annihilated by any polynomial $p_2(s)$ of degree $k$, in particular, by $s^k$ and that $\mathcal{Y}_{W\dot{W}}^u$ can be annihilated by $p_u(s)p_2(s)$.

2. (dual) Let $\mathcal{Y}_W'$ be the maximal invariant space of an LSG $\mathcal{Y}_{W\dot{W}}^l$ contained in $\mathcal{Y}_{W\dot{W}}^l \circ W$. Let $k \equiv r(\mathcal{Y}_{W\dot{W}}^l \circ W + (\mathcal{Y}_{W\dot{W}}^l \circ \dot{W})_W) - r(\mathcal{Y}_W')$. Let $p_l(s)$ be the minimal annihilating polynomial of the genop $\mathcal{Y}_{W\dot{W}}^l \cap \mathcal{Y}_W'$. Show that $\mathcal{Y}_{W\dot{W}}^l + (\mathcal{Y}_W')_{\dot{W}}$ can be annihilated by any polynomial $p_2(s)$ of degree $k$, in particular, by $s^k$ and that $\mathcal{Y}_{W\dot{W}}^l$ can be annihilated by $p_l(s)p_2(s)$.

Answer

The statements are immediate consequences of the following lemma noting that in Problem 81, $\mathcal{Y}_{W\dot{W}}^u$ is USG, $\mathcal{Y}_{W\dot{W}}^l \subseteq \mathcal{Y}_{W\dot{W}}^u$, $\mathcal{Y}_{W\dot{W}}^u \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W$ and in Problem 83, $\mathcal{Y}_{W\dot{W}}^l$ is LSG, $\mathcal{Y}_{W\dot{W}}^l \supseteq \mathcal{Y}_{W\dot{W}}^u$, $\mathcal{Y}_{W\dot{W}}^u \times \dot{W} = \mathcal{Y}_{W\dot{W}}^l \times \dot{W}$.
**Lemma 81.** Let $\mathcal{Y}_{W\dot{W}}^1, \mathcal{Y}_{W\dot{W}}^2$ be generalized autonomous systems with $\mathcal{Y}_{W\dot{W}}^1 \supseteq \mathcal{Y}_{W\dot{W}}^2$.

(a) If $p(s)$ is any polynomial in $s$, then $p(\mathcal{Y}_{W\dot{W}}^1) \supseteq p(\mathcal{Y}_{W\dot{W}}^2)$.

(b) Let $\mathcal{Y}_{W\dot{W}}^1 \circ W = \mathcal{Y}_{W\dot{W}}^2 \circ W$. Then $\mathcal{Y}_{W\dot{W}}^2 + (\mathcal{Y}_{W\dot{W}}^1 \times \dot{W}) = \mathcal{Y}_{W\dot{W}}^1$.

(c) Let $\mathcal{Y}_{W\dot{W}}^1 \times \dot{W} = \mathcal{Y}_{W\dot{W}}^2 \times \dot{W}$. Then $\mathcal{Y}_{W\dot{W}}^1 \cap (\mathcal{Y}_{W\dot{W}}^2 \circ W) = \mathcal{Y}_{W\dot{W}}^2$.

(d) Let $\mathcal{Y}_{W\dot{W}}^1, \mathcal{Y}_{W\dot{W}}^2$ be USG and let $\mathcal{Y}_{W\dot{W}}^1 \circ W = \mathcal{Y}_{W\dot{W}}^2 \circ W$. If $p(\mathcal{Y}_{W\dot{W}}^2)$ is decoupled then so is $p(\mathcal{Y}_{W\dot{W}}^1)$.

(e) Let $\mathcal{Y}_{W\dot{W}}^1, \mathcal{Y}_{W\dot{W}}^2$ be LSG and let $\mathcal{Y}_{W\dot{W}}^1 \times \dot{W} = \mathcal{Y}_{W\dot{W}}^2 \times \dot{W}$. If $p(\mathcal{Y}_{W\dot{W}}^1)$ is decoupled then so is $p(\mathcal{Y}_{W\dot{W}}^2)$.

*Proof.* (a) If $\mathcal{Y}_{W\dot{W}}^1 \supseteq \mathcal{Y}_{W\dot{W}}^2$, it is clear that

$$ (\mathcal{Y}_{W\dot{W}}^1)^{(k)} \supseteq (\mathcal{Y}_{W\dot{W}}^2)^{(k)}, \quad \lambda^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^1)^{(k)} \supseteq \lambda^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^2)^{(k)}, \\ \lambda^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^1)^{(k)} + \dot{w}_1 \cdots \dot{w}_k \sigma^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^1)^{(m)} \supseteq \lambda^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^2)^{(k)} + \dot{w}_1 \cdots \dot{w}_k \sigma^{\dot{w}}(\mathcal{Y}_{W\dot{W}}^2)^{(m)}. $$

The result follows.

(b) Clearly RHS contains LHS. Let $(f_W, g_{\dot{W}}) \in \mathcal{Y}_{W\dot{W}}^1$.

Since $\mathcal{Y}_{W\dot{W}}^1 \circ W = \mathcal{Y}_{W\dot{W}}^2 \circ W$, for some $g'_{\dot{W}}$, $(f_W, g'_{\dot{W}}) \in \mathcal{Y}_{W\dot{W}}^2 \supseteq \mathcal{Y}_{W\dot{W}}^1$.

Therefore, $g_{\dot{W}} - g'_{\dot{W}} \in \mathcal{Y}_{W\dot{W}}^1 \times \dot{W}$, so that

$$ (f_W, g'_{\dot{W}}) + (0_W, g_{\dot{W}} - g'_{\dot{W}}) = (f_W, g_{\dot{W}}) \in \mathcal{Y}_{W\dot{W}}^2 + \mathcal{Y}_{W\dot{W}}^1 \times \dot{W}. $$

Thus LHS contains RHS as required.

(c) This is dual to the previous part.

(d) From the first part of the present lemma, we have that $p(\mathcal{Y}_{W\dot{W}}^1) \supseteq p(\mathcal{Y}_{W\dot{W}}^2)$.

Since $\mathcal{Y}_{W\dot{W}}^1, \mathcal{Y}_{W\dot{W}}^2$ are USG, by the first part of Lemma 66, we have that

$$ p(\mathcal{Y}_{W\dot{W}}^1) \circ W = \mathcal{Y}_{W\dot{W}}^1 \circ W, \quad p(\mathcal{Y}_{W\dot{W}}^2) \circ W = \mathcal{Y}_{W\dot{W}}^2 \circ W. $$

Since we are given that $\mathcal{Y}_{W\dot{W}}^1 \circ W = \mathcal{Y}_{W\dot{W}}^2 \circ W$, we have that $p(\mathcal{Y}_{W\dot{W}}^1) \circ W = p(\mathcal{Y}_{W\dot{W}}^2) \circ W$.

By the second part of the present lemma, we have that

$$ p(\mathcal{Y}_{W\dot{W}}^2) + p(\mathcal{Y}_{W\dot{W}}^1) \times \dot{W} = p(\mathcal{Y}_{W\dot{W}}^2) + (0_W \oplus p(\mathcal{Y}_{W\dot{W}}^1) \times \dot{W}) = p(\mathcal{Y}_{W\dot{W}}^1). $$

If $p(\mathcal{Y}_{W\dot{W}}^2)$ is decoupled, it is clear that so is $p(\mathcal{Y}_{W\dot{W}}^2) + p(\mathcal{Y}_{W\dot{W}}^1) \times \dot{W}$. The result follows.

(e) This is dual to the previous part and follows using the second part of Lemma 66 (the dual of first part of Lemma 66).

<figure><img src="image_9.png" /></figure>

1. We have seen in the solution to Problems 80 and 81, that we can choose a genop $\mathcal{Y}_{W\dot{W}}^{new} \subseteq \mathcal{Y}_{W\dot{W}}^u$ with $\mathcal{Y}_{W\dot{W}}^{new} \circ W = \mathcal{Y}_{W\dot{W}}^u \circ W$ in such a way that $\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W$ has any desired annihilating polynomial
of degree $k$, where $k \equiv r(\mathcal{Y}_W) - r(\mathcal{Y}_W^{com})$, $\mathcal{Y}_W^{com} \equiv \mathcal{Y}_{W\dot{W}}^u \times W \cap (\mathcal{Y}_{W\dot{W}}^u \times \dot{W})_W$. Now $p_2(s)$ annihilates $\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W$, $\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W \subseteq \mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W$ and $\mathcal{Y}_W = (\mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W) \circ W = (\mathcal{Y}_{W\dot{W}}^{new} \cap \mathcal{Y}_W) \circ W$. Therefore, by part (d) of Lemma 81, it follows that $p_2(s)$ annihilates $\mathcal{Y}_{W\dot{W}}^u \cap \mathcal{Y}_W$. By part (b) of Lemma 81, we have $\mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_{W\dot{W}}^u \times \dot{W})_W = \mathcal{Y}_{W\dot{W}}^u$, so that (since $\mathcal{Y}_W \supseteq (\mathcal{Y}_{W\dot{W}}^u \times \dot{W})_W$) $\mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_W)_{\dot{W}} = \mathcal{Y}_{W\dot{W}}^u + (\mathcal{Y}_W)_{\dot{W}}$. Now $p_u(s)$ annihilates $\mathcal{Y}_{W\dot{W}}^{new} + (\mathcal{Y}_W)_{\dot{W}}$ and $p_u(s)p_2(s)$ annihilates $\mathcal{Y}_{W\dot{W}}^{new}$. By part (d) of Lemma 81, it follows that $p_u(s)p_2(s)$ also annihilates $\mathcal{Y}_{W\dot{W}}^1$.

2. Part 2 of the problem is dual to part 1. Its solution follows by duality from the solution to part 1, using the solutions to Problems 82 and 83.

## 17. Pole placement through output feedback

*(This section is based on Section 16.)*

The output feedback problem for a dynamical system $\mathcal{Y}_{W\dot{W}UY}$ is to compute a $\mathcal{Y}_{UY}$ such that $\mathcal{Y}_{W\dot{W}UY} \leftrightarrow \mathcal{Y}_{UY}$ is a genep with a desired minimal annihilating polynomial and if the problem is infeasible, to prove that it is so. The ideas of Section 16 can be modified to solve this problem in the important special case where either input or output is one dimensional. This treatment is from [15].

**Problem 85.** Sketch the procedure for solving the output feedback problem when the dynamical system is in the state-input-output form $\dot{w} = Aw + Bu, y = Cw$ with $\mathcal{Y}_{UY}$ one dimensional.

### Answer

As in Problem 79, we restrict our transformations of the matrices in question to the controllable space and the main object which we use for modifying matrices is a full Krylov sequence.

We consider the modification of a full Krylov sequence $(w^0, \dots, w^k)$ to another $(v^0, \dots, v^k)$, through the rule, taking $\sigma_0 = 1$,

$$ (v^0 | \dots | v^k) \begin{bmatrix} 1 & \sigma_1 & \dots & \dots & \sigma_k \\ 0 & 1 & \dots & \dots & \sigma_{k-1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 0 & 1 \end{bmatrix} = (w^0 | \dots | w^k). \quad (64) $$

If $s^k + d_1 s^{k-1} + \dots + d_k, s^k + b_1 s^{k-1} + \dots + b_k$, are respectively the annihilating polynomials of the matrices with full Krylov sequences $(w^0, \dots, w^k), (v^0, \dots, v^k)$, then we must have (proceeding as in Problem 79),

$$ \begin{bmatrix} 1 & \sigma_1 & \dots & \sigma_k \\ 0 & 1 & \dots & \sigma_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{bmatrix} \begin{pmatrix} d_k \\ d_{k-1} \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix} b_k \\ b_{k-1} \\ \vdots \\ 1 \end{pmatrix} \quad (65) $$

which is equivalent to

$$ \begin{bmatrix} 1 & d_1 & \dots & d_k \\ 0 & 1 & \dots & d_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{bmatrix} \begin{pmatrix} \sigma_k \\ \sigma_{k-1} \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix} b_k \\ b_{k-1} \\ \vdots \\ 1 \end{pmatrix}. \quad (66) $$

The above corresponds to the matrix $A$ being transformed through state feedback to $A + BF$, where the state feedback matrix $F$ has rank one. The output feedback transforms the matrix $A$ to the matrix $A+BKC$, where $K$ is the output feedback matrix. When $K$ has rank one it corresponds to those state feedbacks where
($\sigma_1, \dots, \sigma_k) \in \text{row}(C[w^0|\dots|w^{k-1}])$ (Theorems 82 and 85). This essentially characterizes all matrices of the form $A+BKC$, ‘reachable’ from $(A, B, C)$ through rank one output feedback.

A least square solution to this equation under the condition that $(\sigma_1, \dots, \sigma_k) \in \text{row}(C[w^0|\dots|w^{k-1}])$ can be used to build a sequence $(1, \sigma_1, \dots, \sigma_k)$ and transform the full Krylov sequence $(w^0, \dots, w^k)$ to $(v^0, \dots, v^k)$. The latter will have an annihilating polynomial closest in $l_2$ norm of coefficient vectors to $s^k + b_1s^{k-1} + \dots + b_k$. We call this the rank one update to the original annihilating polynomial. These ideas can be used in practice to handle the multi input - multi output case also (see Problem 89).

**Remark 8.** In this section we have used the notation of [15]. The only difference from that of Section 16, is that we use a ‘$\sigma$-matrix’ to move from a sequence $(v^0, \dots, v^k)$ to a sequence $(w^0, \dots, w^k)$, rather than a ‘$\lambda$-matrix’ to move from a sequence $(w^0, \dots, w^k)$ to a sequence $(v^0, \dots, v^k)$.

**Problem 86.** Prove the following result which characterizes the systems obtainable through output feedback from a dynamical system in the state-input-output form.

**Theorem 82.** Let a dynamical system be defined by $\dot{w} = Aw + Bu, y = Cw$, where $A, B, C$ respectively are $k \times k, k \times m$ and $p \times k$. Let $\hat{A}$ be an $k \times k$ matrix. Then $\hat{A} = A + BKC$ for some $m \times p$ matrix $K$ iff

1. for every $w \in \mathbb{R}^k$, $\hat{A}w = Aw + Bu$ for some $u \in \mathbb{R}^m$, and

2. $\hat{A}w = Aw$ whenever $Cw = 0$.

Answer

*Proof.* (Only if) The necessity is immediate by taking $u = KCw$ and by noting that $\hat{A}w = Aw + BKCw = Aw$, when $Cw = 0$.

(If) Let $w^1, \dots, w^k$, be linearly independent vectors. Let $u^1, \dots, u^k$, be such that

$$ \dot{w}^i = \hat{A}w^i = Aw^i + Bu^i, \quad i = 1, \dots, k. $$

Choose $F$ such that

$$ F[w^1|\dots|w^k] = [u^1|\dots|u^k]. $$

This is always possible since $[w^1|\dots|w^k]$ is an invertible matrix.

Thus $\hat{A}[w^1|\dots|w^k] = A[w^1|\dots|w^k] + B[u^1|\dots|u^k] = (A+BF)[w^1|\dots|w^k]$, i.e., $\hat{A} = A+BF$.

Let the columns of $\hat{B}$ be a maximal linearly independent set of the columns of $B$, so that $\hat{A} = A+BF = A + \hat{B}\hat{F}$, for some $\hat{F}$. Now when $Cw = 0$, we have $\hat{A}w = (A + \hat{B}\hat{F})w$, so that $\hat{B}\hat{F}w = 0$. Since columns of $\hat{B}$ are linearly independent, this means $\hat{F}w = 0$ when $Cw = 0$.

Thus (denoting the row space of a matrix $Q$ by $\text{row}(Q)$) $(\text{row}(\hat{F}))^{\perp} \supseteq (\text{row}(C))^{\perp}$ so that $\text{row}(\hat{F}) \subseteq \text{row}(C)$.

This means that there exists a matrix $\hat{K}$ such that $\hat{F} = \hat{K}C$. Now we can write $B = (\hat{B}|B^2)$ and $\hat{B}\hat{F} = (\hat{B}|B^2)\begin{pmatrix} \hat{F} \\ 0 \end{pmatrix}$, so that $F = \begin{pmatrix} \hat{F} \\ 0 \end{pmatrix} = \begin{pmatrix} \hat{K} \\ 0 \end{pmatrix} C$. We thus have $\hat{A} = A + BF = A + BKC$. $\square$

**Problem 87.** 1. The following result is a translation of Theorem 82 of Problem 86 to the framework of the present chapter. It is an immediate consequence of Theorem 1. Show that the conditions of Theorem 82 are equivalent to those of Theorem 83.

**Theorem 83.** Let $\mathcal{V}_{W\dot{W}UY}$ be a dynamical system and $\mathcal{V}_{W\dot{W}}$ be a genaut. Then $\mathcal{V}_{W\dot{W}} = \mathcal{V}_{W\dot{W}UY} \leftrightarrow \mathcal{V}_{UY}$, for some $\mathcal{V}_{UY}$ iff

1. $\mathcal{V}_{W\dot{W}UY} \circ W \dot{W} \supseteq \mathcal{V}_{W\dot{W}}$ and

2. $\mathcal{V}_{W\dot{W}UY} \times W \dot{W} \subseteq \mathcal{V}_{W\dot{W}}$.
Answer

Let $\mathcal{Y}_{W\dot{W}UY}$ be a dynamical system defined by

$$ \dot{w} = Aw + Bu, \qquad (67) $$

$$ y = Cw. \qquad (68) $$

Let $\mathcal{Y}_{W\dot{W}}$ be defined by $\dot{w} = \hat{A}w$. Theorem 82 states that $\hat{A} = A + BKC$ for some $m \times p$ matrix $K$ iff

(a) (Theorem 82 (1)) for every $w \in \mathbb{R}^k$, $\hat{A}w = Aw + Bu$ for some $u \in \mathbb{R}^m$, and

(b) (Theorem 82 (2)) $\hat{A}w = Aw$ whenever $Cw = 0$.

Observe that $\mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}U$ is the solution space of $\dot{w} = Aw + Bu$.

Let Theorem 82(1) be satisfied and let $(w, \dot{w})$ be s.t. $\dot{w} = \hat{A}w = Aw + Bu$ for some $u$. This means $(w, \dot{w})$ belongs to $\mathcal{Y}_{W\dot{W}}$ only if it belongs to $(\mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}U) \circ W\dot{W} = \mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}$, i.e., only if $\mathcal{Y}_{W\dot{W}UY} \circ W\dot{W} \supseteq \mathcal{Y}_{W\dot{W}}$. Thus Theorem 82(1) implies Theorem 83(1).

Next, suppose $\mathcal{Y}_{W\dot{W}UY} \circ W\dot{W} \supseteq \mathcal{Y}_{W\dot{W}}$, i.e., $(\mathcal{Y}_{W\dot{W}UY} \circ W\dot{W}U) \circ W\dot{W} \supseteq \mathcal{Y}_{W\dot{W}}$. This means whenever $(w, \dot{w})$ belongs to $\mathcal{Y}_{W\dot{W}}$, i.e., satisfies $\dot{w} = \hat{A}w$, there must exist some $u$ such that $\dot{w} = Aw + Bu$. Thus Theorem 83(1) implies Theorem 82(1).

Let Theorem 82(2) be satisfied. The space $\mathcal{Y}_{W\dot{W}UY} \times W\dot{W}$ is the collection of all $(w, \dot{w})$ obtained from Equations 67, 68 by setting $u, y$ to zero, i.e., by setting $u = 0$ in Equation 67 and $y = 0$ in Equation 68.

Now setting $u = 0$ in Equation 67 is the same as writing $\dot{w} = Aw$ and setting $y = 0$ in Equation 68 is the same as setting $Cw = 0$.

So if $\hat{A}w = Aw$ whenever $Cw = 0$, we must have that every member of $\mathcal{Y}_{W\dot{W}UY} \times W\dot{W}$ also satisfies $\dot{w} = \hat{A}w$, i.e., belongs to $\mathcal{Y}_{W\dot{W}}$. Thus Theorem 82(2) implies Theorem 83(2).

Next, suppose $\mathcal{Y}_{W\dot{W}UY} \times W\dot{W} \supseteq \mathcal{Y}_{W\dot{W}}$. So when $u, y$ are set to zero in Equations 67, 68, we must have $(w, \dot{w})$ belonging to $\mathcal{Y}_{W\dot{W}}$, i.e., satisfying $\dot{w} = \hat{A}w$. When $u$ is set to zero we have $\dot{w} = Aw$ and when $y$ is set to zero we have $Cw = 0$. It follows that when $Cw = 0$, we must have $Aw = \hat{A}w$. Thus Theorem 83(2) implies Theorem 82(2).

**Definition 84.** $\sigma^{(k+1)}$ denotes the Toeplitz upper triangular matrix

$$ \begin{bmatrix} \sigma_0 & \sigma_1 & \cdots & \cdots & \sigma_k \\ 0 & \sigma_0 & \sigma_1 & \cdots & \sigma_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_0 & \sigma_1 \\ 0 & 0 & \cdots & 0 & \sigma_0 \end{bmatrix} \qquad (69) $$

We will take $\sigma_0 = 1$.

**Problem 88.** In Problem 79 we presented an algorithm for constructing a state feedback $\mathcal{Y}_{WU}$ for a dynamical system $\mathcal{Y}_{W\dot{W}UY}$ with controllable space $\mathcal{Y}_W$ so that the resulting genop $(\mathcal{Y}_{W\dot{W}UY} \leftrightarrow \mathcal{Y}_{WU}) \cap \mathcal{Y}_W$ has a desired minimal annihilating polynomial (provided it satisfies a degree condition). A key idea there was that, for the state feedback case, if an annihilating polynomial is achievable by a general state feedback matrix $F$, it is also achievable by a matrix $F'$ of column rank one. The column rank one algorithm is easy to extend to the output feedback case. Prove the following result which presents the basis for this algorithm.

**Theorem 85.** Let

$$ \dot{w} = Aw + Bu \qquad (70) $$

$$ y = Cw. \qquad (71) $$
be a set of equations where A, B, C respectively are $k \times k, k \times m$ and $p \times k$ real matrices with the columns of B and the rows of C being linearly independent.

Let $(w^0, \dots, w^k)$ be a full Krylov sequence for A, with $w^0 \in \text{col}(B)$ and let $(v^0|\dots|w^k)\sigma^{(k+1)} = (w^0|\dots|w^k)$. We then have

1. $(v^0, \dots, w^k)$ is a full Krylov sequence for $\hat{A}$, where $\hat{A}$ is such that for $w \in \mathbb{R}^k$, $\hat{Aw} = Aw + w^0u$, with $u = -(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w$.

2. Let $\hat{A}$ be as in the statement of the previous part. Then $\hat{Aw} = Aw$ for $Cw = 0$ iff $(\sigma_1, \dots, \sigma_k) \in \text{row}(C(w^0|\dots|w^{k-1}))$.

3. Let $w^0 = B\mu$. Then $\hat{A} = A + BF$, where $F = -\mu(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}$;

4. $\hat{A} = A + BF = A + BKC$, if $(\sigma_1, \dots, \sigma_k) = \rho^T C(w^0|\dots|w^{k-1})$ and $K = -\mu\rho^T$.

Answer

*Proof.* We first note that by the definition of $\sigma^{(k)}$ and since $(w^0|\dots|w^k)\sigma^{(k+1)} = (w^0|\dots|w^k)$, we must have $(v^0|\dots|w^{k-1})\sigma^{(k)} = (w^0|\dots|w^{k-1})$ and $(v^0|\dots|w^k) \begin{bmatrix} \sigma_1, \dots, \sigma_k \\ \sigma^{(k)} \end{bmatrix} = (w^1|\dots|w^k)$, with $v^0 = w^0$.

1. Let $w = (w^0|\dots|w^{k-1})\beta$ and let $\hat{Aw} = Aw + w^0u$, where $u = -(\sigma_1, \dots, \sigma_k)\beta = -(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w$. Then, $\hat{Aw} = Aw + w^0u = Aw - w^0(\sigma_1, \dots, \sigma_k)\beta = (w^1|\dots|w^k)\beta - w^0(\sigma_1, \dots, \sigma_k)\beta = (w^1|\dots|w^k)\beta - v^0(\sigma_1, \dots, \sigma_k)\beta = (v^0|\dots|w^k) \begin{bmatrix} \sigma_1, \dots, \sigma_k \\ \sigma^{(k)} \end{bmatrix} \beta - v^0(\sigma_1, \dots, \sigma_k)\beta = (v^1|\dots|w^k)\sigma^{(k)}\beta$. Thus if $w = (w^0|\dots|w^{k-1})\sigma^{(k)}\beta$, we have $\hat{A}(w^0|\dots|w^{k-1})\sigma^{(k)}\beta = (w^1|\dots|w^k)\sigma^{(k)}\beta$. Therefore $\hat{A}(w^0|\dots|w^{k-1}) = (w^1|\dots|w^k)$, so that $(w^0|\dots|w^k)$ is a full Krylov sequence for $\hat{A}$.

2. We have $(w^0|\dots|w^k) = (v^0|\dots|w^k)\sigma^{(k+1)}$, i.e.,

$$ 
\begin{array}{ccc}
w^0 & = & v^0 \\
w^1 & = & v^1 + \sigma_1 v^0 \\
\vdots & \vdots & \vdots \\
w^k & = & v^k + \sigma_1 v^{k-1} + \dots + \sigma_k v^0.
\end{array}
$$

We note that since $\hat{Av}^j = v^{j+1}$, $j = 0, \dots, k-1$ and $w^i = v^i + \sigma_1 v^{i-1} + \dots + \sigma_i v^0$, we must have $\hat{Aw}^i = v^{i+1} + \sigma_1 v^i + \dots + \sigma_i v^1$. We then have

$$ \hat{Aw}^i = w^{i+1} = \hat{Aw}^i + \sigma_{i+1} v^0 = \hat{Aw}^i + \sigma_{i+1} w^0. $$

Thus,

$$ A(w^0|\dots|w^{k-1}) = \hat{A}(w^0|\dots|w^{k-1}) + w^0(\sigma_1, \dots, \sigma_k). $$

Let $w \equiv (w^0|\dots|w^{k-1})\beta$. Then

$$ \hat{Aw} = A(w^0|\dots|w^{k-1})\beta = \hat{A}(w^0|\dots|w^{k-1})\beta + w^0(\sigma_1, \dots, \sigma_k)\beta. $$

Therefore,

$$ \hat{Aw} = \hat{A}w \quad \text{iff} $$

$w^0(\sigma_1, \dots, \sigma_k)\beta = w^0(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w = 0$, i.e., iff (since $w^0 \neq 0$),

$$ (\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w = 0. $$

Thus, $\hat{Aw} = \hat{A}w$ for $Cw = 0$ iff

$$ (\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w = 0 \quad \text{whenever} \quad Cw = 0, $$
i.e., iff $(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1} \in \text{row}[C]$,

i.e., iff $(\sigma_1, \dots, \sigma_k) \in \text{row}[C(w^0|\dots|w^{k-1})]$.

3. In the proof of the first part, we saw that when $w \equiv (w^0|\dots|w^{k-1})\beta$, we have

$$ \hat{A}w = Aw - w^0(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w. $$

Since $w^0 = B\mu$, it follows that

$$ \hat{A}w = Aw - B\mu(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w. $$

Setting $F \equiv -\mu(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w$, we get the required result.

4. In the proof of the previous part we saw that

$$ \hat{A}w = Aw - B\mu(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1}w. $$

Let $(\sigma_1, \dots, \sigma_k) = \rho^T C(w^0|\dots|w^{k-1})$. If $K \equiv -\mu\rho^T$ we have $-\mu(\sigma_1, \dots, \sigma_k)(w^0|\dots|w^{k-1})^{-1} = -\mu\rho^T C = KC$ and $\hat{A}w = (A + BKC)w$. $\square$

**Problem 89.** Let the dynamical system be defined through

$$ \begin{bmatrix} S_{\dot{W}} & S_W & S_U & S_Y \end{bmatrix} \begin{pmatrix} \dot{w} \\ w \\ u \\ y \end{pmatrix} = 0. \qquad (72) $$

Let us suppose its constraints are equivalent to $\dot{w} = Aw + Bu$, $y = Cw$. Usually, in a large dynamical system, the number of input and output variables would be far less than the dimension of $w$. Explicit computation of $B$ and $C$ would not be numerically expensive. We will assume that $B, C$ are explicitly available but not $A$, since it is sufficient for our procedure to compute its full Krylov sequence as in Problem 80. Let us suppose the matrix $B$ has a single column. (If $C$ has a single row we could work with the dual system.) Let $A$ have the minimal annihilating polynomial $d_0s^k + \dots + d_k$. Suppose the desired minimal annihilating polynomial is $b_0s^k + \dots + b_k$. We need to find, if it exists, a matrix $K$, such that $A+BKC$ has the desired annihilating polynomial, and if it does not exist, prove that it does not. Sketch an algorithm for doing this. How does this algorithm help in solving the multiple input multiple output case in practice?

*Answer*

Firstly, by Theorem 85, we need to find a sequence $(\sigma_0, \dots, \sigma_k)$ such that Equation 66 is satisfied. This ensures rank one state feedback. Next, by part 4 of the same theorem, we must have $(\sigma_1, \dots, \sigma_k) \in \text{row}(C(w^0|\dots|w^{k-1}))$. These two conditions are together necessary and sufficient.

For typographical convenience we rewrite Equation 66 as follows.

$$ (\sigma_0 \quad \sigma_1 \quad \dots \quad \sigma_k) \begin{bmatrix} d_0 & d_1 & \dots & d_k \\ 0 & d_0 & \dots & d_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & 0 & d_0 \end{bmatrix} = (b_0 \quad b_1 \quad \dots \quad b_k). \qquad (73) $$

We note that $\sigma_0, d_0, b_0$ all equal 1. Therefore,

$$ (0 \quad \sigma_1 \quad \dots \quad \sigma_k) \begin{bmatrix} d_0 & d_1 & \dots & d_k \\ 0 & d_0 & \dots & d_{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & d_0 \end{bmatrix} = (b_0 \quad b_1 \quad \dots \quad b_k) - (d_0 \quad d_1 \quad \dots \quad d_k), \qquad (74) $$
i.e.,

$$ (\sigma_1 \cdots \sigma_k) \begin{bmatrix} d_0 & d_1 & \cdots & d_{k-1} \\ 0 & d_0 & \cdots & d_{k-2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & d_0 \end{bmatrix} = (b_1 \cdots b_k) - (d_1 \cdots d_k), \qquad (75) $$

Now by Theorem 85, part 2, we must have

$$ (\sigma_1 \cdots \sigma_k) = (\rho_1 \cdots \rho_p) C(w^0 | \cdots | w^{k-1}), \qquad (76) $$

for some $(\rho_1, \cdots, \rho_p)$. Thus we need to solve the equation

$$ (\rho_1 \cdots \rho_p) C(w^0 | \cdots | w^{k-1}) \begin{bmatrix} d_0 & d_1 & \cdots & d_{k-1} \\ 0 & d_0 & \cdots & d_{k-2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & d_0 \end{bmatrix} = (b_1 \cdots b_k) - (d_1 \cdots d_k). \qquad (77) $$

As a preliminary to solving this equation, we can project right side vector of the Equation 77 onto the row space of

$$ Q \equiv C(w^0 | \cdots | w^{k-1}) \begin{bmatrix} d_0 & d_1 & \cdots & d_{k-1} \\ 0 & d_0 & \cdots & d_{k-2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & d_0 \end{bmatrix}. \qquad (78) $$

If the projection equals the right side vector of the Equation 77, we compute

$$ (\sigma_1, \cdots, \sigma_k) = (\rho_1, \cdots, \rho_p) C(w^0 | \cdots | w^{k-1}) $$

and thence

$$ (v^0 | \cdots | v^k) = (w^0 | \cdots | w^k) (\sigma^{(k+1)})^{-1}. $$

By Theorem 85, part 2, the matrix with the full Krylov sequence $(v^0 | \cdots | v^k)$ has the form $A+BKC$, where $K = -(\rho_1, \cdots, \rho_p)$. This matrix has the annihilating polynomial $b_0s^k + \cdots + b_k$.

Since the matrix $Q$ has rank $p \le k$, the Equation 77 need not have a solution. In this case the projection will not agree with the right side vector and we can conclude that there is no matrix of the form $A+BKC$ whose annihilating polynomial is $b_0s^k + \cdots + b_k$. Since we are dealing with matrices over the real field, the above procedure through projection is the usual solution in the least square sense.

One way of handling the multi-input multi-output case, is to work with a random vector in $col(B)$ as a matrix $B^1 = BT_1$ and try to solve the output feedback problem of $\dot{w} = Aw + B^1\hat{u}^1$, $y = Cw$. We move from $d_0s^k + \cdots + d_k$ to $b_0^1s^k + \cdots + b_k^1$ and from $\omega(0) := (\omega^0(0), \cdots, \omega^k(0))$ to $\omega(1) := (\omega^0(1), \cdots, \omega^k(1))$ by the above procedure. Let us call $b_0^1s^k + \cdots + b_k^1$ as a rank one update to $d_0s^k + \cdots + d_k$ towards $b_0s^k + \cdots + b_k$. At this stage we have the representation of the dynamical system $\dot{w} = (A+B^1F_1)w + Bu = (A+BT_1K^1C)w + Bu$, $y = Cw$, where $(A+BT_1K^1C)$ has the full Krylov sequence $\omega(1) := (\omega^0(1), \cdots, \omega^k(1))$. The matrix $K^1$ can be computed as in part 4 of Theorem 85. We now pick another random vector in $col(B)$ as a matrix $B^2 = BT_2$ and obtain the full Krylov sequence $\omega(2) := (\omega^0(2), \cdots, \omega^k(2))$ of $(A+B^1F_1 + B^2F_2) = (A + B(T_1K^1 + T_2K^2)C)$. If this process is repeated $n$ times we get a matrix $(A + B(\Sigma_{i=1}^n(T_iK^i))C)$ with a full Krylov sequence $\omega(n) := (\omega^0(n), \cdots, \omega^k(n))$. This corresponds to the output feedback $u = Ky = (\Sigma_{i=1}^n(T_iK^i))y$.

Some numerical experiments were performed to test

* the efficacy of the above algorithm for checking if a desired annihilating polynomial can be achieved through output feedback and

* to examine if the algorithm can be used to shift eigenvalues to desired locations.

The results, which are encouraging, are available in [15].
<figure><img src="image_10.png" /><figcaption>Figure 5: An RC circuit</figcaption></figure>

## 18. Network based dynamical systems

This section illustrates ideas related to dynamical systems for the special case of electrical networks. The first problem is to show how the state-input-output form fits into the definition of emulators. For the rest, the description is entirely 'implicit' in the sense that all the derived entities are also in terms of electrical networks obtained by simple graph theoretic algorithms from the original network.

### 18.1. Emulator for network based dynamical system

**Problem 90.** Consider the dynamical system $\mathcal{V}_{W\dot{W}UY}$ represented by the circuit $\mathcal{N}$ in Fig 5. Take all capacitors of value 1F and all resistors of value 1Ω.

1. Construct the defining constraints of $\mathcal{V}_{W\dot{W}UY}$.

2. Build an emulator $\mathcal{V}_{P\dot{P}UY}$ based on state-input-output equations $\dot{w}=Aw+Bu, y=Cw$, for $\mathcal{V}_{W\dot{W}UY}$. Show that $\mathcal{V}_{WP}^1$ can be different from $\mathcal{V}_{\dot{W}\dot{P}}^2$ for this emulator.

3. Show that the minimal annihilating polynomial of the genop $\mathcal{V}_{W\dot{W}UY} \times W\dot{W}Y \circ W\dot{W}$ has constant terms. Build an emulator $\mathcal{V}_{Q\dot{Q}UY}$ for this dynamical system such that the minimal annihilating polynomial of the genop $\mathcal{V}_{Q\dot{Q}UY} \times Q\dot{Q}Y \circ Q\dot{Q}$ has no constant terms.

**Answer**

1. $\mathcal{V}_{W\dot{W}UY}$ is the solution space of the equations given below. Here the W variables are $v_{C1}, v_{C2}, v_{C3}$, the $\dot{W}$ variables are $\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3}$, and the M variables are $j_5, v_6, v_5, i_6$.

$$ \begin{pmatrix} \dot{v}_{C1} \\ \dot{v}_{C2} \\ \dot{v}_{C3} \end{pmatrix} = \begin{bmatrix} -2/3 & 0 & 0 \\ 1/3 & 0 & 0 \\ 1/3 & 0 & 0 \end{bmatrix} \begin{pmatrix} v_{C1} \\ v_{C2} \\ v_{C3} \end{pmatrix} + \begin{bmatrix} 2/3 \\ -1/3 \\ -1/3 \end{bmatrix} v_6 + \begin{bmatrix} 2/3 \\ -1/3 \\ -1/3 \end{bmatrix} j_5 \quad (79a) $$

$$ 0 = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} \begin{pmatrix} v_{C1} \\ v_{C2} \\ v_{C3} \end{pmatrix} \quad (79b) $$

$$ \begin{pmatrix} i_6 \\ v_5 \end{pmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 0 & 0 \end{bmatrix} \begin{pmatrix} v_{C1} \\ v_{C2} \\ v_{C3} \end{pmatrix} + \begin{bmatrix} -1 \\ 0 \end{bmatrix} v_6 + \begin{bmatrix} 0 \\ 0 \end{bmatrix} j_5. \quad (79c) $$

2. Since P variables and W variables have to be disjoint and so also the variables $\dot{W}$ and $\dot{P}$ we define the new P, $\dot{P}$ variables $v'_{C1}, v'_{C2}, \dot{v}'_{C1}, \dot{v}'_{C2}$ taking $v'_{C1} = v_{C1}, v'_{C2} = v_{C2}, \dot{v}'_{C1} = \dot{v}_{C1}, \dot{v}'_{C2} = \dot{v}_{C2}$. The
dynamical system $\mathcal{Y}_{P\dot{P}UY}$, is the solution space of the state and output equations (of the circuit in Figure 5) given below:

$$ \begin{pmatrix} \dot{v}'_{C1} \\ \dot{v}'_{C2} \end{pmatrix} = \begin{bmatrix} -2/3 & 0 \\ 1/3 & 0 \end{bmatrix} \begin{pmatrix} v'_{C1} \\ v'_{C2} \end{pmatrix} + \begin{bmatrix} 2/3 \\ -1/3 \end{bmatrix} v_6 + \begin{bmatrix} 2/3 \\ -1/3 \end{bmatrix} j_5 \quad (80a) $$

$$ \begin{pmatrix} i_6 \\ v_5 \end{pmatrix} = \begin{bmatrix} 1 & 0 \\ -1 & 0 \end{bmatrix} \begin{pmatrix} v'_{C1} \\ v'_{C2} \end{pmatrix} + \begin{bmatrix} -1 \\ 0 \end{bmatrix} v_6 + \begin{bmatrix} 0 \\ 0 \end{bmatrix} j_5. \quad (80b) $$

The dynamical system pair $\{\mathcal{Y}_{W\dot{W}UY}, \mathcal{Y}_{P\dot{P}UY}\}$ is $\mathcal{E}$-linked and the two dynamical systems are emulators of each other.
We show this by building a suitable $\mathcal{E}$-linkage $\{\mathcal{Y}_{WP}^1, \mathcal{Y}_{WP}^2\}$ for this pair. Observe that the constraint on $v_{C1}, v_{C2}, v_{C3}$ is

$$ v_{C1} + v_{C2} + v_{C3} = 0. $$

The constraints on $\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3}$, are

$$ \begin{pmatrix} \dot{v}_{C1} + \dot{v}_{C2} + \dot{v}_{C3} \\ \dot{v}_{C2}/C_2 - \dot{v}_{C3}/C_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. $$

Thus the space of all vectors $(v_{C1}, v_{C2}, v_{C3})$ is the space spanned by the rows of

$$ \begin{bmatrix} 2 & -1 & -1 \\ 0 & 1 & -1 \end{bmatrix}. $$

Similarly the space of all vectors $(\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3})$ is the space spanned by the row

$$ \begin{bmatrix} 2 & -1 & -1 \end{bmatrix}. $$

The space $\mathcal{Y}_{WP}^1$ can be the space of all vectors $(v_{C1}, v_{C2}, v_{C3}, v'_{C1}, v'_{C2})$ spanned by the rows of

$$ \begin{bmatrix} 2 & -1 & -1 & 2 & -1 \\ 0 & 1 & -1 & 0 & 1 \end{bmatrix}. $$

The space $\mathcal{Y}_{WP}^2$ can be the space of all vectors $(\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3}, \dot{v}'_{C1}, \dot{v}'_{C2})$ spanned by the row

$$ \begin{bmatrix} 2 & -1 & -1 & 2 & -1 \end{bmatrix}. $$

One can verify just by inspection that

$$ \mathcal{Y}_{W\dot{W}UY} \leftrightarrow (\mathcal{Y}_{WP}^1 \oplus \mathcal{Y}_{\dot{W}\dot{P}}^2) = \mathcal{Y}_{P\dot{P}UY}, \quad \mathcal{Y}_{P\dot{P}UY} \leftrightarrow (\mathcal{Y}_{WP}^1 \oplus \mathcal{Y}_{\dot{W}\dot{P}}^2) = \mathcal{Y}_{W\dot{W}UY}, \quad (81) $$

and also that all the following ‘dot-cross’ conditions are satisfied :

$$ \begin{gathered} \mathcal{Y}_{WP}^1 \circ W = \mathcal{Y}_{W\dot{W}UY} \circ W, \quad \mathcal{Y}_{WP}^1 \times W \subseteq \mathcal{Y}_{W\dot{W}UY} \times W, \quad \mathcal{Y}_{\dot{W}\dot{P}}^2 \circ \dot{W} = \mathcal{Y}_{W\dot{W}UY} \circ \dot{W}, \quad \mathcal{Y}_{\dot{W}\dot{P}}^2 \times \dot{W} = \mathcal{Y}_{W\dot{W}UY} \times \dot{W}, \\ \mathcal{Y}_{WP}^1 \circ P = \mathcal{Y}_{P\dot{P}UY} \circ P, \quad \mathcal{Y}_{WP}^1 \times P \subseteq \mathcal{Y}_{P\dot{P}UY} \times P, \quad \mathcal{Y}_{\dot{W}\dot{P}}^2 \circ \dot{P} = \mathcal{Y}_{P\dot{P}UY} \circ \dot{P}, \quad \mathcal{Y}_{\dot{W}\dot{P}}^2 \times \dot{P} = \mathcal{Y}_{P\dot{P}UY} \times \dot{P}. \end{gathered} $$

This is equivalent to working with the reduced set of variables $v_{C1}, v_{C2}, \dot{v}_{C1}, \dot{v}_{C2}$ when we move from $W$ to $P$ and $\dot{W}$ to $\dot{P}$ variables. It must be noted that other linkages would also work in this case. For instance we could have taken both $\mathcal{Y}_{WP}^1$ and $\mathcal{Y}_{\dot{W}\dot{P}}^2$ to be spanned by the vectors

$$ \begin{bmatrix} 2 & -1 & -1 & 2 & -1 \\ 0 & 1 & -1 & 0 & -1 \end{bmatrix}. $$
However, this latter linkage does not reveal as much about the relationship between the emulators as the linkage defined earlier and in this case, the conditions

$$ \mathcal{V}_{\dot{W}\dot{P}}^2 \circ \dot{W} \supseteq \mathcal{V}_{W\dot{W}UY} \circ \dot{W}, \quad \mathcal{V}_{\dot{W}\dot{P}}^2 \circ \dot{P} \supseteq \mathcal{V}_{P\dot{P}UY} \circ \dot{P} $$

are not satisfied with equality.

3. To show that the emulator need not capture the zero eigenvalue situation, we define the new $Q, \dot{Q}$ variables $v_{C1}$, $\dot{v}_{C1}$ taking $v_{C1}'' = v_{C1}, \dot{v}_{C1}'' = \dot{v}_{C1}$. The dynamical system $\mathcal{V}_{Q\dot{Q}UY}$, is the solution space of the equations given below:

$$ (\dot{v}_{C1}'' ) = [-2/3] (v_{C1}'') + [2/3] v_6 + [2/3] j_5 \quad (82a) $$

$$ \begin{pmatrix} i_6 \\ v_5 \end{pmatrix} = \begin{bmatrix} 1 \\ -1 \end{bmatrix} (v_{C1}'') + \begin{bmatrix} -1 \\ 0 \end{bmatrix} v_6 + \begin{bmatrix} 0 \\ 0 \end{bmatrix} j_5. \quad (82b) $$

The dynamical system pair $\{\mathcal{V}_{W\dot{W}UY}, \mathcal{V}_{Q\dot{Q}UY}\}$ is $\mathcal{E}$-linked and the two dynamical systems are emulators of each other.

We show this by building a suitable $\mathcal{E}$-linkage $\{\mathcal{V}_{WQ}^1, \mathcal{V}_{\dot{W}\dot{Q}}^2\}$ for this pair. As before, the space of all vectors $(v_{C1}, v_{C2}, v_{C3})$ is the space spanned by the rows of

$$ \begin{pmatrix} 2 & -1 & -1 \\ 0 & 1 & -1 \end{pmatrix}. $$

Similarly the space of all vectors $(\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3})$ is the space spanned by the row

$$ (2 \quad -1 \quad -1). $$

The space $\mathcal{V}_{WQ}^1$ can be the space of all vectors $(v_{C1}, v_{C2}, v_{C3}, v_{C1}'')$ spanned by the rows of

$$ \begin{bmatrix} 2 & -1 & -1 & 2 \\ 0 & 1 & -1 & 0 \end{bmatrix}. $$

The space $\mathcal{V}_{\dot{W}\dot{Q}}^2$ can be the space of all vectors $(\dot{v}_{C1}, \dot{v}_{C2}, \dot{v}_{C3}, \dot{v}_{C1}'')$ spanned by the row

$$ [2 \quad -1 \quad -1 \quad 2]. $$

One can verify just by inspection that

$$ \mathcal{V}_{W\dot{W}UY} \leftrightarrow (\mathcal{V}_{WQ}^1 \oplus \mathcal{V}_{\dot{W}\dot{Q}}^2) = \mathcal{V}_{Q\dot{Q}UY}, \mathcal{V}_{Q\dot{Q}UY} \leftrightarrow (\mathcal{V}_{WQ}^1 \oplus \mathcal{V}_{\dot{W}\dot{Q}}^2) = \mathcal{V}_{W\dot{W}UY}, \quad (83) $$

and also that all the following ‘dot-cross’ conditions are satisfied :

$$ \mathcal{V}_{WQ}^1 \circ W = \mathcal{V}_{W\dot{W}UY} \circ W, \mathcal{V}_{WQ}^1 \times W = \mathcal{V}_{W\dot{W}UY} \times W, \quad \mathcal{V}_{\dot{W}\dot{Q}}^2 \circ \dot{W} = \mathcal{V}_{W\dot{W}UY} \circ \dot{W}, \mathcal{V}_{\dot{W}\dot{Q}}^2 \times \dot{W} = \mathcal{V}_{W\dot{W}UY} \times \dot{W}, $$

$$ \mathcal{V}_{WQ}^1 \circ Q = \mathcal{V}_{Q\dot{Q}UY} \circ Q, \mathcal{V}_{WQ}^1 \times Q = \mathcal{V}_{Q\dot{Q}UY} \times Q, \quad \mathcal{V}_{\dot{W}\dot{Q}}^2 \circ \dot{Q} = \mathcal{V}_{Q\dot{Q}UY} \circ \dot{Q}, \mathcal{V}_{\dot{W}\dot{Q}}^2 \times \dot{Q} = \mathcal{V}_{Q\dot{Q}UY} \times \dot{Q}. $$

This is equivalent to working with the reduced set of variables $v_{C1}, \dot{v}_{C1}$, when we move from $W$ to $Q$ and $\dot{W}$ to $\dot{Q}$ variables.

The original dynamical system $\mathcal{V}_{W\dot{W}UY}$ defined by Equation 79 results in the system $\mathcal{V}_{W\dot{W}} := \mathcal{V}_{W\dot{W}UY} \times W\dot{W}Y \circ W\dot{W}$ (when input is set to zero and output is kept free), defined by

$$ \begin{pmatrix} \dot{v}_{C1} \\ \dot{v}_{C2} \\ \dot{v}_{C3} \end{pmatrix} = \begin{bmatrix} -2/3 & 0 & 0 \\ 1/3 & 0 & 0 \\ 1/3 & 0 & 0 \end{bmatrix} \begin{pmatrix} v_{C1} \\ v_{C2} \\ v_{C3} \end{pmatrix}. \quad (84a) $$
<figure><img src="image_11.png" /><figcaption>Figure 6: An RLCEJ Network and its multiport decomposition into capacitive multiport and (static + L) multiport</figcaption></figure>

This system has zero eigenvalues, i.e., its minimal annihilating polynomial has no constant term. The emulator dynamical system $\mathcal{V}_{Q\dot{Q}UY}$ defined by Equation 82 results in the system $\mathcal{V}_{Q\dot{Q}} := \mathcal{V}_{Q\dot{Q}UY} \times Q\dot{Q}Y \circ Q\dot{Q}$ (when input is set to zero and output is kept free), defined by

$$ (\dot{v}_{C1}) = [-2/3] (v_{C1}) \qquad (85a) $$

It is clear that this system has no zero eigenvalues, i.e., its minimal annihilating polynomial has constant term. However, knowing $v_{C1}(t)$ and the initial condition $v_{C2}(0)$ it is easy to compute $v_{C1}(t), v_{C2}(t), v_{C3}(t)$ without solving a differential equation.

Since $\dot{v}_{C2}(t) = -1/2 \dot{v}_{C1}(t) = \dot{v}_{C3}(t)$, we have $v_{C1}(t) = v_{C1}(t)$, $v_{C2}(t) = v_{C2}(0) - 1/2(v_{C1}(t) - v_{C1}(0))$, $v_{C3}(t) = v_{C3}(0) - 1/2(v_{C1}(t) - v_{C1}(0))$ (see Problems 92, 93). Thus the dynamics of $\mathcal{V}_{W\dot{W}UY}$ is fully determined by that of $\mathcal{V}_{Q\dot{Q}UY}$.

**Remark 9.** The following problems involve multiport decomposition of an electrical network. It is convenient here to take both the current and voltage of a port branch to have the same direction (unlike in Sections 10, 11).

**Problem 91.** Outline the topological procedure of multiport decomposition for building an emulator. For an electrical network containing capacitors, inductors, sources and static devices (Figure 6), show how to build an emulator (as in Figure 6(b),(c), Figure 7 (e),(f),(g)) by a linear time graph theoretic algorithm. Give an explicit description of this emulator of $\mathcal{V}_{W\dot{W}M}$, the GDS corresponding to the network $\mathcal{N}$.

Answer

Topological procedure for emulator construction

**Step 1.** Decompose the network $\mathcal{N}$ into two multiports $\mathcal{N}_{CP_1}, \mathcal{N}_{2P_1}$ and the port connection diagram $\mathcal{G}_{P_1P_2}$ with minimum number of ports as in Fig 6. Here $\mathcal{N}_{CP_1}$ contains all the capacitors and $\mathcal{N}_{2P_1}$, all the other devices.

It can be shown that in any multiport decomposition with minimum number of ports, the ports will not contain cutsets or circuits of the graphs which figure in the decomposition.
<figure><img src="image_12.png" /><figcaption>Figure 7: Multiport decomposition of (static + L) multiport into static multiport and inductive multiport</figcaption></figure>

[A linear time algorithm for doing this, based only on the graph of the network, is given in Subsection 7. This is justified in [5] and [8]. For general vector space based systems slower decomposition algorithms are available in the same references.]

Figure 6 shows (a) an RLCEJ Network $\mathcal{N}$, its multiport decomposition into (b) the capacitive multiport $\mathcal{N}_{CP_C}$, (c) the port connection diagram $\mathcal{G}_{P_C P_1}$, and (d) the (static + L) multiport $\mathcal{N}_{2P_1}$.

**Step 2.** Decompose the network $\mathcal{N}_{2P_1}$ into two multiports $\mathcal{N}_{P_1 SP_2}$, $\mathcal{N}_{LP_L}$ and the port connection diagram $\mathcal{G}_{P_2 P_L}$ with minimum number of ports as in Figure 7. Here $\mathcal{N}_{LP_L}$ contains all the inductors and $\mathcal{N}_{P_1 SP_2}$, all the static devices such as resistors, linear controlled sources, input and output ports of $\mathcal{N}$, the ‘old’ ports $P_1$ (which were present in the multiport $\mathcal{N}_{2P_1}$ during the decomposition of $\mathcal{N}$ into $\mathcal{N}_{CP_C}$, $\mathcal{N}_{2P_1}$ and the port connection diagram $\mathcal{G}_{P_C P_1}$), and the new ports $P_2$ that arose when $\mathcal{N}_{2P_1}$ was decomposed into two multiports and a port connection diagram.

Figure 7 shows the (static + L) multiport (d), its multiport decomposition into (e) the static multiport $\mathcal{N}_{P_1 SP_2}$, (f) the port connection diagram $\mathcal{G}_{P_2 P_L}$, and (g) the inductive multiport $\mathcal{N}_{LP_L}$.

Let us denote the original GDS $\mathcal{Y}_{\dot{v}M}$ corresponding to the network $\mathcal{N}$ by $\mathcal{Y}_{\dot{v}C i_L \dot{v}C i_L M}$ since the latter notation is natural for RLC networks. The set $M$ contains all the input and output variables. In this case, they are *ui*, *uv*, *yi*, *yv*.

The emulator for this GDS is $\mathcal{Y}_{v_{PC} i_{PL} \dot{v}_{PC} i_{PL} M}$ which is represented implicitly by the three multiports $\mathcal{N}_{CP_C}$, $\mathcal{N}_{P_1 SP_2}$, $\mathcal{N}_{LP_L}$, and the port connection diagrams $\mathcal{G}_{P_C P_1}$, and $\mathcal{G}_{P_2 P_L}$.

The $\mathcal{E}$-linkage for the mutual emulators $\{\mathcal{Y}_{v_{C} i_{L} \dot{v}_{C} i_{L} M}, \mathcal{Y}_{v_{PC} i_{PL} \dot{v}_{PC} i_{PL} M}\}$ is $\mathcal{Y}_{v_{C} i_{L} v_{PC} i_{PL}} \oplus \mathcal{Y}_{\dot{v}_{C} i_{L} \dot{v}_{PC} i_{PL}}$.

The linkage $\mathcal{Y}_{v_{C} i_{L} v_{PC} i_{PL}} := \mathcal{Y}^{v}(\mathcal{G}_{EC E_{PC}}) \oplus \mathcal{Y}^{i}(\mathcal{G}_{EL E_{PL}})$, while the linkage $\mathcal{Y}_{\dot{v}_{C} i_{L} \dot{v}_{PC} i_{PL}}$ can be expressed as $\mathcal{Y}_{\dot{v}_{C} \dot{v}_{PC}} \oplus \mathcal{Y}_{i_{L} i_{PL}}$. Here $\mathcal{Y}_{\dot{v}_{C} \dot{v}_{PC}}$ is obtained by solving the multiport $\mathcal{N}_{CP_C}$ using the constraints $\mathcal{Y}^{v}(\mathcal{G}_{EC E_{PC}})$ for $(\dot{v}_{C}, \dot{v}_{PC})$, the constraints $\mathcal{Y}^{i}(\mathcal{G}_{EC E_{PC}})$ for $(i_C, i_{PC})$ and the ‘device-characteristic’ constraints $i_C = C \dot{v}_C$. Similarly $\mathcal{Y}_{i_L i_{PL}}$ is obtained by solving the multiport $\mathcal{N}_{LP_L}$ using the constraints
$\mathcal{V}^i(\mathcal{G}_{E_L E_{P_L}})$ for $(\dot{i}_L, \dot{i}_{P_L})$, the constraints $\mathcal{V}^v(\mathcal{G}_{E_L E_{P_L}})$ for $(v_L, v_{P_L})$ and the 'device-characteristic' constraints $v_L = L \dot{i}_L$.

When the multiport decompositions involved are performed with minimal ports, it would turn out that
$$ \mathcal{V}_{v_C i_L \dot{v}_C i_L M} \circ \{v_C, i_L\} = \mathcal{V}_{v_C i_L v_{P_C} i_{P_L}} \circ \{v_C, i_L\}, $$

$$ \mathcal{V}_{v_C i_L \dot{v}_C i_L M} \times \{v_C, i_L\} = \mathcal{V}_{v_C i_L v_{P_C} i_{P_L}} \times \{v_C, i_L\}, $$

$$ \mathcal{V}_{v_C i_L \dot{v}_C i_L M} \circ \{\dot{v}_C, \dot{i}_L\} = \mathcal{V}_{\dot{v}_C i_L \dot{v}_{P_C} i_{P_L}} \circ \{\dot{v}_C, \dot{i}_L\}, $$

$$ \mathcal{V}_{v_C i_L \dot{v}_C i_L M} \times \{\dot{v}_C, \dot{i}_L\} = \mathcal{V}_{\dot{v}_C i_L \dot{v}_{P_C} i_{P_L}} \times \{\dot{v}_C, \dot{i}_L\}. $$

Similarly, it would turn out that $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M} \circ \{v_{P_C}, i_{P_L}\} = \mathcal{V}_{v_C i_L v_{P_C} i_{P_L}} \circ \{v_{P_C}, i_{P_L}\}$,

$$ \mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M} \times \{v_{P_C}, i_{P_L}\} = \mathcal{V}_{v_C i_L v_{P_C} i_{P_L}} \times \{v_{P_C}, i_{P_L}\}, $$

$$ \mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M} \circ \{\dot{v}_{P_C}, \dot{i}_{P_L}\} = \mathcal{V}_{\dot{v}_C i_L \dot{v}_{P_C} i_{P_L}} \circ \{\dot{v}_{P_C}, \dot{i}_{P_L}\}, $$

$$ \mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M} \times \{\dot{v}_{P_C}, \dot{i}_{P_L}\} = \mathcal{V}_{\dot{v}_C i_L \dot{v}_{P_C} i_{P_L}} \times \{\dot{v}_{P_C}, \dot{i}_{P_L}\}. $$

These are sufficient conditions for $\mathcal{V}_{v_C i_L v_{P_C} i_{P_L}} \oplus \mathcal{V}_{\dot{v}_C i_L \dot{v}_{P_C} i_{P_L}}$, to be the $\mathcal{E}$-linkage for
$\{\mathcal{V}_{v_C i_L \dot{v}_C i_L M}, \mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}\}$.

The original dynamic variables are $w = (v_C, i_L) = (v_{C1}, v_{C2}, v_{C3}, v_{C4}, i_{L1}, i_{L2}, i_{L3})$. These variables are not state variables because of the presence of capacitor loops and inductor cutsets which cause the voltages to form a dependent set and similarly the currents. A proper subset say $v_{C1}, v_{C2}, v_{C3}, i_{L1}, i_{L2}$ can be taken as the state variables. However, the network has capacitor cutsets and inductor loops which result in zero eigenvalues. For computational purposes, it is more convenient to work with the dynamic variables $(v_{P_C}, i_{P_L})$ which form a smaller subset than the set of state variables but from which the dynamics of the system can be inferred very easily (see Problems 90, 92, 93).

**Problem 92.** One of the uses of implicit linear algebra is to make dynamical system computations based on implicit descriptions. However, for greater clarity, for the network in Problem 91 give an explicit description of the dynamical system $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ and show how computations made on it can be easily translated to computations on $\mathcal{V}_{W \dot{W} M}$. Further, show (illustrating part 2 of Theorem 74) that the minimal annihilating polynomial of the original dynamical system has no constant terms whereas that of the emulator does have.

Answer

An explicit description for $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$.

**Step 1.** Using the constraints of $N_{CP_C}$, obtain the relationship $i_{P_C} = C_{P_C} \dot{v}_{P_C}$.
The constraints are

(a). $(\dot{v}_C, \dot{v}_{P_C}) \in \mathcal{V}^v(\mathcal{G}_{CP_C})$, where $\mathcal{G}_{CP_C}$ is the graph of $N_{CP_C}$. This is the same as satisfying the Kirchhoff voltage equations of $\mathcal{G}_{CP_C}$.

(b). $(i_C, i_{P_C}) \in \mathcal{V}^i(\mathcal{G}_{CP_C})$. This is the same as satisfying Kirchhoff current equations of $\mathcal{G}_{CP_C}$.

(c). $i_C = C \dot{v}_C$. Here $C$ is symmetric positive definite.

**Step 2.** Using the constraints of $N_{LP_L}$, obtain the relationship $i_{P_L} = L_{P_L} \dot{i}_{P_L}$.
The constraints are

(a). $(\dot{i}_L, \dot{i}_{P_L}) \in \mathcal{V}^i(\mathcal{G}_{LP_L})$, where $\mathcal{G}_{LP_L}$ is the graph of $N_{LP_L}$. This is the same as satisfying the Kirchhoff current equations of $\mathcal{G}_{LP_L}$.
(b). $(v_L, v_{P_L}) \in \mathcal{V}^v(\mathcal{G}_{LP_L})$. This is the same as satisfying Kirchhoff voltage equations of $\mathcal{G}_{LP_L}$.

(c). $v_L = L \dot{i}_L$. Here L is symmetric positive definite.

**Step 3.** Similarly using the constraints of $\mathcal{N}_{P_1SP_2}$, we obtain

$$ \begin{pmatrix} i_{P_1} \\ v_{P_2} \end{pmatrix} = \begin{bmatrix} H_{11} & H_{12} \\ H_{21} & H_{22} \end{bmatrix} \begin{pmatrix} v_{P_1} \\ i_{P_2} \end{pmatrix} + \begin{bmatrix} H_{13} \\ H_{23} \end{bmatrix} u \quad (86a) $$

$$ y = [H_{31} \ H_{32}] \begin{pmatrix} v_{P_1} \\ i_{P_2} \end{pmatrix} + [H_{33}]u. \quad (86b) $$

The hybrid matrix $H$ above is invertible because, in $\mathcal{N}_{P_1SP_2}$, given $i_{P_1}, v_{P_2}, u$, the variables $v_{P_1}, i_{P_2}$ are uniquely determined.

**Step 4.** Use the topological constraints of $\mathcal{G}_{P_1P_2}$ to transform $i_{P_1}$ to $i_{P_2}$ and $v_{P_1}$ to $v_{P_2}$. (This is always possible because when the port decomposition has minimum number of ports, the ports cannot contain circuits or cutsets of the port connection diagram. This means that the graph $\mathcal{G}_{P_1P_2}$ has $P_2, P_1$ as cospanning forests. From this it follows that voltage (current) of $P_2$ ($P_1$) can be written in terms of voltage (current) of $P_1$ ($P_2$).)

**Step 5.** Similarly use the topological constraints of $\mathcal{G}_{P_2P_1}$ to transform $i_{P_2}$ to $i_{P_1}$ and $v_{P_2}$ to $v_{P_1}$. (The graph $\mathcal{G}_{P_2P_1}$ has $P_2, P_1$ as cospanning forests.)

**Step 6.** The transformed version of Equation 86 now involves $i_{P_2}, v_{P_2}$ in place of $i_{P_1}, v_{P_1}$ and $v_{P_2}, i_{P_2}$.

**Step 7.** Now substitute $v_{P_2} = C_{P_2}\dot{v}_{P_2}, v_{P_1} = L_{P_1}\dot{i}_{P_1}$ in the above transformed equation to get rid of the variables $i_{P_2}, v_{P_2}$ and obtain

$$ \begin{pmatrix} \dot{v}_{P_2} \\ \dot{i}_{P_2} \end{pmatrix} = \begin{bmatrix} \hat{H}_{11} & \hat{H}_{12} \\ \hat{H}_{21} & \hat{H}_{22} \end{bmatrix} \begin{pmatrix} v_{P_2} \\ i_{P_2} \end{pmatrix} + \begin{bmatrix} \hat{H}_{13} \\ \hat{H}_{23} \end{bmatrix} u \quad (87a) $$

$$ y = [\hat{H}_{31} \ \hat{H}_{32}] \begin{pmatrix} v_{P_2} \\ i_{P_2} \end{pmatrix} + [\hat{H}_{33}]u. \quad (87b) $$

This final equation only involves $v_{P_2}, \dot{v}_{P_2}, i_{P_2}, \dot{i}_{P_2}$ and $u, y$ variables as required. The solution space of this equation is the dynamical system $\mathcal{V}_{v_{P_2}i_{P_2}\dot{v}_{P_2}i_{P_2}M}$. The minimal annihilating polynomial of this system has a constant term. This can be seen as follows. Using the positive definiteness of $C, L$ that of $C_{P_2}, L_{P_2}$ follows. From the invertibility of the hybrid matrix $H$ of $\mathcal{N}_{P_1SP_2}$, the topological conditions of $\mathcal{G}_{CP_2}, \mathcal{G}_{LP_2}$, and the invertibility of $C_{P_2}, L_{P_2}$, the invertibility of the above coefficient matrix $\hat{H}$ in Equation 87 follows. Therefore, the dynamical system described by Equation 87 has no zero eigenvalues, i.e., the minimal annihilating polynomial has a constant term. Since the capacitor voltages and inductor currents in the original dynamical system are dependent, this original system has zero eigenvalues, i.e., the minimal annihilating polynomial of the original system has no constant term.

We now show that $\mathcal{V}_{v_{P_2}i_{P_2}\dot{v}_{P_2}i_{P_2}M}$ captures the essential dynamics of the network and therefore of the dynamical system $\mathcal{V}_{W\dot{W}M}$, which it represents.

Using the constraints of the capacitive multiport $\mathcal{N}_{CP_2}$, we can write $\dot{v}_C = T_C\dot{v}_{P_2}$. (This is a network solution problem and here we are treating $(\dot{v}_C, \dot{v}_{P_2})$ as the voltage variables and $(i_C, i_{P_2})$ as the current variables of $\mathcal{N}_{CP_2}$. Now in $\mathcal{G}_{CP_2}$, the set of edges $P_2$ does not contain loops or cutsets (since the port decomposition is minimal). If the matrix $C$ is symmetric positive definite such a network will have a unique
solution for any given $i_{PC}$ or $\dot{v}_{PC}$.)

$$ 
\begin{aligned}
v_C(t) &= v_C(0) + T_C \int_0^t \dot{v}_{PC} dt \\
&= v_C(0) + T_C(v_{PC}(t) - v_{PC}(0)).
\end{aligned}
$$

Using the constraints of the inductive multiport $\mathcal{N}_{LP_L}$, we can write $\dot{i}_L = T_L \dot{i}_{PL}$. (This is a network solution problem and here we are treating $(\dot{i}_L, \dot{i}_{PL})$ as the current variables and $(v_L, v_{PL})$ as the voltage variables of $\mathcal{N}_{LP_L}$. Now in $\mathcal{G}_{LP_L}$, the set of edges $P_L$ does not contain loops or cutsets (since the port decomposition is minimal). If the matrix $L$ is symmetric positive definite such a network will have a unique solution for any given $v_{PL}$ or $\dot{i}_{PL}$.)

$$ 
\begin{aligned}
i_L(t) &= i_L(0) + T_L \int_0^t \dot{i}_{PL} dt \\
&= i_L(0) + T_L(i_{PL}(t) - i_{PL}(0)).
\end{aligned}
$$

We thus see that, even though $v_{PC}, i_{PL}$ are not state variables, their evolution in time along with $v_C(0), i_L(0)$ fully determines $v_C(t), i_L(t)$. The notion of emulator is meant to capture this property of $\mathcal{Y}_{v_{PC}i_{PL}} \dot{v}_{PC} i_{PL} M$, with respect to $\mathcal{Y}_{W\dot{W}M} \equiv \mathcal{Y}_{v_Ci_L} \dot{v}_C i_{LM}$. Usually in the process of moving from the original system to the emulator we could lose invariant space information about zero eigenvalues of the system. In the present case, working with the emulator $\mathcal{Y}_{v_{PC}i_{PL}} \dot{v}_{PC} i_{PL} M$ does not give us information about the zero eigen-vectors of the original system which has to be independently provided. But the original system $\mathcal{Y}_{v_Ci_L} \dot{v}_C i_{LM}$ provides complete information about the emulator, namely, knowing $v_C(t), i_L(t)$, we can uniquely obtain $v_{PC}(t), i_{PL}(t)$.

## 18.2. Computation using the multiport decomposition based emulator

We assume that the static multiport $\mathcal{N}_{E_r, E_m, P'_C, P'_L}$ has a unique solution for arbitrary port conditions. This is true under mild genericity conditions if the ports contain no cutsets or circuits of the graph of the multiport. When the port decomposition is minimal the ports satisfy this condition.

**Problem 93.** Show, using the multiport decomposition based emulator of Problem 91, how to compute $\mathcal{Y}_{W\dot{W}} \leftrightarrow \mathcal{Y}_W$, when $\mathcal{Y}_M = \mathbf{0}_U \oplus \mathcal{F}_Y$ for a rLCEJ network as in Figure 6.

### Answer

We will only show, given a vector $w \in \mathcal{Y}_W$ how to find all $\dot{w}$ such that $(w, \dot{w}) \in \mathcal{Y}_{W\dot{W}}$. In the generic situation, this will be unique since for $w = 0, u = 0$ the only $\dot{w}$ consistent will be the zero vector. The space $\mathcal{Y}_{W\dot{W}LM} \leftrightarrow \mathcal{Y}_M$ is obtained by setting all input sources to zero. (in Figure 5, $v_E, i_J$ are short circuited and open circuited respectively). The space $\mathcal{Y}_{W\dot{W}}$ is equal to $(\mathcal{Y}_{W\dot{W}LM} \leftrightarrow \mathcal{Y}_M) \circ (\dot{W} \cup W)$.

Let $w \in \mathcal{Y}_W$. This is a vector $v_C, i_L$ in $\mathcal{N}$. There is a unique vector $v_{P'_C}, i_{P'_L}$ (through topological constraints in $\mathcal{G}_{E_C P_C}, \mathcal{G}_{E_L P_L}, \mathcal{G}_{P_C P'_C}, \mathcal{G}_{P_L P'_L}$ since $P_C, P'_C, P_L, P'_L$ do not form loops or cutsets in any of the graphs) corresponding to $v_C, i_L$. Impose $v_{P'_C}, i_{P'_L}$ onto the ports of $\mathcal{N}_{E_r, E_m, P'_C, P'_L}$ with the sources set to zero. As mentioned before, under mild genericity assumptions on the static characteristics, there will be a unique $i_{P'_C}, v_{P'_L}$ corresponding to this port condition. By solving this (static) multi-port we would get $i_{P'_C}, v_{P'_L}$ from which we can get $i_{PC}, v_{PL}$ through the topological constraints in $\mathcal{G}_{PC P'_C}$ and $\mathcal{G}_{PL P'_L}$.

We now solve the multi-port $\mathcal{N}_{E_C P_C}$ with currents $i_{PC}$ in the ports $P_C$ using the device-characteristics constraints $i_C = C \dot{v}_C$, KCL conditions of $\mathcal{G}_{E_C P_C}$ on $(i_C, i_{PC})$, KVL conditions of $\mathcal{G}_{E_C P_C}$ on $(\dot{v}_C, \dot{v}_{PC})$. This yields $\dot{v}_C$.

Similarly, we solve the multi-port $\mathcal{N}_{E_L P_L}$ with voltages $v_{PL}$ in the ports $P_L$ using the device-characteristics $v_L = L \frac{di_L}{dt}$, KVL conditions of $\mathcal{G}_{E_L P_L}$ on $(v_L, v_{PL})$, KCL conditions of $\mathcal{G}_{E_L P_L}$ on $(\frac{di_L}{dt}, \frac{di_{PL}}{dt})$. This yields $\frac{di_L}{dt}$. We then get the unique vector $\dot{w} = (\dot{v}_C, \frac{di_L}{dt})$ corresponding to the vector $w = (v_C, i_L)$. Observe that the computationally significant steps are the solutions of the three multi-ports.
**Problem 94.** Show, using the multiport decomposition based emulator of Problem 91, how to compute $\mathcal{V}_{WM} \leftrightarrow \mathcal{V}_{\dot{W}}$, when $\mathcal{V}_M = \mathbf{0}_U \oplus \mathcal{F}_Y$ for a rLCEJ network as in Figure 7.

**Answer**

To compute $\mathcal{V}_{WM} \leftrightarrow \mathcal{V}_{\dot{W}}$, we begin once again by setting all sources to zero. Let $\dot{w} = (\dot{v}_C, \frac{di_L}{dt}) \in \mathcal{V}_{\dot{W}}$. We will show how to find all $w$ such that $(w, \dot{w}) \in \mathcal{V}_{WM}$.

The first step is to compute all $w = (v_C, i_L)$ corresponding to $\dot{w} = 0$. We will show that generically the collection of all such $v_C$ is the voltage space of $\mathcal{G}_{E_C P_C} \times E_C$ and the collection of all such $i_L$ is the current space of $\mathcal{G}_{E_L P_L} \circ E_L$. Now $\dot{w} = 0$ implies $\dot{v}_C = 0$ and $\frac{di_L}{dt} = 0$. This implies $C \dot{v}_C = 0$ and $L \frac{di_L}{dt} = 0$. Hence $i_C = 0, v_L = 0$. Therefore in the multi-ports $\mathcal{N}_{E_C P_C}, \mathcal{N}_{E_L P_L}$, since $P_C, P_L$ do not contain cutsets, $i_{P_C} = 0, v_{P_L} = 0$. Using KCL, KVL of $\mathcal{G}_{P_C P'_C}, \mathcal{G}_{P_L P'_L}$ this implies $i_{P'_C} = 0, v_{P'_L} = 0$. In the multi-port $\mathcal{N}_{E_r E_m P'_C P'_L}$, the sources have already been set to zero (since $\mathcal{V}_M = \mathbf{0}_U \oplus \mathcal{F}_Y$). In this network $P'_C, P'_L$ contain no loops or cutsets even when all sources are set to zero. As mentioned before, under mild genericity conditions on the static devices, this network can be shown to have a unique solution for arbitrary values of $i_{P'_C}, v_{P'_L}$. So in particular if $i_{P'_C} = 0, v_{P'_L} = 0$ we would have only the zero solution. Hence $v_{P'_C}, i_{P'_L}$ are zero vectors. This means, through KCL, KVL of $\mathcal{G}_{P_C P'_C}, \mathcal{G}_{P_L P'_L}$ that $v_{P_C} = 0, i_{P_L} = 0$. The corresponding space of $v_C$ (with $v_{P_C} = 0$) would therefore be the space of solutions of KVL constraints of $\mathcal{G}_{E_C P_C}$ with $P_C$ short circuited, that is, the voltage space of $\mathcal{G}_{E_C P_C} \times E_C$. (Under minimal multi-port decomposition this is the space of solutions of KVL constraints of $\mathcal{G}$ with all branches other than the $C$ branches short circuited). The corresponding space of $i_L$ (with $i_{P_L} = 0$) can similarly be shown to be the space of KCL constraints of $\mathcal{G}_{E_L P_L}$ with $P_L$ open circuited, that is, the current space of $\mathcal{G}_{E_L P_L} \circ E_L$. (Under minimal multi-port decomposition this is the space of solutions of KCL constraints of $\mathcal{G}$ with all branches of $\mathcal{G}$ other than $L$ branches open circuited). Next, we compute a single $w^1 \in \mathcal{V}_W$ corresponding to a $\dot{w}^1 \in \mathcal{V}_{\dot{W}}$. Let $\dot{w}^1 \in \mathcal{V}_{\dot{W}}$. Now let $\dot{w}^1 = (\dot{v}_C, \frac{di_L^1}{dt})$. Using $i_C^1 = C \dot{v}_C, v_L^1 = L \frac{di_L^1}{dt}$ we get $i_C^1, v_L^1$. Using KVL, KCL of $\mathcal{G}_{E_C P_C}, \mathcal{G}_{E_L P_L}$, since $P_C, P_L$ contain no loops or cutsets in these graphs we can compute $i_{P_C}^1, v_{P_L}^1$ (uniquely). Using KCL, KVL of $\mathcal{G}_{P_C P'_C}, \mathcal{G}_{P_L P'_L}$ we can compute $i_{P'_C}^1, v_{P'_L}^1$. In the multi-port $\mathcal{N}_{E_r E_m P'_C P'_L}$, the sources have already been set to zero (since $\mathcal{V}_M = \mathbf{0}_U \oplus \mathcal{F}_Y$). As before we can compute $v_{P'_C}^1, i_{P'_L}^1$ uniquely. Through KCL, KVL of $\mathcal{G}_{P_L P'_L}, \mathcal{G}_{P_C P'_C}, v_{P_C}^1, i_{P_L}^1$ can be computed uniquely. One solution $v_C^1$ can be obtained by extending $P_C$ to a tree $t_C$ in $\mathcal{G}_{E_C P_C}$ assigning arbitrary voltages to branches in $t_C - P_C$ and hence by KVL of $\mathcal{G}_{E_C P_C}$, computing voltages for $E_C - t_C$. Similarly, one solution $i_L^1$ corresponding to $i_{P_L}^1$ can be obtained by extending $P_L$ to a co-tree $\bar{t}_L$ in $\mathcal{G}_{E_L P_L}$ assigning arbitrary currents to branches in $\bar{t}_L - P_L$ and hence by KCL of $\mathcal{G}_{E_L P_L}$ computing currents for $E_L - \bar{t}_L$. $v_C^1, i_L^1$ together constitute the desired $w^1 \in \mathcal{V}_W$.

The collection of all vectors $\mathcal{A}_C^1 \oplus \mathcal{A}_L^1$ corresponding to $v_{P_C}^1, i_{P_L}^1$ (and therefore also corresponding to $\dot{w}^1 = (\dot{v}_C, \frac{di_L^1}{dt})$) is obtained as follows: $\mathcal{A}_C^1 = v_C^1 + \mathcal{V}_C^0, \mathcal{A}_L^1 = i_L^1 + \mathcal{V}_L^0$, where $\mathcal{V}_C^0, \mathcal{V}_L^0$ correspond to $\dot{v}_C = 0, \frac{di_L}{dt} = 0$. In the above, the computations which involve only KCL, KVL are, being linear time, inexpensive. The significant computation is the one that involves solution of the multi-port $\mathcal{N}_{E_r E_m P'_C P'_L}$ for given $i_{P'_C}^1, v_{P'_L}^1$.

### 18.3. Building the adjoint implicitly for a network based dynamical system

The primal $\mathcal{N}$ (or rather its solution space $\mathcal{V}^{\text{sol}}(\mathcal{N})$), shown in Figure 8, is a GDSA (generalized dynamical system with additional variables) with the variables

$$v_C, i_L, i_C, v_L, \dot{v}_C, \dot{i}_L, v_R, i_R, u_i, u_v, y_i, y_v, v_{ui}, i_{uv}, v_{yi}, i_{yv}.$$

Of these the dynamical variables are $v_C, i_L, \dot{v}_C, \dot{i}_L$, the manifest variables $U$ are $u_i, u_v$, and the manifest variables $Y$ are $y_i, y_v$. The additional variables are $i_C, v_L, v_R, i_R, v_{ui}, i_{uv}, v_{yi}, i_{yv}$. For greater readability, we will make this total set of variables, the index set. For simplicity, in Problem 95, we assume the capacitor voltages are independent and so are the inductor currents. This means there are no topological constraints on $\dot{v}_C$ and on $\dot{i}_L$, which makes the treatment simpler. Next, in Problem 96, we use this construction and the
<figure><img src="image_13.png" /><figcaption>Figure 8: Primal RLCuy network and its adjoint RLCu'y' network</figcaption></figure>

emulator based on multiport decomposition, to build the adjoint for the more general case, where capacitor voltages and inductor currents are not independent. In this subsection we have, in the cases of the devices in the network, denoted the space satisfying the constraints by {$\mathit{constraints}$}, for instance in the case of the resistor $\mathcal{Y}_{vRiR}$ we have denoted it by {$v_R = Ri_R$}.

**Problem 95.** For the primal RLCuy network $\mathcal{N}$ shown in Figure 8 show how to build its (dynamical system) adjoint RLCu'y' network ($\mathcal{N}^a$ of the same figure).

Answer

We note that the *adjoint network*, as conventionally defined for electrical networks, would have a change of sign for some of the variables in comparison with the *dynamical system adjoint* of the dynamical system, defined by the original network (see [6]). We have adopted a notation where the adjoint network corresponds to the definition of adjoint dynamical systems. This has resulted in negative resistors, inductors and capacitors in the adjoint network.

Let $\mathcal{G}$ be the graph of the network. Let the device-characteristic constraints of the network be

$$i_C = C\dot{v}_C; \quad v_L = L\dot{i}_L; \quad v_R = Ri_R; \quad v_{yi} = 0; \quad i_{yv} = 0; \quad v_{ui} \text{ free, } i_{uv} \text{ free, }$$

where the matrices $C, L, R$ are symmetric positive definite. The original GDS (Generalized dynamical system) $\mathcal{Y}_{W\dot{W}UY}$ corresponding to $\mathcal{N}$ has the index set $\{v_C, i_L, \dot{v}_C, i_L, ui, uv, yi, yv\}$. We have,

$$\mathcal{Y}_{W\dot{W}UY} = [[\mathcal{Y}^{\text{top}}(\mathcal{N}) \leftrightarrow (\{v_R = Ri_R\} \oplus \mathbf{0}_{v_{yi}i_{yv}} \oplus \mathcal{F}_{v_{ui}i_{uv}})] \leftrightarrow [{i_C = C\dot{v}_C} \oplus \{v_L = L\dot{i}_L\}]].$$
Here we denote

$$\mathcal{Y}^v(\mathcal{G}) \oplus \mathcal{Y}^i(\mathcal{G}) \quad \text{by} \quad \mathcal{Y}^{\text{top}}(\mathcal{N}).$$

So, using the fact that $(\mathcal{Y}^v(\mathcal{G}))^\perp = \mathcal{Y}^i(\mathcal{G})$,

$$\mathcal{Y}_{W\dot{W}UY}^{\perp} = [[(\mathcal{Y}^v(\mathcal{G}) \oplus \mathcal{Y}^i(\mathcal{G}) \leftrightarrow (\{v_R = Ri_R\}^{\perp} \oplus \mathbf{0}_{v_{yi}i_{yv}}^{\perp} \oplus \mathcal{F}_{v_{ui}i_{uv}}^{\perp})] \rightleftharpoons [{i_C = C\dot{v}_C}^{\perp} \oplus \{v_L = L\dot{i}_L\}^{\perp}]].$$

We need to construct (using dashed variables for the adjoint system to avoid confusion with primal variables)

$$(\mathcal{Y}_{W\dot{W}UY}^{\perp})_{-\dot{W}'W'-Y'U'} = \mathcal{Y}_{W'\dot{W}'U'Y'}^{a}.$$

We will do this in stages and reach a space on a suitable set of variables corresponding to $W', \dot{W}', U', Y'$. We first make the following changes of variables: replace $v$ by $-i''$, $i$ by $-v''$, $\dot{v}_C$ by $q_C$, $i_L$ by $\psi_L$. We also
<figure><img src="image_14.png" /><figcaption>Figure 9: The primal network with port decomposition into capacitor, inductor and static multiports</figcaption></figure>

make use of $(\mathcal{Y}^v(\mathcal{G}))_i^\perp = \mathcal{Y}^i(\mathcal{G}); (\mathcal{Y}^i(\mathcal{G}))_v^\perp = \mathcal{Y}^v(\mathcal{G})$. So the above expression reduces to
$$ \left[ \left[ (\mathcal{Y}^i(\mathcal{G}))_{i''} \oplus (\mathcal{Y}^v(\mathcal{G}))_{v''} \right] \leftrightarrow (\{-Ri''_R = v''_R\} \oplus \mathcal{F}_{i''_{y''_i}v''_{y''_v}} \oplus \mathbf{0}_{i''_{u''_i}v''_{u''_v}}) \right] \right. \\ \left. \Rightarrow [\{Cv''_C = q_C\} \oplus \{Li''_L = \psi_L\}] \right]. $$

(Here $v''_C, i''_L$ are the common variables between the two sides of the '$\Leftrightarrow$' symbol.)

Next, change the names of the edges $yi, yv, ui, uv$ respectively to $u''v, u''i, y''v, y''i$ respectively so that the expression reduces to

$$ \left[ \left[ (\mathcal{Y}^i(\mathcal{G}))_{i''} \oplus (\mathcal{Y}^v(\mathcal{G}))_{v''} \right] \leftrightarrow (\{-Ri''_R = v''_R\} \oplus \mathcal{F}_{i''_{u''_i}v''_{u''_v}} \oplus \mathbf{0}_{i''_{y''_i}v''_{y''_v}}) \right] \right. \\ \left. \leftrightarrow [\{-Cv''_C = q_C\} \oplus \{-Li''_L = \psi_L\}] \right]. $$

This space is on the variables (which we also treat as index set) $i''_C, v''_L, q_C, \psi_L, u''v, u''i, y''i, y''v$.

We now rename $i''_C$ as $\dot{q}_C, v''_L$ as $\dot{\psi}_L$ and rename $y''v, y''i$ as $-y'v, -y'i$ and rename $v''_C, i''_L, i''_R, v''_R, u''v, u''i, y''i, y''v, v''_{u''i}, i''_{u''v}, i''_{y''v}, v''_{y''i}$, respectively as $v'_C, i'_L, i'_R, v'_R, u'_v, u'_i, -y'_i, -y'_v, v'_{u'_i}, i'_{u'_v}, -i'_{y'_v}, -v'_{y'_i}$. This results in the final expression which we would

obtain if we replace $i'_C, v'_L$ by $\dot{q}_C, \dot{\psi}_L$, respectively, in the expression
$$ \left[ \left[ (\mathcal{Y}^i(\mathcal{G}))_{i'} \oplus (\mathcal{Y}^v(\mathcal{G}))_{v'} \right] \leftrightarrow (\{-Ri'_R = v'_R\} \oplus \mathcal{F}_{i'_{u'_i}v'_{u'_v}} \oplus \mathbf{0}_{i'_{y'_i}v'_{y'_v}}) \right] \leftrightarrow [\{-Cv'_C = q_C\} \oplus \{-Li'_L = \psi_L\}] \right]. $$

The above constraints are those corresponding to the adjoint network $\mathcal{N}^a$ shown in Figure 8.

The resulting space corresponding to the above final expression is

$$ (\mathcal{Y}^\perp_{W\dot{W}UY})_{-\dot{W}'W'-Y'U'} = \mathcal{Y}^a_{W'\dot{W}'U'Y'} $$

Here, in the adjoint, $W' \equiv \{q_C, \psi_L\}, \dot{W}' \equiv \{\dot{q}_C, \dot{\psi}_L\}, U' \equiv \{u'_v, u'_i\}, Y' \equiv \{y'_i, y'_v\}$.

**Problem 96.** Consider the case, where the RLCuy network has capacitor loops and inductor cutsets as in Figure 9. Using the emulator based on multiport decomposition as described in Problem 91 build the adjoint of the dynamical system associated with the network.

### Answer

Let us denote the dynamical system described by the RLCuy network by $\mathcal{Y}_{v_C i_L \dot{v}_C i_L M}$. If we decompose the network into capacitor, inductor and static multiports we have the emulator
$\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ (as described in Problem 91) for $\mathcal{V}_{v_{C i_L} \dot{v}_{C i_L} M}$. To build the adjoint of $\mathcal{V}_{v_{C i_L} \dot{v}_{C i_L} M}$, we first build the adjoint of $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ and convert it through the $\mathcal{E}$-linkage as in Theorem 52 to the adjoint of $\mathcal{V}_{v_{C i_L} \dot{v}_{C i_L} M}$.

Note that in the static network, the port branches $P'_C, P'_L$ contain no loops or cutsets, since the multiport decomposition is minimal. We will build an intermediate network in which capacitors and inductors contain no loops or cutsets by replacing $P'_C, P'_L$ by suitable capacitors $\hat{C}_{P'_C}$ and inductors $\hat{L}_{P'_L}$. This will result in a dynamical system $\mathcal{V}_{v_{P'_C} i_{P'_L} \dot{v}_{P'_C} i_{P'_L} M}$ which will be an emulator for $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$. The adjoint of $\mathcal{V}_{v_{P'_C} i_{P'_L} \dot{v}_{P'_C} i_{P'_L} M}$ can be built as in Problem 95. Using the $\mathcal{E}$-linkage as in Theorem 52, this can be first converted to the adjoint of $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ and then to the adjoint of $\mathcal{V}_{v_{C i_L} \dot{v}_{C i_L} M}$.

We proceed as in Problem 91.

Using the constraints of $\mathcal{N}_{CP_C}$, obtain the relationship $i_{P_C} = C_{P_C} \dot{v}_{P_C}$. We note that the corresponding linkage

$$ \mathcal{V}_{i_{P_C} \dot{v}_{P_C}} = [(\mathcal{V}^v(\mathcal{G}_{CP_C}))_{\dot{v}_C \dot{v}_{P_C}} \oplus \mathcal{V}^i(\mathcal{G}_{CP_C})] \leftrightarrow \{i_C = C \dot{v}_C\}. $$

By using the topological conditions $(\mathcal{V}^v(\mathcal{G}_{P_C P'_C}))_{\dot{v}_{P_C} \dot{v}_{P'_C}}, \mathcal{V}^i(\mathcal{G}_{P_C P'_C})$ of the port connection graph $\mathcal{G}_{P_C P'_C}$ we obtain the relationship $i_{P'_C} = \hat{C}_{P'_C} \dot{v}_{P'_C}$, with the corresponding linkage

$$ \mathcal{V}_{i_{P'_C} \dot{v}_{P'_C}} = [(\mathcal{V}^v(\mathcal{G}_{CP_C}))_{\dot{v}_C \dot{v}_{P_C}} \oplus \mathcal{V}^i(\mathcal{G}_{CP_C})] \leftrightarrow \{i_C = C \dot{v}_C\} \leftrightarrow ((\mathcal{V}^v(\mathcal{G}_{P_C P'_C}))_{\dot{v}_{P_C} \dot{v}_{P'_C}} \oplus \mathcal{V}^i(\mathcal{G}_{P_C P'_C})) $$

Using the constraints of $\mathcal{N}_{LP_L}$, obtain the relationship $i_{P_L} = L_{P_L} \dot{i}_{P_L}$. We note that the corresponding linkage

$$ \mathcal{V}_{v_{P_L} \dot{i}_{P_L}} = [(\mathcal{V}^i(\mathcal{G}_{LP_L}))_{i_L \dot{i}_{P_L}} \oplus \mathcal{V}^v(\mathcal{G}_{LP_L})] \leftrightarrow \{v_L = L \dot{i}_L\}. $$

By using the topological conditions $\mathcal{V}^v(\mathcal{G}_{P_L P'_L}), (\mathcal{V}^i(\mathcal{G}_{P_L P'_L}))_{i_{P_L} \dot{i}_{P'_L}}$ of the port connection graph $\mathcal{G}_{P_L P'_L}$ we obtain the relationship $v_{P'_L} = \hat{L}_{P'_L} \dot{i}_{P'_L}$, with the corresponding linkage

$$ \mathcal{V}_{v_{P_L} \dot{i}_{P_L}} = [(\mathcal{V}^i(\mathcal{G}_{LP_L}))_{i_L \dot{i}_{P_L}} \oplus \mathcal{V}^v(\mathcal{G}_{LP_L})] \leftrightarrow \{v_L = L \dot{i}_L\} \leftrightarrow ((\mathcal{V}^i(\mathcal{G}_{P_L P'_L}))_{i_{P_L} \dot{i}_{P'_L}} \oplus \mathcal{V}^v(\mathcal{G}_{P_L P'_L})) $$

We now replace the port branches $P'_C, P'_L$ by capacitors $\hat{C}_{P'_C}$ and inductors $\hat{L}_{P'_L}$. The resulting dynamical system $\mathcal{V}_{v_{P'_C} i_{P'_L} \dot{v}_{P'_C} i_{P'_L} M}$ and $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ are mutual emulators with the $\mathcal{E}$-linkage
$$ \{ (\mathcal{V}_{v_{P_C} v_{P'_C}} \oplus \mathcal{V}_{i_{P_L} i_{P'_L}}), ((\mathcal{V}_{v_{P_C} v_{P'_C}} \dot{v}_{P_C} \dot{v}_{P'_C}) \oplus (\mathcal{V}_{i_{P_L} i_{P'_L}} \dot{i}_{P_L} \dot{i}_{P'_L})) \} $$
$$ \therefore \{ ((\mathcal{V}^v(\mathcal{G}_{P_C P'_C}) \oplus \mathcal{V}^i(\mathcal{G}_{P_L P'_L})), ((\mathcal{V}^v(\mathcal{G}_{P_C P'_C}) \dot{v}_{P_C} \dot{v}_{P'_C}) \oplus (\mathcal{V}^i(\mathcal{G}_{P_L P'_L}) \dot{i}_{P_L} \dot{i}_{P'_L})) \}. $$

The dynamical system $\mathcal{V}_{v_{C i_L} \dot{v}_{C i_L} M}$ is associated with the given RL Cuy network. This system and $\mathcal{V}_{v_{P_C} i_{P_L} \dot{v}_{P_C} i_{P_L} M}$ are mutual emulators with the $\mathcal{E}$-linkage
$$ \{ (\mathcal{V}^v(\mathcal{G}_{CP_C}) \oplus \mathcal{V}^i(\mathcal{G}_{LP_L})), (\mathcal{V}_{\dot{v}_C \dot{v}_{P_C}} \oplus \mathcal{V}_{i_C i_{P_L}}) \}, \text{ where} $$
$$ \mathcal{V}_{\dot{v}_C \dot{v}_{P_C}} \equiv [[(\mathcal{V}^v(\mathcal{G}_{CP_C}))_{\dot{v}_C \dot{v}_{P_C}} \oplus \mathcal{V}^i(\mathcal{G}_{CP_C})] \cap \{i_C = C \dot{v}_C\}] \circ \{\dot{v}_C, \dot{v}_{P_C}\}, $$
$$ \mathcal{V}_{i_L i_{P_L}} \equiv [[(\mathcal{V}^i(\mathcal{G}_{LP_L}))_{i_L i_{P_L}} \oplus \mathcal{V}^v(\mathcal{G}_{LP_L})] \cap \{v_L = L \dot{i}_L\}] \circ \{i_L, i_{P_L}\}. $$
$(\mathcal{V}_{\dot{v}_C \dot{v}_{P_C}}$ is obtained by solving the multiport on graph $\mathcal{G}_{CP_C}$ with KVL conditions on $\{\dot{v}_C, \dot{v}_{P_C}\}$, KCL conditions on $\{i_C, i_{P_C}\}$ and device-characteristic conditions $\{i_C = C \dot{v}_C\}$,
$\mathcal{V}_{i_L i_{P_L}}$ is obtained by solving the multiport on graph $\mathcal{G}_{LP_L}$ with KCL conditions on $\{i_L, i_{P_L}\}$, KVL conditions on $\{v_L, v_{P_L}\}$ and device-characteristic conditions $\{v_L = L \dot{i}_L\}.)$
For the convenience of the reader, we reproduce the relevant part of Theorem 52 below.

$$ \text{Let } \mathcal{V}_{P\dot{P}UY} = (\mathcal{V}_{WP}^1 \oplus \mathcal{V}_{\dot{W}\dot{P}}^2) \leftrightarrow \mathcal{V}_{W\dot{W}UY}. $$

$$ \text{Then } ((\mathcal{V}_{WP}^1)^\perp)_{\dot{W}-\dot{P}} \subseteq (\mathcal{V}_{\dot{W}-\dot{P}}^2)^\perp \text{ and } \mathcal{V}_{P\dot{P}U'Y'}^a = ((\mathcal{V}_{WP}^1)_{\dot{W}-\dot{P}}^\perp \oplus (\mathcal{V}_{\dot{W}-\dot{P}}^2)_{WP}^\perp) \leftrightarrow \mathcal{V}_{W\dot{W}U'Y'}^a, $$

To build the adjoint of $\mathcal{V}_{v_{C}i_{L}}\dot{v}_{C}i_{L}M$, we first build the adjoint of $\mathcal{V}_{v_{P'_{C}}i_{P'_{L}}}\dot{v}_{P'_{C}}i_{P'_{L}}M$ as in Problem 95, and convert it through the $\mathcal{E}$-linkage as in the statement of Theorem 52 above to the adjoint of $\mathcal{V}_{v_{P_{C}}i_{P_{L}}}\dot{v}_{P_{C}}i_{P_{L}}M$. Next, the adjoint of $\mathcal{V}_{v_{P_{C}}i_{P_{L}}}\dot{v}_{P_{C}}i_{P_{L}}M$ is converted to the adjoint of $\mathcal{V}_{v_{C}i_{L}}\dot{v}_{C}i_{L}M$, using the appropriate $\mathcal{E}$-linkage, described above.

# 19. Ad joints for behavioural systems

*(This section is based on Section 7 of [19] but is largely self contained.)*

The problems in this section present a possible way of bringing in the duality between the notions of ‘control’ and ‘observe’ in the context of behavioural system theory. We follow the treatment in [9].

A **behaviour** $\mathcal{B}_W$ is the solution set of a system of linear constant coefficient differential equations $(R[d/dt])w = 0$, where the entries of $w$ are $\mathcal{C}^\infty$ functions $w_1, \dots, w_q$ and $R[d/dt]$ is a matrix over $\Re[\xi]$ (i.e, the entries are real polynomials in $\xi$), with $\xi$ substituted by $d/dt$. We say $(R[d/dt])w = 0$, is a kernel representation for $\mathcal{B}_W$. The **module** $\mathcal{C}_W$ (collection of row vectors on the column set $W$, over the scalar domain $\Re[\xi] := \Re[\frac{d}{dt}]$, closed under addition and scalar multiplication) generated by the rows of $R[\xi]$ when $\mathcal{B}_W$ is the solution space of $(R[d/dt])w = 0$, is uniquely associated with $\mathcal{B}_W$ and this fact is expressed by $\mathcal{C}_W = \mathcal{C}(\mathcal{B}_W)$ or by $\mathcal{B}(\mathcal{C}_W) = \mathcal{B}_W$. If the rows of the matrix $R[\xi]$ are linearly independent, the module generated by them is said to have $R[\xi]$ as a **representative matrix**.

A square matrix $R[\xi]$ is said to be **unimodular** iff its determinant is a nonzero real number (i.e., does not involve the transcendental $\xi$). The Smith Canonical Form (SCF) of a matrix $R[\xi]$ is obtained from it by invertible row and column operations and has the form $\begin{pmatrix} D & 0 \\ 0 & 0 \end{pmatrix}$, where $D$ is a diagonal matrix with diagonal entries nonzero, and with $D_{ii}$ a factor of $D_{jj}$, whenever $j > i$. The SCF of $R[\xi]$ can be shown to be unique within nonzero real multiplications. We say a module is **unimodular** iff we can adjoin additional rows to one of its (therefore any of its) representative matrices $R[\xi]$ to make it unimodular. It is easy to show that this is possible iff the representative matrix $R[\xi]$ has a SCF of the form $(D | 0)$, where $D$ has only real entries. Such a matrix is said to be **row unimodular**. **Column unimodular** matrices are defined similarly. If the SCF is real but may have zero rows and columns we say the matrix is **g-unimodular**. A behaviour $\mathcal{B}_W$ is said to be **controllable** iff for each $w^1, w^2 \in \mathcal{B}_W$, there exists a $w \in \mathcal{B}$ and a $t' \ge 0$ such that $w(t) = w^1(t)$ for $t < 0$ and $w(t) = w^2(t - t')$ for $t \ge t'$. We say $\mathcal{B}_{WL}$ is **l-observable** iff $(R_w[d/dt])w + (R_l[d/dt])l_1 = 0$ and $(R_w[d/dt])w + (R_l[d/dt])l_2 = 0$ implies $l_1 = l_2$. It can be shown that a behaviour $\mathcal{B}$ is controllable iff the module $\mathcal{C}(\mathcal{B})$ associated with it is unimodular [20]. Also, when behaviour $\mathcal{B}_{WL}$ is represented by $(R_w[d/dt])w + (R_l[d/dt])l = 0$, it is l-observable iff $R_l[\xi]$ is column unimodular. The restriction $\mathcal{B}_{WL} \circ W$ of a behaviour to $W$ is the collection $\{w : (w, l) \in \mathcal{B}_{WL}\}$ and is denoted by $\mathcal{B}_{WL} \circ W$.

$$ \text{Let behaviour } \mathcal{B}_{WL} \text{ have the kernel representation } (R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0. $$

$$ \text{We define the adjoint } \mathcal{B}_{WL}^{adj} \text{ as having the kernel representation } \begin{pmatrix} I & -R_w^T \\ 0 & -R_l^T \end{pmatrix} \begin{pmatrix} \dot{w} \\ \hat{l} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. $$

We say $f_S, g_S$ are **orthogonal** to each other iff $\langle f_S, g_S \rangle = 0$. Given a collection of vectors $\mathcal{K}_S$ on $S$, we denote by $\mathcal{K}_S^*$, the collection of all vectors orthogonal to vectors in $\mathcal{K}_S$. We say $\mathcal{K}_S$ is **involutive** iff $\mathcal{K}_S$ and $\mathcal{K}_S^*$, are **complementary orthogonal** i.e., iff $(\mathcal{K}_S^*)^* = \mathcal{K}_S$.

**Problem 97.** When a behaviour $\mathcal{B}_{WL}$ is defined through $(R[d/dt])w + (R[d/dt])l = 0$, show how to construct a kernel representation for its restriction $\mathcal{B}_{WL} \circ W$. Hence show that $\mathcal{C}(\mathcal{B}_{WL}) \times W = \mathcal{C}(\mathcal{B}_{WL} \circ W)$.

Answer

A kernel representation for this restriction can be obtained as follows: rewrite the coefficient matrix of the kernel representation of $\mathcal{B}_{WL}$ through invertible row operations (with entries in $\Re[\xi]$ but determinant real nonzero) as
$$ \begin{bmatrix} R_{1w} & 0 \\ R_{2w} & R_{2l} \end{bmatrix}, $$

where the rows of $R_{2l}$ are linearly independent. Now the equation $(R_{2l}[d/dt])l = f$ always has a solution owing to the linear independence of the rows of the coefficient matrix. It follows that $B_{WL} \circ W$ has the kernel representation $(R_{1w}[d/dt])w = 0$. It is clear that the rows of $R_{1w}$ span $\mathcal{C}(B_{WL}) \times W$ and $R_{1w}w = 0$ is the behaviour $B_{WL} \circ W$.

**Problem 98.** Let the behaviour $\mathcal{B}_{XUY}$ have the state-input-output representation

$$ \begin{aligned} dx/dt &= Ax + Bu \\ y &= Cx + Du, \end{aligned} $$

Show that the system is x-observable/controllable in the behavioural sense iff it is observable/controllable in the conventional 'state' sense.

Answer

For studying the observability question we can work with $u = 0$ so that the system equations become

$$ \begin{aligned} dx/dt &= Ax \\ y &= Cx. \end{aligned} $$

We know that this system is observable in the conventional sense iff the matrix $$ \begin{pmatrix} -C \\ -CA \\ \vdots \\ -CA^{n-1} \end{pmatrix} $$ has rank $n$.

Now the defining equations of the system can be rewritten as

$$ \begin{pmatrix} I\xi - A & 0 \\ -C & I \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = 0 \qquad (88) $$

By row operations on the coefficient matrix (scalsars from $\Re[\xi]$) in Equation 88, we get the matrix

$$ \begin{pmatrix} I\xi - A & 0 \\ C & -I \\ CA & -I\xi \\ CA^2 & -I\xi^2 \\ \vdots & \vdots \\ CA^{n-1} & -I\xi^{n-1} \end{pmatrix} \qquad (89) $$

It can be seen that the first submatrix in the column partition is column g-unimodular (the condition for x- observability) iff the matrix $$ \begin{pmatrix} -C \\ -CA \\ \vdots \\ -CA^{n-1} \end{pmatrix} $$ has column rank $n$.

For studying the controllability question, we note that the system defined by

$$ dx/dt = Ax + Bu $$

is controllable in the conventional sense iff the matrix $(B|AB|\cdots|A^{n-1}B)$ is of rank $n$. This can also be seen to be the condition for the matrix $(I\xi - A|B)$ to be row unimodular, the condition for controllability in the behavioural sense.
**Problem 99.** Prove the following lemma on the involutive nature of modules generated by rows of g-unimodular matrices.

**Lemma 86.** 1. Let $\mathcal{K}$ be a collection of vectors over $\mathbb{R}[\xi]$ on $S$. Then $\mathcal{K}^*$ is unimodular.

2. Let $A$ be a $g$-unimodular matrix. Let $C$ be the module generated by the rows or columns of $A$. Then $C^{**} = C$.

*Answer*

*Proof.* 1. Let $K$ be a representative matrix for $\mathcal{K}$. The SCF of $K$ has the form $(D|0)$ and we have $PKQ = (D|0)$, i.e., $K = P^{-1}(D|0)Q^{-1}$, where $P, Q$ are unimodular. Let $K^* = P^T(0|I)Q^T$. The matrix $K^*$ is row unimodular and is a representative matrix for $\mathcal{K}^*$. Therefore the module $\mathcal{K}^*$ is unimodular.

2. The SCF of $A$ has the form $\begin{pmatrix} I & 0 \\ 0 & 0 \end{pmatrix}$ and $\mathcal{C}$ has a representative matrix $P(I|0)Q$, where $P, Q$, are unimodular. Arguing as in the previous part, it is clear that $(\mathcal{C}^*)^*$ also has the representative matrix $P(I|0)Q$, so that $\mathcal{C}^{**} = \mathcal{C}$. $\square$

**Problem 100.** Prove the following lemma which brings out the analogy between solutions of equations over $\mathbb{R}$ and over $\mathbb{R}[\xi]$.

**Lemma 87.** Let $A$ be an $m \times n$ $g$-unimodular matrix over $\mathbb{R}[\xi]$, $b$ an $m \times 1$ vector over $\mathbb{R}[\xi]$. Then $Ax = b$ has a solution (with $x$ a vector over $\mathbb{R}[\xi]$) iff for every $(1 \times m)$ vector $\lambda^T$ over $\mathbb{R}[\xi]$ we have $"\lambda^T A = 0" \Rightarrow "\lambda^T b = 0"$.

*Answer*

*Proof.* $Ax = b$ has a solution iff $b$ belongs to the column module $\mathcal{C}$ generated by columns of $A$, i.e., iff $b \in \mathcal{C}^{**}$ ($\mathcal{C} = \mathcal{C}^{**}$, since $A$ is $g$-unimodular), i.e., iff whenever $\lambda^T \in \mathcal{C}^*$ we also have $\lambda^T b = 0$, i.e., iff whenever $\lambda^T A = 0$, we also have $\lambda^T b = 0$. $\square$

**Problem 101.** Prove the following implicit duality theorem for unimodular modules.

**Theorem 88.** (The Implicit Duality Theorem for unimodular modules) Let $\mathcal{K}_{SP}, \mathcal{K}_{P}$ be unimodular modules on $S \uplus P, P$ respectively, such that $\mathcal{K}_{SP} + \mathcal{K}_{P}$ is also unimodular. Then,

(a) $(\mathcal{K}_{SP}^* \leftrightarrow \mathcal{K}_{P}^*)^* = \mathcal{K}_{SP} \leftrightarrow \mathcal{K}_{P}$.

(b) $\mathcal{K}_{SP} \leftrightarrow \mathcal{K}_{P}$ is unimodular.

If, $\mathcal{K}_{SP}^* + \mathcal{K}_{P}^*$ is unimodular, then

(c) $(\mathcal{K}_{SP} \leftrightarrow \mathcal{K}_{P})^* = \mathcal{K}_{SP}^* \leftrightarrow \mathcal{K}_{P}^*$.

(d) $\mathcal{K}_{SP}^* \leftrightarrow \mathcal{K}_{P}^*$ is unimodular.

*Answer*

*Proof.* (Proof of the Implicit Duality Theorem 88)

Let $\mathcal{K}_{SP}$ have the representative matrix $[A_S \quad A_P]$ and let $\mathcal{K}_{P}$ have the representative matrix $[\hat{A}_P]$. Then $\mathcal{K}_{SP} + \mathcal{K}_{P}$ has the representative matrix

$$ \begin{bmatrix} A_S & A_P \\ 0 & \hat{A}_P \end{bmatrix} $$

which is $g$-unimodular by hypothesis.

Now $x_S \in \mathcal{K}_{SP} \leftrightarrow \mathcal{K}_{P}$ iff $\exists \lambda_1, \lambda_2$ over $\mathbb{R}[\xi]$ s.t.

$$ \begin{bmatrix} A_S^T & 0 \\ A_P^T & \hat{A}_P^T \end{bmatrix} \begin{array}{l} \lambda_1 \\ \lambda_2 \end{array} = \begin{pmatrix} x_S \\ 0 \end{pmatrix} $$
i.e., iff (since column module of the above matrix is unimodular) whenever, for $y_S, y_P$ over $\mathbb{R}[\xi]$ we have

$$[\begin{matrix} y_S^T & y_P^T \end{matrix}] \begin{bmatrix} A_S^T & 0 \\ A_P^T & \hat{A}_P^T \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix}$$

we also have

$$y_S^T x_S = 0;$$

i.e., iff whenever $(y_S^T y_P^T) \in \mathcal{H}_{SP}^*$, $y_P^T \in \mathcal{H}_P^*$, we also have $y_S^T x_S = 0$;

i.e., iff whenever $y_S \in \mathcal{H}_{SP}^* \leftrightarrow \mathcal{H}_P^*$, we have $y_S^T x_S = 0$.

Thus, $x_S \in \mathcal{H}_{SP} \leftrightarrow \mathcal{H}_P$ iff $x_S \in (\mathcal{H}_{SP}^* \leftrightarrow \mathcal{H}_P^*)^*$.

This proves (a).

The statement in (b) follows from (a) and Lemma 86.

(c) Suppose $\mathcal{H}_{SP}^* + \mathcal{H}_P^*$ is unimodular. Since by Lemma 86 we already have $\mathcal{H}_{SP}^*, \mathcal{H}_P^*$ as unimodular, we can use (a) above and conclude that

$$(\mathcal{H}_{SP}^{**} \leftrightarrow \mathcal{H}_P^{**})^* = \mathcal{H}_{SP}^* \leftrightarrow \mathcal{H}_P^*$$

But $\mathcal{H}_{SP}, \mathcal{H}_P$ are unimodular and so by Lemma 86, $\mathcal{H}_{SP}^{**} = \mathcal{H}_{SP}$ and $\mathcal{H}_P^{**} = \mathcal{H}_P$

$$(\mathcal{H}_{SP} \leftrightarrow \mathcal{H}_P)^* = (\mathcal{H}_{SP}^* \leftrightarrow \mathcal{H}_P^*)$$

Statement (d) follows from (c) and Lemma 86.

□

**Problem 102.** Show that the adjoint of a behaviour is essentially unique in the following sense. Let a behavioural system be represented by $(R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$ or equivalently by $(PR_w|PR_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$, where $P$ is a unimodular matrix. Then $(\hat{w}^T|\hat{l}^T)$ is a member of the adjoint of the behaviour represented as originally, iff $(\hat{w}^T|\hat{l}^T P^{-1})$ is a member of the adjoint of the behaviour represented in the modified manner.

Answer

If $(R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$ is replaced by the equivalent $(PR_w|PR_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$, where $P$ is a unimodular matrix, then the adjoint is $\begin{pmatrix} I & -R_w^T P^T \\ 0 & -R_l^T P^T \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$. Thus $(\hat{w}^T|\hat{l}^T)$ is a member of the adjoint of the behaviour represented as originally, iff $(\hat{w}^T|\hat{l}^T P^{-1})$ is a member of the adjoint of the behaviour represented in the modified manner. We note that $P^{-1}$ has only real polynomials in $\xi$ as its entries.

**Problem 103.** Show that the adjoint of the adjoint of a behavioural system is simply related to the original: if $(w, l)$ is a typical member of the original system, then $(-w, w, l)$ is a typical member of the adjoint of the adjoint.

Answer

If $\mathcal{B}_{WL}$ has the kernel representation $(R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$, the adjoint $\mathcal{B}_{\hat{W}\hat{L}}^{adj}$ has the kernel representation $(\begin{matrix} I & -R_w^T \\ 0 & -R_l^T \end{matrix}) \begin{pmatrix} \hat{w} \\ \hat{l} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ and $(\mathcal{B}^{adj})_{\hat{W}\hat{L}}^{adj}$ has the kernel representation

$$\begin{pmatrix} I & I & 0 \\ 0 & R_w & R_l \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l} \end{pmatrix} = \begin{pmatrix} I & I & 0 \\ 0 & R_w & R_l \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l}_1 \\ \hat{l}_2 \end{pmatrix}.$$
We note that the constraints of the adjoint of the adjoint are equivalent to identifying the variables $\hat{w}, \hat{l}_1, \hat{l}_2$, respectively with $-w, w, l$ of the original behaviour.

**Problem 104.** For the behavioural system $\mathcal{B}$ defined by $\dot{x} = Ax + Bu, y = Cx$, show that $\mathcal{B}^{\text{adj}}$ is essentially the same as the conventional adjoint in the following sense. $(\hat{u}, \hat{y}, \hat{x})$ is a member of the conventional adjoint iff $((\hat{u}, \hat{u}, \hat{y}, \hat{x})$ is a member of $\mathcal{B}^{\text{adj}}$.

Answer

For the original system we take $w^T = (u^T \quad y^T)$, $x = l$. The constraints for the original system are

$$ \begin{pmatrix} -B & 0 & (\xi I - A) \\ 0 & I & -C \end{pmatrix} \begin{pmatrix} u \\ y \\ x \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}. \text{ The adjoint is } \begin{pmatrix} I & 0 & B^T & 0 \\ 0 & I & 0 & -I \\ 0 & 0 & -(\xi I - A)^T & C^T \end{pmatrix} \begin{pmatrix} \hat{w}_1 \\ \hat{w}_2 \\ \hat{l}_1 \\ \hat{l}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}. $$

The variables $\hat{w}_2, \hat{l}_2$ are seen to be identical using the second row. The constraints on $\hat{w}_1, \hat{w}_2, \hat{l}_1$ are

$$ \begin{pmatrix} I & 0 & B^T \\ 0 & C^T & -(\xi I - A)^T \end{pmatrix} \begin{pmatrix} \hat{w}_1 \\ \hat{w}_2 \\ \hat{l}_1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}. \text{ It can be seen that these are the constraints of the conventional adjoint, if we identify the variables } \hat{w}_1, \hat{w}_2, \hat{l}_1 \text{ with output, input and state variables of the conventional adjoint.} $$

**Problem 105.** Prove

$$ \begin{align*} \mathcal{B}_{WL} \text{ is controllable} &\equiv \mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \text{ is } \hat{l} \text{-observable} \\ \mathcal{B}_{WL} \text{ is } l\text{-observable} &\equiv \mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \text{ is controllable.} \end{align*} $$

Answer

If $\mathcal{B}_{WL}$ has the kernel representation $(R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$, the adjoint $\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}$ has the kernel representation

$$ \begin{pmatrix} I & -R_w^T \\ 0 & -R_l^T \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \text{ The required results are immediate from the following facts;} $$

(i) $(R_w \quad R_l)$ is row unimodular iff $\begin{pmatrix} -R_w^T \\ -R_l^T \end{pmatrix}$ is column unimodular;

(ii) $R_l$ is column unimodular iff $\begin{pmatrix} I & -R_w^T \\ 0 & -R_l^T \end{pmatrix}$ is row unimodular.

**Problem 106.** Prove the following result for the duality of modules of adjoint behaviours through the use of Implicit Duality Theorem.

**Theorem 89.** If behaviour $\mathcal{B}_{WL}$ is controllable

$$ (\mathcal{C}(\mathcal{B}_{WL} \circ W))_{\hat{W}} = (\mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \circ \hat{W}))^*. $$

If $\mathcal{B}_{WL}$ is $l$-observable then

$$ (\mathcal{C}(\mathcal{B}_{WL} \circ W))_{\hat{W}}^* = \mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \circ \hat{W}). $$

Answer

*Proof.* Let $\mathcal{B}_{WL}$ be defined by the constraints $(R_w \quad R_l) \begin{pmatrix} w \\ l \end{pmatrix} = 0$.

Then $\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}$ is defined by the constraints $\begin{pmatrix} I & -R_w^T \\ 0 & -R_l^T \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l} \end{pmatrix} = 0$.
In terms of the variables $w, l$ the constraints of $\mathcal{B}_{WL}$ are equivalent to

$$ (R_w \quad 0 \quad I) \begin{pmatrix} w \\ l \\ l' \end{pmatrix} = (0), (-R_l \quad I) \begin{pmatrix} l \\ l' \\ l \end{pmatrix} = (0). $$

In terms of the variables $\hat{w}, \hat{l}$ the constraints of $\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}$ are equivalent to

$$ \begin{pmatrix} I & 0 & -R_w^T \\ 0 & I & 0 \\ 0 & 0 & I \end{pmatrix} \begin{pmatrix} \hat{w} \\ \hat{l} \\ \hat{l} \end{pmatrix} = (0), (I \quad R_l^T) \begin{pmatrix} \hat{l} \\ \hat{l} \\ I \end{pmatrix} = (0). $$

Let $\mathcal{K}_{WL}, \mathcal{K}_{WLL'}, \mathcal{K}_{LL'}, \mathcal{K}_{\hat{W}\hat{L}}$ be the modules spanned by the rows respectively of

$$ (R_w \quad R_l), (R_w \quad 0 \quad I), (-R_l \quad I), \begin{pmatrix} I & -R_w^T \\ 0 & -R_l^T \end{pmatrix}. $$

Then $\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* := (\mathcal{K}_{WLL'}^*)_{\hat{W}\hat{L}'\hat{L}}, \mathcal{K}_{\hat{L}'\hat{L}}^* := (\mathcal{K}_{LL'}^*)_{\hat{L}'\hat{L}}$, are the modules spanned by the rows respectively of

$$ \begin{pmatrix} I & 0 & -R_w^T \\ 0 & I & 0 \end{pmatrix}, (I \quad R_l^T). $$

It is clear that

* $\mathcal{K}_{WLL'} + \mathcal{K}_{LL'}$ is the module spanned by the rows of $\begin{pmatrix} R_w & 0 & I \\ 0 & -R_l & I \end{pmatrix}$, i.e., by the rows of $\begin{pmatrix} R_w & R_l & 0 \\ 0 & -R_l & I \end{pmatrix}$, so that $\mathcal{K}_{WLL'} + \mathcal{K}_{LL'}$ is unimodular if $(R_w \quad R_l)$ is row unimodular, i.e., if $\mathcal{B}_{WL}$ is controllable;

* $\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* + \mathcal{K}_{\hat{L}'\hat{L}}^*$ is the module spanned by the rows of $\begin{pmatrix} I & 0 & -R_w^T \\ 0 & I & 0 \\ 0 & I & R_l^T \end{pmatrix}$, i.e., by the rows of $\begin{pmatrix} I & 0 & -R_w^T \\ 0 & 0 & -R_l^T \\ 0 & I & 0 \end{pmatrix}$, so that $\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* + \mathcal{K}_{\hat{L}'\hat{L}}^*$ is unimodular if $(R_l^T)$ is row unimodular, i.e., if $\mathcal{B}_{WL}$ is $l$-observable;

* $\mathcal{K}_{WLL'} \leftrightarrow \mathcal{K}_{LL'} = \mathcal{K}_{WL} \times W$.

* $\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* \leftrightarrow \mathcal{K}_{\hat{L}'\hat{L}}^* = \mathcal{K}_{\hat{W}\hat{L}} \times \hat{W}$.

Now $\mathcal{C}(\mathcal{B}_{WL}) = \mathcal{K}_{WL}, \mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}) = \mathcal{K}_{\hat{W}\hat{L}}$ and we know that $\mathcal{C}(\mathcal{B}_{WL} \circ W) = \mathcal{K}_{WL} \times W, \mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \circ \hat{W}) = \mathcal{K}_{\hat{W}\hat{L}} \times \hat{W}$.

Next, $\mathcal{K}_{WL}, \mathcal{K}_{WLL'} + \mathcal{K}_{LL'}$ are unimodular if $\mathcal{B}_{WL}$ is controllable, i.e., if $(R_w \quad R_l)$ is row unimodular and $\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}, \mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* + \mathcal{K}_{\hat{L}'\hat{L}}^*$ are unimodular if $\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}$ is $\hat{l}$-observable.

From part (a) of Theorem 88, we have when $\mathcal{B}_{WL}$ is controllable, that $(\mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \circ \hat{W}))^* = (\mathcal{K}_{\hat{W}\hat{L}}^* \times \hat{W})^* = (\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* \leftrightarrow \mathcal{K}_{\hat{L}'\hat{L}}^*)_{\hat{W}}^* = (\mathcal{K}_{WLL'} \leftrightarrow \mathcal{K}_{LL'})_{\hat{W}} = (\mathcal{K}_{WL} \times W)_{\hat{W}} = (\mathcal{C}(\mathcal{B}_{WL} \circ W))_{\hat{W}}$.

From part (c) of Theorem 88, we have when $\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}}$ is $\hat{l}$-observable, that $(\mathcal{C}(\mathcal{B}_{WL} \circ W))^* = (\mathcal{K}_{WL} \times W)^* = (\mathcal{K}_{WLL'} \leftrightarrow \mathcal{K}_{LL'})^* = (\mathcal{K}_{\hat{W}\hat{L}'\hat{L}}^* \leftrightarrow \mathcal{K}_{\hat{L}'\hat{L}}^*)_{\hat{W}} = (\mathcal{K}_{\hat{W}\hat{L}} \times \hat{W})_{\hat{W}} = (\mathcal{C}(\mathcal{B}_{\hat{W}\hat{L}}^{\text{adj}} \circ \hat{W}))_{\hat{W}}$. $\square$

## 20. General framework for implicit duality

We summarize the relevant definitions from [19] for the convenience of the reader.

Let $G^1, G^2, G^3$ be abelian groups and let $\mathcal{V}_Z^1, \mathcal{V}_Z^2$, be chain groups over $G^1, G^2$, respectively (collections of vectors on $Z$ with entries from $G^1, G^2$, respectively, closed under subtraction). Let $\mathcal{J}_Z \subseteq \mathcal{V}_Z^1, \mathcal{K}_Z \subseteq \mathcal{V}_Z^2$, be closed under addition with the zero vector present in them. Let $H \subseteq G^3$ be closed under addition with $0 \in H$.

**Definition 90.** Let $\hat{f} : G^1 \times G^2 \to G^3$, be such that
$$ \hat{f}(a_1, b_2 + 2c_2) = \hat{f}(a_1, b_2) + 3 \hat{f}(a_1, c_2) \text{ and } \hat{f}(a_1 + 1, b_1, c_2) = \hat{f}(a_1, c_2) + 3 \hat{f}(b_1, c_2), a_1, b_1 \in G^1, b_2, c_2 \in G^2 $$
where $+_i, i = 1, 2, 3$, denote respectively the addition operations of $G^1, G^2, G^3$. (It follows that $\hat{f}(a_1, 0) =$

<footnote>* (This section is based on the section with the same title in [19].)</footnote>
$\hat{f}(0, b_2) = 0, a_1 \in G^1, b_2 \in G^2$ and $\hat{f}(-a, b) = \hat{f}(a, -b) = -\hat{f}(a, b).$

Let $f: \mathcal{V}_Z^1 \times \mathcal{V}_Z^2 \to G^3$ be defined by $f(x, y) = \sum_{e \in Z} \hat{f}(x_e, y_e)$, $x \in \mathcal{V}_Z^1, y \in \mathcal{V}_Z^2$, where $\Sigma$ denotes the addition operation of $G^3$. We will use $\langle x, y \rangle$ in place of $f(x, y)$ and call it a $q$-dot product of $x, y$. We say $\mathcal{J}, \mathcal{K}$ are $q$-orthogonal (quasi orthogonal) iff $\langle x, y \rangle \in H$, whenever $x \in \mathcal{J}_Z, y \in \mathcal{K}_Z$. For $\mathcal{J}_Z \subseteq \mathcal{V}_Z^1, \mathcal{K}_Z \subseteq \mathcal{V}_Z^2$, we define $\mathcal{J}_Z^* := \{y, \langle x, y \rangle \in H, x \in \mathcal{J}_Z\}, \mathcal{K}_Z^* := \{x, \langle x, y \rangle \in H, y \in \mathcal{K}_Z\}$. We say $\mathcal{J}_Z, \mathcal{K}_Z$ are closed under $q$-orthogonality iff $(\mathcal{J}_Z^*)^* = \mathcal{J}_Z$ and $(\mathcal{K}_Z^*)^* = \mathcal{K}_Z$.

**Definition 91.** Let $\mathcal{V}_Z^1, \mathcal{V}_Z^2$, be chain groups over abelian groups $G^1, G^2$, respectively. We say a family $\mathcal{S}^1$ ($\mathcal{S}^2$) of collections of vectors $\mathcal{J}_Y \subseteq \mathcal{V}_Z^1 \circ Y$ ($\mathcal{K}_Y \subseteq \mathcal{V}_Z^2 \circ Y$) on $Y \subseteq Z$ over $G^1$ ($G^2$) is regular relative to $\mathcal{V}_Z^1$ ($\mathcal{V}_Z^2$), respectively iff

* each $\mathcal{J}_Y$ ($\mathcal{K}_Y$) is closed under addition and contains the zero vector;

* each $\mathcal{J}_Y$ ($\mathcal{K}_Y$) is closed under $q$-orthogonality;

* whenever $\mathcal{J}_Y$ ($\mathcal{K}_Y$) is in $\mathcal{S}^1$ ($\mathcal{S}^2$), so are its restriction and contraction to $T \subseteq Y$;

* whenever $\mathcal{J}'_Y, \mathcal{J}''_Y$ ($\mathcal{K}'_Y, \mathcal{K}''_Y$) are in $\mathcal{S}^1$ ($\mathcal{S}^2$), so are $\mathcal{J}'_Y + \mathcal{J}''_Y, \mathcal{J}'_Y \cap \mathcal{J}''_Y$ ($\mathcal{K}'_Y + \mathcal{K}''_Y, \mathcal{K}'_Y \cap \mathcal{K}''_Y$).

We say $(\mathcal{S}^1, \mathcal{S}^2)$ is a regular pair of families relative to $(\mathcal{V}_Z^1, \mathcal{V}_Z^2)$, iff $\mathcal{S}^1$ ($\mathcal{S}^2$) is regular relative to $\mathcal{V}_Z^1$ ($\mathcal{V}_Z^2$), and whenever $\mathcal{J}_Y \in \mathcal{S}^1$ ($\mathcal{K}_Y \in \mathcal{S}^2$), we have $\mathcal{J}_Y^* \in \mathcal{S}^2$ ($\mathcal{K}_Y^* \in \mathcal{S}^1$).

**Problem 107.** Prove the following implicit duality theorem in the above general framework.

**Theorem 92.** Let $(\mathcal{S}^1, \mathcal{S}^2)$ be regular relative to $(\mathcal{V}_Z^1, \mathcal{V}_Z^2)$. Let $\mathcal{J}_{SP}, \mathcal{J}_{PQ}$ ($\mathcal{K}_{SP}, \mathcal{K}_{PQ}$) be members of $\mathcal{S}^1$ ($\mathcal{S}^2$). We define $\mathcal{J}_{SP} \leftrightarrow \mathcal{J}_{PQ} \equiv (\mathcal{J}_{SP} \cap \mathcal{J}_{PQ}) \circ \text{SQ} = (\mathcal{J}_{SP} + (\mathcal{J}_{PQ})(-P)Q) \times \text{SQ}$, $\mathcal{J}_{SP} \rightleftharpoons \mathcal{J}_{PQ} \equiv \mathcal{J}_{SP} \leftrightarrow (\mathcal{J}_{PQ})(-P)Q$. We then have the following.

1. $\mathcal{J}_Y \to (\mathcal{J}_Y)^*$ is a bijection between $\mathcal{S}^1, \mathcal{S}^2$ ($\mathcal{K}_Y \to (\mathcal{K}_Y)^*$ is the inverse bijection between $\mathcal{S}^2, \mathcal{S}^1$).

2. Let $\mathcal{J}_{SP}, \mathcal{J}_{PQ}$ ($\mathcal{K}_{SP}, \mathcal{K}_{PQ}$) be members of $\mathcal{S}^1$ ($\mathcal{S}^2$). We then have $(\mathcal{J}_{SP} \leftrightarrow \mathcal{J}_{PQ})^* = (\mathcal{J}_{SP}^* \rightleftharpoons \mathcal{J}_{PQ}^*)$ ($\mathcal{K}_{SP} \leftrightarrow \mathcal{K}_{PQ}^*)^* = (\mathcal{K}_{SP}^* \rightleftharpoons \mathcal{K}_{PQ}^*)$).

Answer

We need the following couple of lemmas for the proof of Theorem 92.

**Lemma 93.** Let $\mathcal{J}_Z^1, \mathcal{J}_Z^2 \subseteq \mathcal{V}_Z^1, \mathcal{K}_Z^1, \mathcal{K}_Z^2 \subseteq \mathcal{V}_Z^2$. We have the following.

1. $((\mathcal{J}_Z^1)^*)^* \supseteq \mathcal{J}_1, ((\mathcal{K}_Z^1)^*)^* \supseteq (\mathcal{K}_Z^1)$.

2. If $\mathcal{J}_Z^1 \supseteq \mathcal{J}_Z^2$ then $(\mathcal{J}_Z^1)^* \subseteq (\mathcal{J}_Z^2)^*$; $\mathcal{K}_Z^1 \supseteq \mathcal{K}_Z^2$ then $(\mathcal{K}_Z^1)^* \subseteq (\mathcal{K}_Z^2)^*$.

3. $(\mathcal{J}_Z^1)^*, (\mathcal{K}_Z^1)^*$ are closed under $q$-orthogonality.

4. If $\mathcal{J}_Z^1, \mathcal{J}_Z^2, \mathcal{K}_Z^1, \mathcal{K}_Z^2$, are closed under $q$-orthogonality, then $\mathcal{J}_Z^1 \cap \mathcal{J}_Z^2, \mathcal{K}_Z^1 \cap \mathcal{K}_Z^2$ are closed under $q$-orthogonality.

*Proof.* We will only prove the results for subsets of $\mathcal{V}_Z^1$.

1. Let $x \in \mathcal{J}_Z^1$ and $y \in (\mathcal{J}_Z^1)^*$. We then have $\langle x, y \rangle \in H$. By the definition of $((\mathcal{J}_Z^1)^*)^*$, it follows that $x \in ((\mathcal{J}_Z^1)^*)^*$.

2. Let $y \in (\mathcal{J}_Z^1)^*, x \in \mathcal{J}_Z^2 \subseteq \mathcal{J}_Z^1$. It is clear that $\langle x, y \rangle \in H$, so that $y \in (\mathcal{J}_Z^2)^*$.

3. We need to show that $(( (\mathcal{J}_Z^1)^*)^* )^* \subseteq (\mathcal{J}_Z^1)^*$, by part 1 above. Let $y \in (((\mathcal{J}_Z^1)^*)^*)^*$. If $x \in \mathcal{J}_Z^1 \subseteq ((\mathcal{J}_Z^1)^*)^*$ then $\langle x, y \rangle \in H$. Therefore $y \in (\mathcal{J}_Z^1)^*$.

4. By part 2 above, $(\mathcal{J}_Z^1 \cap \mathcal{J}_Z^2)^* \supseteq (\mathcal{J}_Z^1)^* \cap (\mathcal{J}_Z^2)^*$. Therefore $((\mathcal{J}_Z^1 \cap \mathcal{J}_Z^2)^*)^* \subseteq ((\mathcal{J}_Z^1)^* \cap (\mathcal{J}_Z^2)^*)^* \subseteq ((\mathcal{J}_Z^1)^* \times ((\mathcal{J}_Z^2)^*)^*)^* = \mathcal{J}_Z^1 \cap \mathcal{J}_Z^2$. By part 1 above, this means $((\mathcal{J}_Z^1 \cap \mathcal{J}_Z^2)^*)^* = \mathcal{J}_Z^1 \cap \mathcal{J}_Z^2$. $\square$
**Lemma 94.** Let $\mathcal{J}_1, \mathcal{J}_2 \subseteq \mathcal{V}_Z^1, \mathcal{J}_Y \subseteq \mathcal{V}_Z^1 \circ Y, Y \subseteq Z, \mathcal{K}_1, \mathcal{K}_2 \subseteq \mathcal{V}_Z^2, \mathcal{K}_Y \subseteq \mathcal{V}^2 \circ Y, Y \subseteq Z$, be closed under addition with the zero vector present in them. We have the following.

$$1. (\mathcal{J}_1 + \mathcal{J}_2)^* = \mathcal{J}_1^* \cap \mathcal{J}_2^*; (\mathcal{K}_1 + \mathcal{K}_2)^* = \mathcal{K}_1^* \cap \mathcal{K}_2^*.$$

2. If $\mathcal{J}_1, \mathcal{J}_2, \mathcal{J}_1^*, \mathcal{J}_2^*, \mathcal{K}_1, \mathcal{K}_2, \mathcal{K}_1^*, \mathcal{K}_2^*$ are closed under q-orthogonality, then $(\mathcal{J}_1 \cap \mathcal{J}_2)^* = \mathcal{J}_1^* + \mathcal{J}_2^*; (\mathcal{K}_1 \cap \mathcal{K}_2)^* = \mathcal{K}_1^* + \mathcal{K}_2^*$.

3. $(\mathcal{J}_Y \circ T)^* = \mathcal{J}_Y^* \times T, T \subseteq Y$. $(\mathcal{K}_Y \circ T)^* = \mathcal{K}_Y^* \times T, T \subseteq Y$.

4. If $\mathcal{J}_Y, \mathcal{J}_Y \circ T, T \subseteq Y$ are closed under q-orthogonality, then $(\mathcal{J}_Y^* \times T)^* = \mathcal{J}_Y \circ T$. If $\mathcal{K}_Y, \mathcal{K}_Y \circ T, T \subseteq Y$ are closed under q-orthogonality, then $(\mathcal{K}_Y^* \times T)^* = \mathcal{K}_Y \circ T$.

*Proof.* We will prove the results only for subsets of $\mathcal{V}_Z^1, \mathcal{V}_Z^1 \circ Y$.

1. Let $y \in (\mathcal{J}_1 + \mathcal{J}_2)^*$. Since the zero vector belongs to both $\mathcal{J}_1$ as well as $\mathcal{J}_2$, it is clear that $\mathcal{J}_1 + \mathcal{J}_2 \supseteq \mathcal{J}_1 \cup \mathcal{J}_2$. Therefore $y \in \mathcal{J}_1^*$ and $y \in \mathcal{J}_2^*$. Therefore $y \in \mathcal{J}_1^* \cap \mathcal{J}_2^*$. Next, let $y \in \mathcal{J}_1^* \cap \mathcal{J}_2^*$. Then $y \in \mathcal{J}_1^*$ and $y \in \mathcal{J}_2^*$. If $x_1 \in \mathcal{J}_1$ and $x_2 \in \mathcal{J}_2$, then $\langle x_1 + x_2, y \rangle = \langle x_1, y \rangle + \langle x_2, y \rangle \in H$, since $H$ is closed under addition. It follows that $y \in (\mathcal{J}_1 + \mathcal{J}_2)^*$.

2. By part 4 of Lemma 93, we have that $\mathcal{J}_1 \cap \mathcal{J}_2$ is closed under q-orthogonality. By the previous part of the present lemma, and part 3 of Lemma 93, we have $(\mathcal{J}_1^* + \mathcal{J}_2^*)^* = (\mathcal{J}_1^*)^* \cap (\mathcal{J}_2^*)^* = \mathcal{J}_1 \cap \mathcal{J}_2$. Now $(\mathcal{J}_1 \cap \mathcal{J}_2)^* = ((\mathcal{J}_1^* + \mathcal{J}_2^*)^*)^* = \mathcal{J}_1^* + \mathcal{J}_2^*$, since $\mathcal{J}_1^* + \mathcal{J}_2^*$ is given to be closed under q-orthogonality.

3. If $x_T \in \mathcal{J}_Y \circ T$, then there exists $x_{(Y-T)}$ such that $(x_T, x_{(Y-T)}) \in \mathcal{J}_Y$. Now if $y_T \in \mathcal{J}_Y^* \times T$, then $(y_T, 0_{(Y-T)}) \in \mathcal{J}_Y^*$. Therefore $\langle (x_T, x_{(Y-T)}), (y_T, 0_{(Y-T)}) \rangle = \langle x_T, y_T \rangle + \langle x_{(Y-T)}, 0_{(Y-T)} \rangle = \langle x_T, y_T \rangle \in H$. Thus $(\mathcal{J}_Y \circ T)^* \supseteq \mathcal{J}_Y^* \times T$.

On the other hand if $y_T \in (\mathcal{J}_Y \circ T)^*$, it is clear that $(y_T, 0_{(Y-T)}) \in \mathcal{J}_Y^*$. Therefore $y_T \in \mathcal{J}_Y^* \times T$. Thus $(\mathcal{J}_Y \circ T)^* \subseteq \mathcal{J}_Y^* \times T$.

4. We have, $\mathcal{J}_Y \circ T = ((\mathcal{J}_Y \circ T)^*)^* = (\mathcal{J}_Y^* \times T)^*$, using part 3 above. $\square$

<figure><img src="image_15.png" /></figure>

*Proof.* (of Theorem 92) 1. This is immediate from the fact that members of $(\mathcal{S}^1, \mathcal{S}^2)$ are closed under q-orthogonality.

2. We will prove the result only for members of $\mathcal{S}^1$.

$$ \begin{aligned} & \text{We have } (\mathcal{J}_{SP} \leftrightarrow \mathcal{J}_{PQ})^* = ((\mathcal{J}_{SP} \cap \mathcal{J}_{PQ}) \circ SQ)^* \\ & = ((\mathcal{J}_{SP} \cap \mathcal{J}_{PQ})^* \times SQ) = ((\mathcal{J}_{SP}^* + \mathcal{J}_{PQ}^*) \times SQ \text{ using part 2, part 3 of Lemma 94}) \\ & = \mathcal{J}_{SP}^* \leftrightarrow (\mathcal{J}_{PQ}^*)(-P)Q = (\mathcal{J}_{SP}^* \rightleftharpoons \mathcal{J}_{PQ}^*). \end{aligned} \square $$

<figure><img src="image_16.png" /></figure>

**21. Implicit duality theorem for matroids**

We assume familiarity with the notions of independent set, base, restriction $(\mathcal{M} \circ T)$, contraction $(\mathcal{M} \times T)$, dual $(\mathcal{M}^*)$ of a matroid $\mathcal{M}$. Let $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$, be matroids defined on $S \uplus P, P \uplus Q$, respectively, where $S, P, Q$, are pairwise disjoint. We define $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$, to be the matroid whose bases are maximal unions of bases of $\mathcal{M}_{SP}, \mathcal{M}_{PQ}$ and $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$, to be the matroid whose bases are minimal intersections of sets of the form $(b_{SP} \uplus Q) \cap (b_{PQ} \uplus S)$, where $b_{SP}, b_{PQ}$ are bases of $\mathcal{M}_{SP}, \mathcal{M}_{PQ}$, respectively. It can be seen that $(\mathcal{M}_{SP} \vee \mathcal{M}_{PQ})^* = \mathcal{M}_{SP}^* \wedge \mathcal{M}_{PQ}^*$. We define $\mathcal{M}_{SP} \leftrightarrow \mathcal{M}_{PQ} :\equiv (\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}) \times (S \uplus Q)$.

**Problem 108.** Prove the following analogue of the vector space result $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} = (\mathcal{V}_{SP} \cap \mathcal{V}_{PQ}) \circ SQ = (\mathcal{V}_{SP} + (\mathcal{V}_{PQ})(-P)Q) \times SQ$.

**Theorem 95.** Let $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$, be matroids respectively on $S \uplus P, P \uplus Q$, respectively, where $(\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}) \times (S \cup Q) = (\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}) \cdot (S \cup Q)$

Answer

The proof given below is from [21].

<footnote>\*(This section is based on the section with the same title in [19].)</footnote>
Proof. Let $b_S \cup b_Q$ be a base of LHS. Then there exist bases $b_S \cup b_P^1$ and $b_P^2 \cup b_Q$ of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$ respectively such that $b_P^1 \cap b_P^2$ is minimal and among all such pairs of bases of $\mathcal{M}_{SP}, \mathcal{M}_{PQ}$, $b_S \cup b_Q$ is minimal. We will show that the same bases can be used to derive a base of RHS. Firstly we need to show that $b_S \cup b_Q \cup (b_P^1 \cap b_P^2)$ is a base of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$, i.e., we should show that it is a minimal intersection of bases of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$ (recall that while taking wedge-intersection, we pad the bases with entire sets on which the original matroids are not defined i.e., we are looking at intersection of $b_S \cup b_P^1 \cup Q$ and $S \cup b_P^2 \cup b_Q$). Suppose the set $b_S \cup b_Q \cup (b_P^1 \cap b_P^2)$ is not minimal. Then we should be able to remove elements from it retaining the property that it is an intersection of bases of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$. We already know that $b_P^1 \cap b_P^2$ is minimal among all such pairs of bases, so we cannot remove any element from it. Next, among all such pairs of bases of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$, where $b_P^1 \cap b_P^2$ is minimal, we know that $b_S \cup b_Q$ is minimal. So we cannot remove any element from $b_S$ or $b_Q$ either. Hence $b_S \cup b_Q \cup (b_P^1 \cap b_P^2)$ is a base of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$.

Suppose $b_S \cup b_Q$ is not a maximal intersection with $S \cup Q$, among all bases of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$. Then there exist bases $\hat{b}_S \cup \hat{b}_P^1$ and $\hat{b}_P^2 \cup \hat{b}_Q$ of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$ respectively such that $\hat{b}_S \cup \hat{b}_Q \cup (\hat{b}_P^1 \cap \hat{b}_P^2)$ is a base of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$ and $\hat{b}_S \cup \hat{b}_Q \supset b_S \cup b_Q$. But this implies $|\hat{b}_P^1 \cap \hat{b}_P^2| < |b_P^1 \cap b_P^2|$, a contradiction. Hence $b_S \cup b_Q$ is a base of RHS too.

Next, let $b_S \cup b_Q$ be a base of RHS. Then there exist bases $b_S \cup b_P^1$ and $b_P^2 \cup b_Q$ of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$ respectively such that $b_S \cup b_Q \cup (b_P^1 \cap b_P^2)$ is a base of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$ and further (since $b_S \cup b_Q$ is a maximal intersection with $S \cup Q$ among bases of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$), for all such pairs of bases, $b_P^1 \cap b_P^2$ is minimal. Hence $b_S \cup b_Q \cup b_P^1 \cup b_P^2$ is a base of $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$. Further, for the given intersection $b_P^1 \cap b_P^2$, the set $b_S \cup b_Q$ is a minimal intersection with $S \cup Q$ among bases of $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$. This is because $b_S \cup b_Q \cup (b_P^1 \cap b_P^2)$, being a base of $\mathcal{M}_{SP} \wedge \mathcal{M}_{PQ}$, is minimal among all pairs of bases $b_S \cup b_P^1$ and $b_P^2 \cup b_Q$ of $\mathcal{M}_{SP}$ and $\mathcal{M}_{PQ}$ respectively). But this means $b_S \cup b_Q$ is a minimal intersection of a base of $\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}$ with $S \cup Q$, i.e., is a base of LHS.

□

**Problem 109.** Prove the following ‘implicit duality theorem’ for matroids.

**Theorem 96.** (Implicit Duality Theorem for matroids) Let $\mathcal{M}_{SP} \leftrightarrow \mathcal{M}_{PQ} : \equiv (\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}) \times (S \uplus Q)$. We then have

$$ (\mathcal{M}_{SP} \leftrightarrow \mathcal{M}_{PQ})^* = \mathcal{M}_{SP}^* \leftrightarrow \mathcal{M}_{PQ}^* \qquad (90) $$

Answer

The proof given below is from [21].

Proof.

$$ \begin{align*} (\mathcal{M}_{SP} \leftrightarrow \mathcal{M}_{PQ})^* &= [(\mathcal{M}_{SP} \vee \mathcal{M}_{PQ}) \times (S \cup Q)]^* \\ &= (\mathcal{M}_{SP} \vee \mathcal{M}_{PQ})^* \cdot (S \cup Q) \\ &= (\mathcal{M}_{SP}^* \wedge \mathcal{M}_{PQ}^*) \cdot (S \cup Q) \\ &= (\mathcal{M}_{SP}^* \vee \mathcal{M}_{PQ}^*) \times (S \cup Q) \quad \text{(using Theorem 95).} \\ &= \mathcal{M}_{SP}^* \leftrightarrow \mathcal{M}_{PQ}^* \end{align*} $$

□

References

[1] G. Basile, G. Marro, Controlled and Conditioned Invariants in Linear System Theory, Prentice-Hall, Englewood Cliffs, NJ, 1992.

[2] G. D. Forney, M. D. Trott, The Dynamics of Group Codes: Dual Abelian Group Codes and Systems, IEEE Transactions on Information Theory 50 (11) (2004) 1–30.

[3] R.E.Kalman, Mathematical description of linear dynamical systems, SIAM J. Control 1 (1963) 152–192.
[4] L. W. Nagel, D. O. Pederson, SPICE (Simulation Program with Integrated Circuit Emphasis) (Technical report). University of California, Berkeley. UCB/ERL M382 (April 1973).

[5] H. Narayanan, On the decomposition of vector spaces, Linear Algebra and its Applications 76 (1986) 61–98.

[6] H. Narayanan, A Unified Construction of Adjoint Systems and Networks, Circuit Theory and Applications 14 (1986) 263–276.

[7] H. Narayanan, Topological transformations of electrical networks, International Journal of Circuit Theory and Applications 15 (3) (1987) 211–233.

[8] H. Narayanan, Submodular Functions and Electrical Networks, Annals of Discrete Mathematics, vol. 54, North Holland, Amsterdam, 1997. Open 2nd edition, 2009. URL https://www.ee.iitb.ac.in/~hn/.

[9] H. Narayanan, On the Duality between Controllability and Observability in Behavioural Systems Theory, Proc. International Conference on Communications Control and Signal Processing, CCSP 2000, Bangalore, July 25-July 28,2000, 183–186.

[10] H. Narayanan, Matroids representable over Modules, Electrical Network Topology and Behavioural Systems Theory, Research report of the EE Dept., IIT Bombay, May 2000. URL https://www.ee.iitb.ac.in/~hn/otherpapers.htm.

[11] H. Narayanan, Some applications of an implicit duality theorem to connections of structures of special types including dirac and reciprocal structures, Systems & Control Letters 45 (2) (2002) 87 – 95.

[12] H. Narayanan, H. Priyadarshan, A subspace approach to linear dynamical systems, Linear Algebra and its Applications 438 (2013) 3576–3599.

[13] H. Narayanan & Hariharan Narayanan, On Thevenin - Norton and Maximum power transfer theorems, arXiv:2104.05202v1 [math.GM] (2021).

[14] H. Narayanan, Implicit Linear Algebra and its Applications, arXiv:1609.07991v1 [math.GM] (2016).

[15] H. Narayanan, Hariharan Narayanan, On the linear static output feedback problem: the annihilating polynomial approach, Linear Algebra and its Applications 579, (2019) 336–364.

[16] H. Narayanan, Hariharan Narayanan, On the linking of number lattices, arXiv:1907.08675 [math.NT] (2019).

[17] H. Narayanan, Hariharan Narayanan, On complete versions of Thevenin-Norton and maximum power transfer theorems, Circuits, Systems, and Signal Processing, 41, (2022) 597–608.

[18] H. Narayanan, 'On composition and decomposition operations for vector spaces, graphs and matroids' arXiv:2305.16354 [math.GM] (2023).

[19] H. Narayanan, Applications of the implicit inversion and implicit duality theorems, Chapter 1 of present monograph (2024).

[20] J. W. Polderman, J. C. Willems, Introduction to Mathematical Systems Theory: a Behavioural Approach, Springer-Verlag, 1997.

[21] Siva Theja, H. Narayanan, On the notion of generalized minor in topological network theory and matroids, Linear Algebra and its Applications 458 (2014) 1–46.

[22] W. M. Wonham, On pole assignment in multi-input controllable systems, IEEE Trans. Automat. Control AC-12 (1967) 660–665.

[23] W. M. Wonham, Linear Systems Theory: A Geometric Approach, Springer-Verlag, New York, USA, 1978.