# Problems on 'Applications of the Implicit Inversion and Implicit Duality theorems'

Narayanan Harihar

► To cite this version:

Narayanan Harihar. Problems on 'Applications of the Implicit Inversion and Implicit Duality theo-
rems'. 2025. hal-04895390

HAL Id: hal-04895390

https://hal.science/hal-04895390v1

Preprint submitted on 18 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Problems on 'Applications of the Implicit Inversion and Implicit Duality theorems'

H. Narayanan*

Department of Electrical Engineering, Indian Institute of Technology Bombay

**Abstract**

This paper is intended to be the second chapter of a monograph entitled 'implicit linear algebra and its Applications' and is meant to complement the first chapter entitled 'Applications of the Implicit Inversion and Implicit Duality theorems'. This chapter is largely self contained except that it needs the preliminaries section of the first chapter. For better readability we have repeated some definitions at appropriate places.

**Keywords:** Linear Dynamical Systems, State Space Theory, Behavioural Systems Theory, Controlled and Conditioned Invariant Spaces, Duality in Adjoint System, Implicit Linear Algebra, Implicit Duality Theorem

2000 MSC: 15A03, 15A04, 15A18

## 1. Introduction

## 2. Preliminary definitions and results

*(This is an abridged version of the 'Preliminaries' section of [19].)

We give below a brief description of the notation of implicit linear algebra. In our approach, we avoid the use of explicit maps and work rather with vector spaces and the operations sum, intersection, restriction, contraction and the operation $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P$, of generalized minor. A **vector** $f_S$ is a function $f_S : S \to \mathbb{R}$. A **zero-member collection** $\mathcal{K}_S$ is a collection of vectors $f_S : S \to \mathbb{R}$, with the zero vector $0_S$ as a member. The sets on which vectors are defined, are referred to as **index** sets and unless otherwise mentioned, are to be taken as **finite**. We write $S \uplus P$ for $S \cup P$, when $S, P$, are disjoint. For better readability, we write $A - B$ for the **set difference** $A \setminus B$. A vector $f_{SP}$ on $S \uplus P$ is usually written as $(f_S, f_P)$. A **vector space** $\mathcal{V}_S$ is a collection of vectors $f_S : S \to \mathbb{R}$, closed under addition and scalar multiplication, $\mathcal{V}_{SP} := \mathcal{V}_{S \uplus P}$, **sum** $\mathcal{V}_A + \mathcal{V}_B := \{(f_{A-B}, f_{A\cap B} + g_{A\cap B}, g_{B-A}) : (f_{A-B}, f_{A\cap B}) \in \mathcal{V}_A, (g_{A\cap B}, g_{B-A}) \in \mathcal{V}_B\}$, **intersection** $\mathcal{V}_A \cap \mathcal{V}_B := \{(f_{A-B}, h_{A\cap B}, g_{B-A}) : (f_{A-B}, h_{A\cap B}) \in \mathcal{V}_A, (h_{A\cap B}, g_{B-A}) \in \mathcal{V}_B\}$, **restriction** $\mathcal{V}_{SP} \circ S := \{f_S : (f_S, f_P) \in \mathcal{V}_{SP}\}$, **contraction** $\mathcal{V}_{SP} \times S := \{f_S : (f_S, 0_P) \in \mathcal{V}_{SP}\}$, **generalized minor** $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P := \{f_S : (f_S, f_P) \in \mathcal{V}_{SP}, f_P \in \mathcal{V}_P\}$, **matched composition** $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} := \{f : f = (g|_S, h|_Q)\}$, where $g \in \mathcal{V}_{SP}, h \in \mathcal{V}_{PQ} \& g|_P = h|_P$}, **skewed composition** $\mathcal{V}_{SP} \rightleftharpoons \mathcal{V}_{PQ} := \{f : f = (g|_S, h|_Q)\}$, where $g \in \mathcal{V}_{SP}, h \in \mathcal{V}_{PQ} \& g|_P = -h|_P$}. Spaces obtained by restriction followed by contraction or the other way about, are called **minors**. (Note that the sum and intersection operations are mild generalizations of the usual sum and intersection of vector spaces.) When $f_X, g_X$ are over $\mathbb{F}$ the **dot product** $\langle f_X, g_X \rangle$ of $f_X$ and $g_X$ is defined by $\langle f_X, g_X \rangle = \sum_{e \in X} f_X(e)g_X(e)$. We say $f_X, g_X$ are **orthogonal** iff $\langle f_X, g_X \rangle = 0$. The collection of all vectors orthogonal to vectors in $\mathcal{K}_X$ is denoted by $\mathcal{K}_X^{\perp}$. When $\mathcal{K}_X$ is a vector space we have $(\mathcal{K}_X^{\perp})^{\perp} = \mathcal{K}_X$. Using the fact that $(\mathcal{V}_X^{\perp})^{\perp} = \mathcal{V}_X$, one can verify that $(\mathcal{V}_X^1 + \mathcal{V}_X^2)^{\perp} = (\mathcal{V}_X^1)^{\perp} \cap (\mathcal{V}_X^2)^{\perp}, (\mathcal{V}_X^1 \cap \mathcal{V}_X^2)^{\perp} = (\mathcal{V}_X^1)^{\perp} + (\mathcal{V}_X^2)^{\perp}$. Our general definition of sum and

<footnote>* Corresponding author
Email address: hn@ee.iitb.ac.in (H. Narayanan)</footnote>
intersection of vector spaces allows these results to go through even if the vector spaces are on different sets: $(\mathcal{V}_A^1 + \mathcal{V}_B^2)^\perp = (\mathcal{V}_A^1)^\perp \cap (\mathcal{V}_B^2)^\perp, (\mathcal{V}_A^1 \cap \mathcal{V}_B^2)^\perp = (\mathcal{V}_A^1)^\perp + (\mathcal{V}_B^2)^\perp$.

We say set $X$, $X'$ are copies of each other iff they are disjoint and there is a bijection, usually clear from the context, mapping $e \in X$ to $e' \in X'$. We need this operation in order to talk, for instance, of the vector $(v, i)$ where $v$ is a voltage vector on the edge set of a graph while $i$ is a current vector on the same set. We handle this by building a copy $E'$ of the edge set $E$ and say $v$ is on $E$ and $i$ is on $E'$. When $X$, $X'$ are copies of each other, the vectors $f_X$ and $f_{X'}$ are said to be copies of each other, i.e., $f_{X'}(e') = f_X(e)$. If the vectors on $X$ and $X'$ are not copies of each other, they would be distinguished using notation, such as, $f_X$, $\hat{f}_{X'}$ etc. Vectors without subscripts like, $x$, $\dot{x}$ and $w$, $\dot{w}$ are not necessarily copies of each other. When $A$ and $A'$ are copies of each other, the collections of vectors $\mathcal{K}_A$, $\mathcal{K}_{A'}$ (or say $\mathcal{V}_A$, $\mathcal{V}_{A'}$) always represent copies of each other. We would usually write $\mathcal{K}_{A'} := (\mathcal{K}_A)_{A'} := \{f_{A'} : f_A \in \mathcal{K}_A\}$. The collection $\{(f_X, \lambda f_Y) : (f_X, f_Y) \in \mathcal{K}_{XY}\}, \lambda \in \mathbb{F}$, is denoted by $\mathcal{K}_{X(\lambda Y)}$. When $\lambda = -1$ we would write more simply $\mathcal{K}_{X(-Y)}$. Observe that $(\mathcal{K}_{X(-Y)})_{X(-Y)} = \mathcal{K}_{XY}$. Suppose $\mathcal{K}_{AC} := \mathcal{K}_{AB} \leftrightarrow \mathcal{K}_{BC}$. Let $A', B', C'$, be pairwise disjoint copies of $A, B, C$, respectively. We often simply write $(\mathcal{K}_{AC})_{A'C'}$ as $(\mathcal{K}_{AB} \leftrightarrow \mathcal{K}_{BC})_{A'C'}$. This latter expression should be taken to mean $(\mathcal{K}_{AB})_{A'B'} \leftrightarrow (\mathcal{K}_{BC})_{B'C'} = (\mathcal{K}_{AC})_{A'C'}$.

**Theorem 1. (Implicit inversion theorem)** Consider the equation $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} = \mathcal{V}_{SQ}$. Then

1. given $\mathcal{V}_{SP}, \mathcal{V}_{SQ}, \exists \mathcal{V}_{PQ}$, satisfying the equation iff $\mathcal{V}_{SP} \circ S \supseteq \mathcal{V}_{SQ} \circ S$ and $\mathcal{V}_{SP} \times S \subseteq \mathcal{V}_{SQ} \times S$;

2. given $\mathcal{V}_{SP}, \mathcal{V}_{PQ}, \mathcal{V}_{SQ}$ satisfying the equation, we have $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{SQ} = \mathcal{V}_{PQ}$ iff $\mathcal{V}_{SP} \circ P \supseteq \mathcal{V}_{PQ} \circ P$ and $\mathcal{V}_{SP} \times P \subseteq \mathcal{V}_{PQ} \times P$.

**Theorem 2. (Implicit duality theorem)** $(\mathcal{V}_{XY} \leftrightarrow \mathcal{V}_{YZ})^\perp = \mathcal{V}_{XY}^\perp \Leftrightarrow \mathcal{V}_{YZ}^\perp$. In particular, $(\mathcal{V}_{XY} \leftrightarrow \mathcal{V}_{Y})^\perp = \mathcal{V}_{XY}^\perp \leftrightarrow \mathcal{V}_{Y}^\perp$.

The implicit duality theorem is dealt with in some detail in Chapter 7 of [8].

For definitions on graphs and graph operations, please see the preliminaries section in [19].

An electrical network $\mathcal{N}$ is a pair $(\mathcal{G}_E, \mathcal{D}_E)$. Here $\mathcal{G}_E$ is a directed graph and $\mathcal{D}_E$ is a collection of pairs of vector functions of time $(v(\cdot), i(\cdot))$, where $v(t), i(t)$ are vectors on the edge set of the graph. $\mathcal{D}_E$ is called the 'device-characteristic' of the network. A **solution** of $\mathcal{N}$ is a pair $(v(\cdot), i(\cdot))$, satisfying

$$v(t) \in \mathcal{V}^v(\mathcal{G}_E), \quad i(t) \in \mathcal{V}^i(\mathcal{G}_E) \quad (\text{KVL, KCL}) \quad \text{and} \quad (v(\cdot), i(\cdot)) \in \mathcal{D}_E.$$

It is often convenient for us to deal with the pair $(v_E, i_E)$ as a single vector $(v_E, i_E')$ on $E \uplus E'$, where $E'$ is a disjoint copy of $E$. In this case, $\mathcal{D}_E$ would be a collection $\mathcal{K}_{EE'}$ of vector functions $(v_E(\cdot), i_E'(\cdot))$, the solution would be a vector function $(v_E(\cdot), i_E'(\cdot))$, satisfying

$v_E(t) \in \mathcal{V}^v(\mathcal{G}_E), \quad i_E'(t) \in \mathcal{V}^i(\mathcal{G}_E') \quad (\text{KVL, KCL}) \quad \text{and} \quad (v_E(\cdot), i_E'(\cdot)) \in \mathcal{K}_{EE'}, \mathcal{G}_E'$ being a copy of $\mathcal{G}_E$ with edge set $E'$. We may alternatively write $\mathcal{N} := (\mathcal{G}_E, \mathcal{K}_{EE'})$ or $\mathcal{N} := (\mathcal{V}_{EE'}^G, \mathcal{K}_{EE'})$, where $\mathcal{V}_{EE'}^G := \mathcal{V}^v(\mathcal{G}_E) \oplus (\mathcal{V}^i(\mathcal{G}_E))_{E'}$. The network is **static** iff the vector functions are constant functions.

An electrical multiport $\mathcal{N}_P$, is a network $(\mathcal{G}_{EP}, \mathcal{D}_E \times \mathcal{D}_P)$, where $\mathcal{D}_P := \mathcal{F}_{PP'}$, i.e., there are no device-characteristic constraints on $P$ and the current and voltage vectors on $P$ are only constrained by KCL and KVL equations of the graph. The device-characteristic $\mathcal{D}_E$ is the constraint $(v_E, i_E') \in \mathcal{K}_{EE'}$. A vector $(v_{EP}, i_{E'P'}) \in \mathcal{D}_E \times \mathcal{D}_P$ iff $(v_{EP}|_E, i_{E'P'}|_{E'}) \in \mathcal{D}_E$ and $(v_{EP}|_P, i_{E'P'}|_P) \in \mathcal{D}_P$. We would usually write $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$ since $\mathcal{D}_P := \mathcal{F}_{PP'}$. We may alternatively write $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{K}_{EE'})$ or $\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{K}_{EE'})$, where $\mathcal{V}_{EPE'P'} := \mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}$.

**Theorem 3.** An expression of the form $\leftrightarrow_{i,j,k,...} (\mathcal{K}_{(\pm A_i)(\pm B_j)(\pm C_k)...})$, where the index sets $\pm A_i, \pm B_j, \pm C_k, ...$ are all mutually disjoint, has a unique meaning provided it contains no null subexpression and no index set occurs more than twice in it.

**Remark 1.** 1. In $\leftrightarrow_{i,j,k,...} (\mathcal{K}_{(\pm A_i)(\pm B_j)(\pm C_k)...})$, the terms of the kind $p_{D_i}$ survive if they occur only once and they get coupled through the terms which occur twice. These latter dont survive in the final expression. Such an interpretation is valid even if we are dealing with signed index sets of the kind $-A_i$.
2. The condition 'contains no null subexpression' is not necessary if we define an object called $\mathcal{K}_0$, with the property that $\mathcal{K}_0 \leftrightarrow \mathcal{K}_A = \mathcal{K}_A$, for every $\mathcal{K}_A$, including $\mathcal{K}_0$. Whenever we have a term $(\mathcal{K}_A \leftrightarrow \mathcal{K}_A)$ or $(\mathcal{K}_A \leftrightarrow \mathcal{K}_{-A})$, we treat it as $\mathcal{K}_0$.

**Tellegen's Theorem** ([8]) states that $\mathcal{V}^v(\mathcal{G}_E) = \mathcal{V}^i(\mathcal{G}_E)^\perp$. The following result on vector spaces associated with graphs is useful.

$$ \mathcal{V}^v(\mathcal{G}_E \circ T) = \mathcal{V}^v(\mathcal{G}_E) \circ T, \quad \mathcal{V}^v(\mathcal{G}_E \times T) = \mathcal{V}^v(\mathcal{G}_E) \times T, \quad T \subseteq E; $$

$$ \mathcal{V}^i(\mathcal{G}_E \circ T) = \mathcal{V}^i(\mathcal{G}_E) \times T, \quad \mathcal{V}^i(\mathcal{G}_E \times T) = \mathcal{V}^i(\mathcal{G}_E) \circ T, \quad T \subseteq E. $$

### 3. Basic vector space results

We say $C_S$ is a **generator matrix** for a vector space $V_S$ iff the rows of $C_S$ span $V_S$. A generator matrix whose rows are linearly independent is called a **representative matrix**.

**Problem 1.** Describe how to eliminate variables when the constraints are linear and prove the following result.

**Theorem 4.** 1. $r(\mathcal{V}_{SP}) = r(\mathcal{V}_{SP} \circ S) + r(\mathcal{V}_{SP} \times P)$.

2. $\mathcal{V}_{SP}^{\perp} \circ P = (\mathcal{V}_{SP} \times P)^\perp$.

3. $\mathcal{V}_{SP}^{\perp} \times S = (\mathcal{V}_{SP} \circ S)^\perp$.

Answer

Let the constraints be

$$ (C_S \quad C_P) \begin{pmatrix} x_S \\ x_P \end{pmatrix} = s, \qquad (1) $$

and let it be required to compute the constraint it imposes on the variables $x_P$.

To do this we do invertible row operations on the equation to put it in the form

$$ \begin{pmatrix} C_{1S} & \cdots & C_{1P} \\ 0_{2S} & \cdots & C_{2P} \end{pmatrix} \begin{pmatrix} x_S \\ x_P \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}, \qquad (2) $$

where rows of $C_{1S}$ are linearly independent and span the rows of $C_S$. We claim that the Equation 1 imposes the constraint

$$ (C_{2P}) (x_P) = s_2, \qquad (3) $$

on $x_P$, i.e., whenever $\hat{x}_S, \hat{x}_P$ is a solution of Equation 1, $\hat{x}_P$ is a solution of Equation 3 and whenever $\hat{x}_P$ is a solution of Equation 3, there exists some $\hat{x}_S$, such that $\hat{x}_S, \hat{x}_P$ is a solution of Equation 1. The first part of the sentence is obvious. The second part follows because, for any given $\hat{x}_P$, the equation

$$ (C_{1S})x_S = -(C_{1P})\hat{x}_P + s_1 $$

has a solution since rows of $C_{1S}$ are linearly independent. It is clear that Equation 1 has a solution iff Equation 3 has a solution. The solution always exists if the rows of $(C_S|C_P)$ are linearly independent. We note that if the rows of $C_{2P}$ are linearly dependent, Equation 3 has a solution iff $\lambda^T(C_{2P}) = 0$ always implies $\lambda^T s_2 = 0$.

Let us now examine the special case, where the right side of Equation 1 is zero.

Let $(C_S|C_P)$ be a representative matrix for the vector space $\mathcal{V}_{SP}$. The solution space of Equation 1 would then be $\mathcal{V}_{SP}^\perp$.
Let $(C_{SP})$ denote the coefficient matrix in Equation 2. Since $(C_{SP})$ is obtained from $(C_S|C_P)$ by invertible linear operations, it is also a representative matrix for vector space $\mathcal{V}_{SP}$. Therefore, the rows of $(C_{2P})$, are linearly independent. Further, the rows of $(C_{1S})$ are independent and span the rows of $(C_S)$, by construction. Therefore, whenever $(f_S, f_P)$ is a vector in $\mathcal{V}_{SP}$, we must have $f_S$, linearly dependent on the rows of $(C_{1S})$. Since these rows are independent, if $(0_S, f_P)$ is a vector in $\mathcal{V}_{SP}$, $f_P$ must be linearly dependent on the rows of $(C_{2P})$. By the definition of restriction and contraction of vector spaces, we therefore conclude that $(C_{1S})$ is a representative matrix for $\mathcal{V}_{SP} \circ S$ and that $(C_{2P})$ is a representative matrix for $\mathcal{V}_{SP} \times P$.

The theorem follows from the form of the matrix $(C_{SP})$ and the above discussion.

**Problem 2.** 1. Prove the following identities about minors using the generalized minor operation.

(a) $\mathcal{V}_{SP} \times S = \mathcal{V}_{SP} \leftrightarrow \mathbf{0}_P; \mathcal{V}_{SP} \circ S = \mathcal{V}_{SP} \leftrightarrow \mathcal{F}_P. \mathcal{V}_{SP} \times (S \cup P_1) \circ S = \mathcal{V}_{SP} \circ (S \cup P_2) \times S.$

(b) $(\mathcal{V}_{SP} \times S)^\perp = \mathcal{V}_{SP}^\perp \circ S; (\mathcal{V}_{SP} \circ S)^\perp = \mathcal{V}_{SP}^\perp \times S.$

2. (a) Prove the following identities about the generalized minor operation.
($\mathcal{V}_{SP}^1 \cap \mathcal{V}_{SP}^2$) $\leftrightarrow$ $\mathcal{V}_P \subseteq (\mathcal{V}_{SP}^1 \leftrightarrow \mathcal{V}_P) \cap (\mathcal{V}_{SP}^2 \leftrightarrow \mathcal{V}_P)$; equality holds if $\mathcal{V}_{SP}^1 \times P \supseteq \mathcal{V}_P$. Hence
$(\mathcal{V}_{SP}^1 \cap \mathcal{V}_{SP}^2) \times P = (\mathcal{V}_{SP}^1 \times P) \cap (\mathcal{V}_{SP}^2 \times P)$.
$(\mathcal{V}_{SP}^1 + \mathcal{V}_{SP}^2) \leftrightarrow \mathcal{V}_P \supseteq (\mathcal{V}_{SP}^1 \leftrightarrow \mathcal{V}_P) + (\mathcal{V}_{SP}^2 \leftrightarrow \mathcal{V}_P)$; equality holds if $\mathcal{V}_{SP}^1 \circ P \subseteq \mathcal{V}_P$. Hence
$(\mathcal{V}_{SP}^1 + \mathcal{V}_{SP}^2) \circ P = (\mathcal{V}_{SP}^1 \circ P) + (\mathcal{V}_{SP}^2 \circ P)$.

(b) Let $\mathcal{V}_{SP} \circ P \supseteq \mathcal{H}_P^1, \mathcal{H}_P^2$, where $\mathcal{H}_P^1, \mathcal{H}_P^2$ are nonvoid collections of vectors on $P$. Then
$\mathcal{V}_{SP} \leftrightarrow (\mathcal{H}_P^1 + \mathcal{H}_P^2) = (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^1) + (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^2)$.

(c) Let $\mathcal{V}_P^1, \mathcal{V}_P^2$ be vector spaces on $P$. If $\mathcal{V}_{SP} \circ P \supseteq \mathcal{V}_P^1, \mathcal{V}_P^2$, then $\mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_P^1 + \mathcal{V}_P^2) = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^1) + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^2)$.
If $\mathcal{V}_{SP} \times P \supseteq \mathcal{V}_P^1, \mathcal{V}_P^2$, then $\mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_P^1 \cap \mathcal{V}_P^2) = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^1) \cap (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^2)$.

Answer

$$
\begin{align*}
1. \quad & \mathcal{V}_{SP} \times S = \mathcal{V}_{SP} \leftrightarrow \mathbf{0}_P; \mathcal{V}_{SP} \circ S = \mathcal{V}_{SP} \leftrightarrow \mathcal{F}_P. \\
& \mathcal{V}_{SP} \times (S \cup P_1) \circ S = (\mathcal{V}_{SP} \leftrightarrow \mathbf{0}_{P_2}) \leftrightarrow \mathcal{F}_{P_1} = (\mathcal{V}_{SP} \leftrightarrow \mathcal{F}_{P_1}) \leftrightarrow \mathbf{0}_{P_2} = \mathcal{V}_{SP} \circ (S \cup P_2) \times S \quad \text{(using Theorem 3)} \\
& (\mathcal{V}_{SP} \times S)^\perp = (\mathcal{V}_{SP} \leftrightarrow \mathbf{0}_P)^\perp = \mathcal{V}_{SP}^\perp \leftrightarrow \mathcal{F}_P \quad \text{(using Theorem 2)} = \mathcal{V}_{SP}^\perp \circ S. \\
& (\mathcal{V}_{SP} \circ S)^\perp = (\mathcal{V}_{SP} \leftrightarrow \mathcal{F}_P)^\perp = \mathcal{V}_{SP}^\perp \leftrightarrow \mathbf{0}_P = \mathcal{V}_{SP}^\perp \times S.
\end{align*}
$$

2(a) The proofs are routine. We will only examine cases where equality holds.

We have to show that $(\mathcal{V}_{SP}^1 \cap \mathcal{V}_{SP}^2) \leftrightarrow \mathcal{V}_P \supseteq (\mathcal{V}_{SP}^1 \leftrightarrow \mathcal{V}_P) \cap (\mathcal{V}_{SP}^2 \leftrightarrow \mathcal{V}_P)$, when $\mathcal{V}_{SP}^1 \times P \supseteq \mathcal{V}_P$. Let $\mathcal{V}_{SP}^1 \times P \supseteq \mathcal{V}_P$. Let $f_S \in (\mathcal{V}_{SP}^1 \leftrightarrow \mathcal{V}_P) \cap (\mathcal{V}_{SP}^2 \leftrightarrow \mathcal{V}_P)$. Then there exist $(f_S, f_P^1) \in \mathcal{V}_{SP}^1, (f_S, f_P^2) \in \mathcal{V}_{SP}^2$, such that $f_P^1, f_P^2 \in \mathcal{V}_P$. Since $\mathcal{V}_{SP}^1 \times P \supseteq \mathcal{V}_P$, we must have $(f_P^2 - f_P^1) \in \mathcal{V}_P \subseteq \mathcal{V}_{SP}^1 \times P$. It follows that $[(f_S, f_P^1) + (0_S, (f_P^2 - f_P^1))] = (f_S, f_P^2) \in \mathcal{V}_{SP}^1$, so that $(f_S, f_P^2) \in \mathcal{V}_{SP}^1 \cap \mathcal{V}_{SP}^2$ and $f_S \in (\mathcal{V}_{SP}^1 \cap \mathcal{V}_{SP}^2) \leftrightarrow \mathcal{V}_P$.

Next, let $\mathcal{V}_{SP}^1 \circ P \subseteq \mathcal{V}_P$. Then $(\mathcal{V}_{SP}^1)^\perp \times P \supseteq \mathcal{V}_P^\perp$, so that
$((\mathcal{V}_{SP}^1)^\perp \cap (\mathcal{V}_{SP}^2)^\perp) \leftrightarrow \mathcal{V}_P^\perp = ((\mathcal{V}_{SP}^1)^\perp \leftrightarrow \mathcal{V}_P^\perp) \cap ((\mathcal{V}_{SP}^2)^\perp \leftrightarrow \mathcal{V}_P^\perp)$.
Therefore $(\mathcal{V}_{SP}^1 + \mathcal{V}_{SP}^2) \leftrightarrow \mathcal{V}_P = (((\mathcal{V}_{SP}^1)^\perp \cap (\mathcal{V}_{SP}^2)^\perp) \leftrightarrow \mathcal{V}_P^\perp)^\perp$ (using Theorem 2)
$= (((\mathcal{V}_{SP}^1)^\perp \leftrightarrow \mathcal{V}_P^\perp) \cap ((\mathcal{V}_{SP}^2)^\perp \leftrightarrow \mathcal{V}_P^\perp))^\perp = (((\mathcal{V}_{SP}^1)^\perp \leftrightarrow \mathcal{V}_P^\perp)^\perp + ((\mathcal{V}_{SP}^2)^\perp \leftrightarrow \mathcal{V}_P^\perp))^\perp$
$= (\mathcal{V}_{SP}^1 \leftrightarrow \mathcal{V}_P) + (\mathcal{V}_{SP}^2 \leftrightarrow \mathcal{V}_P)$ (using Theorem 2).

2(b) Let $\mathcal{H}_P: \equiv \mathcal{H}_P^1 + \mathcal{H}_P^2$. First, since $\mathcal{V}_{SP}$ is a vector space, $(\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^1) + (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^2) \subseteq (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P)$. We will now show that $(\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P) \subseteq (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^1) + (\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^2)$.

Let $f_S \in \mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P$. Then, there exists $f_P \in \mathcal{H}_P$ such that $(f_S, f_P) \in \mathcal{V}_{SP}$.

Since $\mathcal{H}_P = \mathcal{H}_P^1 + \mathcal{H}_P^2$, we have $f_P = f_P^1 + f_P^2$, for some $f_P^1 \in \mathcal{H}_P^1, f_P^2 \in \mathcal{H}_P^2$ and since $\mathcal{V}_{SP} \circ P \supseteq \mathcal{H}_P^1, \mathcal{H}_P^2$, there must exist $f_S^1, f_S^2$ such that $(f_S^1, f_P^1) \in \mathcal{V}_{SP}, (f_S^2, f_P^2) \in \mathcal{V}_{SP}$ and therefore $(f_S^1 + f_S^2, f_P^1 + f_P^2) = (f_S^1 + f_S^2, f_P)$.

Now $(f_S, f_P) \in \mathcal{V}_{SP}$, so that we have $v_S \equiv f_S^1 + f_S^2 - f_S \in \mathcal{V}_{SP} \times S$.

Since $f_S^2 \in \mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^2, v_S \in \mathcal{V}_{SP} \times S$, so does $f_S^2 - v_S \in \mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P^2$.

2(c) From part (b) above, it follows that
$\mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_P^1 + \mathcal{V}_P^2) = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^1) + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^2)$, if $\mathcal{V}_{SP} \circ P \supseteq \mathcal{V}_P^1, \mathcal{V}_P^2$. We will now show that when $\mathcal{V}_{SP} \times P \subseteq \mathcal{V}_P^1, \mathcal{V}_P^2$, we have $\mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_P^1 \cap \mathcal{V}_P^2) = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^1) \cap (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^2)$.
The proof proceeds as in the second half of the proof of equality in 2(a).
Let $\mathcal{V}_{SP} \times P \subseteq \mathcal{V}_P^1, \mathcal{V}_P^2$. Then $\mathcal{V}_{SP}^{\perp} \circ P \supseteq (\mathcal{V}_P^1)^{\perp}, (\mathcal{V}_P^2)^{\perp}$ and therefore

$\mathcal{V}_{SP}^{\perp} \leftrightarrow ((\mathcal{V}_P^1)^{\perp} + (\mathcal{V}_P^2)^{\perp}) = (\mathcal{V}_{SP}^{\perp} \leftrightarrow (\mathcal{V}_P^1)^{\perp}) + (\mathcal{V}_{SP}^{\perp} \leftrightarrow (\mathcal{V}_P^2)^{\perp})$. It follows that $(\mathcal{V}_{SP}^{\perp} \leftrightarrow ((\mathcal{V}_P^1)^{\perp} + (\mathcal{V}_P^2)^{\perp}))^{\perp} = ((\mathcal{V}_{SP}^{\perp} \leftrightarrow (\mathcal{V}_P^1)^{\perp}) + (\mathcal{V}_{SP}^{\perp} \leftrightarrow (\mathcal{V}_P^2)^{\perp}))^{\perp}$.

Using Theorem 2 and the facts that $(\mathcal{V}_A^{\perp})^{\perp} = \mathcal{V}_A, (\mathcal{V}_A + \mathcal{V}'_A)^{\perp} = \mathcal{V}_A^{\perp} \cap (\mathcal{V}'_A)^{\perp}$, when $\mathcal{V}_A, \mathcal{V}'_A$ are vector spaces, the result now follows.

# 4. Variations of implicit inversion theorem

## 4.1. Preliminaries

* (To peruse this section the reader requires familiarity with the basic definitions of implicit linear algebra given in Section 2 and the implicit inversion theorem (Theorem 1).)

## 4.2. Implicit inversion for affine spaces

**Definition 5.** We say $\mathcal{V}_S$ is a vector space translate of the affine space $\mathcal{A}_S$, iff there exists a vector $\alpha_S$ such that $\mathcal{A}_S = \alpha_S + \mathcal{V}_S$.

**Problem 3.** Prove the following modification of Theorem 1 where in place of $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$, we have affine spaces $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$. Indicate how to test for nonvoidness of $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$.

**Theorem 6.** Let $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$, be affine spaces on $S \uplus P, P \uplus Q$, where $S, P, Q$ are pairwise disjoint sets. Let $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$ respectively, be the vector space translates of $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$. Let $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$ be nonvoid and let $\alpha_{SQ} \in \mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$. Then,

1. $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ} = \alpha_{SQ} + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})$.

2. $\mathcal{A}_{PQ} = \mathcal{A}_{SP} \leftrightarrow (\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ})$ iff $\mathcal{V}_{SP} \circ P \supseteq \mathcal{V}_{PQ} \circ P$ and $\mathcal{V}_{SP} \times P \subseteq \mathcal{V}_{PQ} \times P$.

**Answer**

*Proof.* 1. Since $\alpha_{SQ} \in \mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$, there exist $\alpha_{SP} \in \mathcal{A}_{SP}, \alpha_{PQ} \in \mathcal{A}_{PQ}$, such that $\alpha_{SP}|_P = \alpha_{PQ}|_P, \alpha_{SQ} = (\alpha_{SP}|_S, \alpha_{PQ}|_Q)$.

Let $x_{SQ} \in \mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ}$. Then there exist $x_{SP} \in \mathcal{V}_{SP}, x_{PQ} \in \mathcal{V}_{PQ}$, such that $x_{SP}|_P = x_{PQ}|_P, x_{SQ} = (x_{SP}|_S, x_{PQ}|_Q)$. Now $(\alpha_{SP} + x_{SP}) \in \mathcal{A}_{SP}, (\alpha_{PQ} + x_{PQ}) \in \mathcal{A}_{PQ}, (\alpha_{SP} + x_{SP})|_P = (\alpha_{PQ} + x_{PQ})|_P$, so that $(\alpha_{SQ} + x_{SQ}) \in \mathcal{A}_{SQ}$. We conclude that $\alpha_{SQ} + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ}) \subseteq (\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ})$.

Next, let $\beta_{SQ} \in \mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$. There exist $\beta_{SP} \in \mathcal{A}_{SP}, \beta_{PQ} \in \mathcal{A}_{PQ}$, such that $\beta_{SP}|_P = \beta_{PQ}|_P, \beta_{SQ} = (\beta_{SP}|_S, \beta_{PQ}|_Q)$. It follows that $(\alpha_{SP} - \beta_{SP}) \in \mathcal{V}_{SP}, (\alpha_{PQ} - \beta_{PQ}) \in \mathcal{V}_{PQ}, (\alpha_{SP} - \beta_{SP})|_P = (\alpha_{PQ} - \beta_{PQ})|_P$ and $(\alpha_{SQ} - \beta_{SQ}) \in (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})$. Thus $\alpha_{SQ} - (\alpha_{SQ} - \beta_{SQ}) = \beta_{SQ} \in \alpha_{SQ} + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})$.

We conclude that $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ} = \alpha_{SQ} + (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})$.

2. We are given that $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$ is nonvoid so that $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$ are nonvoid. We have by part 1 above, that the vector space translate of $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$ is $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ}$, where $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$, are respectively the vector space translates of $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$. Thus, again by part 1, $\mathcal{A}_{PQ} = \mathcal{A}_{SP} \leftrightarrow (\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ})$ iff $\mathcal{V}_{PQ} = \mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})$. The result now follows from part 2 of Theorem 1. $\square$

**Remark 2.** Testing whether $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$ is nonvoid is equivalent to checking whether a set of linear equations has a solution. Let $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$ be the vector space translates of $\mathcal{A}_{SP}, \mathcal{A}_{PQ}$, and let $(B_S|B_P), (C_P|C_Q)$ be representative matrices of $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$. Let $\mathcal{A}_{SP} = \alpha_{SP} + \mathcal{V}_{SP}, \mathcal{A}_{PQ} = \beta_{PQ} + \mathcal{V}_{PQ}$.

Let $\alpha_{SP}^T = (\alpha_S^T, \alpha_P^T), \beta_{PQ}^T = (\beta_P^T, \beta_Q^T)$. Consider the equation

$$ \lambda^T(B_P) + \alpha_P^T = \sigma^T(C_P) + \beta_P^T. \quad (4) $$

Let $\hat{\lambda}, \hat{\sigma}$ be a solution to this equation. Then the vector $(\hat{\lambda}^T(B_S|B_P) + (\alpha_S^T, \alpha_P^T)) \in \mathcal{A}_{SP}, (\hat{\sigma}^T(C_P|C_Q) + (\beta_P^T, \beta_Q^T)) \in \mathcal{A}_{PQ}, (\hat{\lambda}^T(B_S) + \alpha_S^T, \hat{\sigma}^T(C_Q) + \beta_Q^T) \in \mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$. Conversely, if $\mathcal{A}_{SP} \leftrightarrow \mathcal{A}_{PQ}$ is nonvoid, Equation 4 has a solution.
### 4.3. Generalization of implicit inversion

In the matched composition operation ($\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} \equiv \{f_{SQ} : f_{SQ} = (g|_S, h|_Q)\}$, where $g_{SP} \in \mathcal{V}_{SP}, h_{PQ} \in \mathcal{V}_{PQ}, g|_P = h|_Q$)), the common index set $P$ gets eliminated from the result of the operation. We know that $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} \equiv (\mathcal{V}_{SP} \cap \mathcal{V}_{PQ}) \circ S \uplus Q = (\mathcal{V}_{SP} + (\mathcal{V}_{PQ})(-P)Q) \times S \uplus Q$. But there are instances where the common index sets get only partially eliminated, for instance in the case of state feedback and output injection of control theory. The following problem deals with this situation and the relevant result can be regarded as a generalization of Theorem 1 (implicit inversion theorem (IIT)). Here we give a direct proof of the result. In Problem 48, we derive it as a consequence of IIT.

**Problem 4.** Prove the following generalization of IIT which has application to state feedback $\mathcal{V}_{WU}$ and output injection $\mathcal{V}_{\dot{W}Y}$ of a dynamical system $\mathcal{V}_{\dot{W}\dot{W}UY}$ which can be modelled respectively as $(\mathcal{V}_{\dot{W}\dot{W}UY} \cap \mathcal{V}_{WU}) \circ W \dot{W}$ and $(\mathcal{V}_{\dot{W}\dot{M}} + \mathcal{V}_{\dot{W}Y}) \times W \dot{W}$. The following result gives necessary and sufficient conditions for existence of such operations which will convert the dynamical system into the desired $\mathcal{V}_{\dot{W}\dot{M}}$. Further, the result also gives a method for building such operations that yield the desired $\mathcal{V}_{\dot{W}\dot{M}}$ (see Subsection 13.3).

**Theorem 7.** 1. Given $\mathcal{V}_{ABCD}, \mathcal{V}_{AB}$, there exists $\mathcal{V}_{AC}$ such that $(\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB = \mathcal{V}_{AB}$ iff

$$ \mathcal{V}_{ABCD} \circ AB \supseteq \mathcal{V}_{AB}; \quad \mathcal{V}_{ABCD} \circ ABC \times B \subseteq \mathcal{V}_{AB} \times B. \qquad (5) $$

Let the conditions in Equation 5 hold and let $\mathcal{V}_{AC} \equiv (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB}) \circ AC$. Then $(\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB = \mathcal{V}_{AB}$.

2. Given $\mathcal{V}_{ABCD}, \mathcal{V}_{AB}$, there exists $\mathcal{V}_{AC}$ such that $(\mathcal{V}_{ABCD} + \mathcal{V}_{AC}) \times AB = \mathcal{V}_{AB}$ iff

$$ \mathcal{V}_{ABCD} \times AB \subseteq \mathcal{V}_{AB}; \quad \mathcal{V}_{ABCD} \times ABC \circ B \supseteq \mathcal{V}_{AB} \circ B. \qquad (6) $$

Let the conditions in Equation 6 hold and let $\mathcal{V}_{AC} \equiv (\mathcal{V}_{ABCD} + \mathcal{V}_{AB}) \times AC$. Then $(\mathcal{V}_{ABCD} + \mathcal{V}_{AC}) \times AB = \mathcal{V}_{AB}$.

**Answer**

We need the following routine lemma for the proof of Theorem 7. The proof is available in solution to Problem 2.

**Lemma 8.** 1. $(\mathcal{V}_{ST}^1 + \mathcal{V}_{ST}^2) \circ S = (\mathcal{V}_{ST}^1 \circ S) + (\mathcal{V}_{ST}^2 \circ S)$;

2. $(\mathcal{V}_{ST}^1 \cap \mathcal{V}_{ST}^2) \times S = (\mathcal{V}_{ST}^1 \times S) \cap (\mathcal{V}_{ST}^2 \times S)$;

3. $(\mathcal{V}_{ST}^1 + \mathcal{V}_{ST}^2) \times S \supseteq (\mathcal{V}_{ST}^1 \times S) + (\mathcal{V}_{ST}^2 \times S)$;

4. $(\mathcal{V}_{ST}^1 \cap \mathcal{V}_{ST}^2) \circ S \subseteq (\mathcal{V}_{ST}^1 \circ S) \cap (\mathcal{V}_{ST}^2 \circ S)$;

**Proof.** (Proof of Theorem 7)

1. (only if) Let $(\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB = \mathcal{V}_{AB}$. Suppose $(f_A, f_B) \in \mathcal{V}_{AB}$. By the definition of $\mathcal{V}_{AB}$, we must have $(f_A, f_B, f_C, f_D) \in \mathcal{V}_{ABCD}$ and $(f_A, f_C) \in \mathcal{V}_{AC}$, for some $f_C, f_D$. Therefore $(f_A, f_B) \in \mathcal{V}_{ABCD} \circ AB$. Next, let $f_B \in \mathcal{V}_{ABCD} \circ ABC \times B$. Then for some $f_D$, $(0_A, f_B, 0_C, f_D) \in \mathcal{V}_{ABCD}$, with $(0_A, 0_C) \in \mathcal{V}_{AC}$ so that $(0_A, f_B) \in (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB = \mathcal{V}_{AB}$. Therefore, $f_B \in \mathcal{V}_{AB} \times B$.

(if) Let conditions in Equation 5 hold. Suppose $(f_A, f_B) \in \mathcal{V}_{AB} \subseteq (\mathcal{V}_{ABCD} \circ AB)$. Then there exist $f_C, f_D$, such that $(f_A, f_B, f_C, f_D) \in (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB})$. Therefore $(f_A, f_B, f_C, f_D) \in ((\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB}) \circ AC) \oplus \mathcal{F}_B \oplus \mathcal{F}_D$ and $(f_A, f_B) \in (\mathcal{V}_{ABCD} \cap ((\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB}) \circ AC) \oplus \mathcal{F}_B \oplus \mathcal{F}_D)) \circ AB = (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB$. Thus $\mathcal{V}_{AB} \subseteq (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB$.

Next, let $(f_A, f_B) \in (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB = (\mathcal{V}_{ABCD} \cap ((\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB}) \circ AC) \oplus \mathcal{F}_B \oplus \mathcal{F}_D)) \circ AB$. Therefore there exist $f_C, f_D$, such that $(f_A, f_B, f_C, f_D) \in \mathcal{V}_{ABCD}$ and $(f_A, f_C) \in \mathcal{V}_{AC} = (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB}) \circ AC$. Therefore there exist $f_{B'}$, $f_{D'}$ such that $(f_A, f_{B'}$, $f_C$, $f_{D'}) \in (\mathcal{V}_{ABCD} \cap \mathcal{V}_{AB})$. It follows that $(f_A, f_{B'}) \in \mathcal{V}_{AB}$ and $(f_A, f_{B'}, f_C) \in \mathcal{V}_{ABCD} \circ ABC$. Now $(f_A, f_B, f_C) - (f_A, f_{B'}, f_C) \in \mathcal{V}_{ABCD} \circ ABC$, so that $(f_B - f_{B'}) \in \mathcal{V}_{ABCD} \circ ABC \times B \subseteq \mathcal{V}_{AB} \times B$. Therefore $(f_A, f_{B'}) + (0_A, (f_B - f_{B'})) = (f_A, f_B) \in \mathcal{V}_{AB}$. Thus $(\mathcal{V}_{ABCD} \cap \mathcal{V}_{AC}) \circ AB \subseteq \mathcal{V}_{AB}$.
2. We will dualize Theorem 7 using Theorem 2. Let $\hat{\mathcal{V}}$ denote $\mathcal{V}^{\perp}$. We then have the statement of Theorem 7 for $\hat{\mathcal{V}}_{ABCD}, \hat{\mathcal{V}}_{AB}, \hat{\mathcal{V}}_{AC}$:
Given $\hat{\mathcal{V}}_{ABCD}, \hat{\mathcal{V}}_{AB}$, there exists $\hat{\mathcal{V}}_{AC}$ such that $(\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AC}) \circ AB = \hat{\mathcal{V}}_{AB}$ iff

$$ \hat{\mathcal{V}}_{ABCD} \circ AB \supseteq \hat{\mathcal{V}}_{AB}; \quad \hat{\mathcal{V}}_{ABCD} \circ ABC \times B \subseteq \hat{\mathcal{V}}_{AB} \times B. \qquad (7) $$

If conditions in Equation 7 hold and $\hat{\mathcal{V}}_{AC} := (\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AB}) \circ AC$, then $(\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AC}) \circ AB = \hat{\mathcal{V}}_{AB}$.
Now $(\hat{\mathcal{V}})^{\perp} = \mathcal{V}$. Therefore

$$ (\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AC}) \circ AB = \hat{\mathcal{V}}_{AB} \text{ is equivalent to } (\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AC})^{\perp} \times AB = (\hat{\mathcal{V}}_{AB})^{\perp}, \text{ i.e., to} \\ (\mathcal{V}_{ABCD} + \mathcal{V}_{AC}) \times AB = \mathcal{V}_{AB}; $$

$$ \hat{\mathcal{V}}_{AC} := (\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AB}) \circ AC \text{ is equivalent to } (\hat{\mathcal{V}}_{AC})^{\perp} = (\hat{\mathcal{V}}_{ABCD} \cap \hat{\mathcal{V}}_{AB})^{\perp} \times AC, \text{ i.e., to} $$

$$ \mathcal{V}_{AC} = (\mathcal{V}_{ABCD} + \mathcal{V}_{AB}) \times AC; $$

$$ \hat{\mathcal{V}}_{ABCD} \circ AB \supseteq \hat{\mathcal{V}}_{AB} \text{ is equivalent to } (\hat{\mathcal{V}}_{ABCD})^{\perp} \times AB \subseteq (\hat{\mathcal{V}}_{AB})^{\perp}, \text{ i.e., to } \mathcal{V}_{ABCD} \times AB \subseteq \mathcal{V}_{AB}; $$

$$ \hat{\mathcal{V}}_{ABCD} \circ ABC \times B \subseteq \hat{\mathcal{V}}_{AB} \times B, \text{ is equivalent to } (\hat{\mathcal{V}}_{ABCD})^{\perp} \times ABC \circ B \supseteq (\hat{\mathcal{V}}_{AB})^{\perp} \circ B, \text{ i.e., to} $$

$$ \mathcal{V}_{ABCD} \times ABC \circ B \supseteq \mathcal{V}_{AB} \circ B. $$

The result follows.

□

# 5. Linkages and maps

## 5.1. Generalization of maps to linkages

A **linkage** is a vector space $\mathcal{V}_S$ with a specified partition $\{S_1, \dots, S_k\}$ of $S$. We will denote it by $\mathcal{V}_{S_1 \dots S_k}$, the blocks of the partition $\{S_1, \dots, S_k\}$, being called 'index sets'. Observe that a map $x^T K = y^T$ can be regarded as a linkage $\mathcal{V}_{XY}$, with a typical vector $(x^T, y^T)$, whose basis is the set of rows of $[I \ K]$, the first set of columns of the matrix being indexed by $X$ and the second set by $Y$.

**Problem 5.** Show that the matched composition operation " $\leftrightarrow$ " can be regarded as a generalization of the composition operation for ordinary maps. What are the differences between the two operations?

*Answer*

If $x^T K = y^T$, $y^T P = z^T$, it can be seen that $\mathcal{V}_{XY} \leftrightarrow \mathcal{V}_{YZ}$ would have as the basis, the rows of $[I \ KP]$, the first set of columns of the matrix being indexed by $X$ and the second set by $Z$.

1. When we compose matrices, the order is important. In the case of linkages, since vectors are indexed by subsets, order does not matter. Thus $\mathcal{V}_{SP} = \mathcal{V}_{PS}$ and $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} = \mathcal{V}_{PQ} \leftrightarrow \mathcal{V}_{PS}$.

2. $\mathcal{V}_{XY}$ mimics the map $K$ by linking row vectors $x^T$, $y^T$ which correspond to each other when $x^T$ is operated upon by $K$, into the long vector $(x^T, y^T)$. The collection of all such vectors forms a vector space which contains all the information that the map $K$ and $K^{-1}$ (if it exists) contain and represents both of them implicitly.

But there are two essential differences: a map takes vectors in $\mathcal{F}_X$ to vectors in $\mathcal{F}_Y$, but takes the vector $0_X$ only to the vector $0_Y$. In the case of linkages, only a subspace of $\mathcal{F}_X$ may be involved as $\mathcal{V}_{XY} \circ X$ and the vector $0_X$ may be linked to a nontrivial subspace of $\mathcal{F}_Y$.

3. If we represent the interaction between operators through composition by graphs, operators corresponding to nodes and the product $A_1A_2$, corresponding to a directed edge between node $A_1$ to node $A_2$, the graph representing interaction between operators can only be a directed path, $A_1A_2 \dots A_n$ corresponding to a directed line from node $A_1$ to node $A_n$.

The corresponding situation for linkages, in the case, where no index set occurs more than twice, is very much more flexible. The linkages are represented by nodes and index sets by *undirected edges*: whenever we have $\mathcal{V}_{ABC} \leftrightarrow \mathcal{V}_{BDFG}$ occurring, there is an edge between node $\mathcal{V}_{ABC}$ and node $\mathcal{V}_{BDFG}$. Indeed any graph could be made into the 'interaction graph' of an appropriate set of linkages. The interaction graph can be thought of as representing the result of the '$\leftrightarrow$' operations on the linkages, this result being a linkage which has as index sets every index set which occurs only once in the
original collection of linkages. We could therefore add this linkage as an 'output node' (calling this linkage as the output linkage) and introduce dotted lines to this output node from linkages which have an index set in common with this node. Let us call this graph, the extended interaction graph. (We can make an edge between node $\mathcal{Y}_{ABC}$ and node $\mathcal{Y}_{BDFG}$, directed in the interaction graph, iff $\mathcal{Y}_{ABC} \circ B \supseteq \mathcal{Y}_{BDFG} \circ B$, and $\mathcal{Y}_{ABC} \times B \subseteq \mathcal{Y}_{BDFG} \times B$. By Theorem 1, in the extended interaction graph the dotted lines to the output node will all be directed. The interaction graph does not change if we replace every linkage by its orthogonal complement, neither do the direction of edges if they are directed.)

## 5.2. Existence and uniqueness of solutions of equations

**Problem 6.** The following result is well known.

**Theorem 9.** $Ax = b$ has a solution iff whenever $\lambda^T A = 0$, we also have $\lambda^T b = 0$. The solution is unique only if columns of $A$ are independent.

How is this result related to the implicit inversion theorem (IIT) (Theorem 1)?

**Answer**

Notation: To indicate a row vector in equations we use the transpose symbol. For instance, $f_S^T$ would indicate a row vector.

We first note that Theorem 9 is not true in general for modules, for instance when entries of $A$ are real polynomials in $\xi$, whereas IIT is true for modules (see the proof of Theorem 1 in the appendix of [19]). However, the equation $Ax = b$ can be written in the form $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ} = \mathcal{Y}_{SQ}$. We examine this aspect and identify where the break between the two results occurs.

We denote by $\{[K]\}$ the space spanned by the rows of the matrix $K$. We will associate with $A, x, b$ vector spaces $\mathcal{Y}_{SP}, \mathcal{Y}_{PQ}, \mathcal{Y}_{SQ}$ respectively, where

$\mathcal{Y}_{SP}$ is the space of vectors $(f_S, g_P)$ with $f_S^T A = g_P^T, \mathcal{Y}_{SP} \circ S = \mathcal{F}_S$,

$\mathcal{Y}_{PQ}$ is a space of vectors $(g_P, h_Q)$ with $g_P^T x = h_Q^T$,

$\mathcal{Y}_{SQ}$ is the space of vectors $(f_S, h_Q)$ with $f_S^T b = h_Q^T, \mathcal{Y}_{SQ} \circ S = \mathcal{F}_S$.

Observe that from $\mathcal{Y}_{SP}, \mathcal{Y}_{PQ}, \mathcal{Y}_{SQ}$ we can uniquely infer $A, x, b$.

The equation $Ax = b$ translates to $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ} = \mathcal{Y}_{SQ}$.

By IIT, we have that $\mathcal{Y}_{PQ}$ exists such that $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ} = \mathcal{Y}_{SQ}$ iff $\mathcal{Y}_{SP} \circ S \supseteq \mathcal{Y}_{SQ} \circ S$ and $\mathcal{Y}_{SP} \times S \subseteq \mathcal{Y}_{SQ} \times S$. The first condition is automatic for maps since the domain is $\mathcal{F}_S$ which translates to $\mathcal{Y}_{SP} \circ S = \mathcal{F}_S$. The second condition is equivalent to stating that 'whenever $f_S^T A = 0$, we must also have $f_S^T b = 0', which is the same as saying $b \in (\text{col}(A))^{\perp}$.

We need next to show that existence of a solution $\mathcal{Y}_{PQ}$ to the equation also implies that there is another solution of the form $\{[I \ \hat{x}]\}$.

We try to do this as follows. If $\mathcal{Y}_{SP} = \{[I \ A]\}, \mathcal{Y}_{SQ} = \{[I \ b]\}$ then $\mathcal{Y}_{PQ} = \mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{SQ} = \{[A \ b]\}$ and $\mathcal{Y}_{SP} \circ P = \mathcal{Y}_{PQ} \circ P$. We may assume wlog rows of $\{[A \ b]\}$ to be independent. This implies that the rows of $A$ are linearly independent (using 'whenever $f_S^T A = 0$, we must also have $f_S^T b = 0'). Now we try to extend $\mathcal{Y}_{PQ}$ to a vector space $\mathcal{Y}'_{PQ}$ such that $\mathcal{Y}'_{PQ} \cdot P = \mathcal{F}_P$. If this can be done, it can be seen that $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}'_{PQ}$ is equal to $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ}$ and further $\mathcal{Y}'_{PQ}$ has the form $\{[I \ \hat{x}]\}$. But, while this can be done in the case of vector spaces, in general for modules, we cannot add additional rows to $(A)$ to obtain a matrix $\begin{pmatrix} A \\ A_2 \end{pmatrix}$, with independent rows which span $\mathcal{F}_P$.

Next, let $\mathcal{Y}_{SP}, \mathcal{Y}_{SQ}$ be such that there exists some $\mathcal{Y}_{PQ}$ satisfying $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ} = \mathcal{Y}_{SQ}$.

We know by Theorem 1, it is unique only if $\mathcal{Y}_{SP} \circ P \supseteq \mathcal{Y}_{PQ} \circ P$ and $\mathcal{Y}_{SP} \times P \subseteq \mathcal{Y}_{PQ} \times P$. The second condition is trivial since $0_S^T A = 0_P$, so that $\mathcal{Y}_{SP} \times P = 0_P$.

Next, note that since $x$ corresponds to the map $g_P^T x = h_Q^T$, we must have $\mathcal{Y}_{PQ} \circ P = \mathcal{F}_P$.

So the first condition implies that the range of the map $f_S^T A = g_P^T$, must be $\mathcal{F}_P$.

This means that columns of $A$ are independent.
### 5.3. Generalization of product of maps

**Problem 7.** Generalize the notion of product of maps to linkages. Define transpose of linkages and prove the generalization of $(AB)^T = B^T A^T$.

**Answer**

The matched composition operation acts similar to the operation of product of maps and can be regarded as a generalization of the notion of product of maps to linkages. We define the **transpose** $\mathcal{V}_{AB}^T$ of $\mathcal{V}_{AB}$ as $\mathcal{V}_{AB}^T := (\mathcal{V}_{AB}^{\perp})_{(-A)B}$ and have the following result on transpose of matched composition.

**Theorem 10.** Let $\mathcal{V}_{SP}, \mathcal{V}_{PQ}$ be linkages. We have $(\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})^T = \mathcal{V}_{SP}^T \leftrightarrow \mathcal{V}_{PQ}^T$.

*Proof.* We have by Theorem 2 and the definition of transpose, $(\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})^T = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ})_{S(-Q)}^{\perp} = ((\mathcal{V}_{SP}^{\perp})_{S(-P)} \leftrightarrow \mathcal{V}_{PQ}^{\perp})_{S(-Q)} = (\mathcal{V}_{SP}^{\perp})_{S(-P)} \leftrightarrow (\mathcal{V}_{PQ}^{\perp})_{P(-Q)} = \mathcal{V}_{SP}^T \leftrightarrow \mathcal{V}_{PQ}^T$. $\square$

The order of operations is not relevant in the case of the generalization because the definition of linkages is in terms of the partition of the index set, independent of the order of the blocks.

### 5.4. Pseudoidentity

Let subset $A'$ be a copy of $A$, both being disjoint from the subset $B$. We say the linkage $\mathcal{V}_{AA'}$ is a pseudoidentity for a linkage $\mathcal{V}_{AB}$ iff $\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB} = (\mathcal{V}_{AB})_{A'B}$. We denote by $I_{AA'}$, the linkage $\{(f_A, f_{A'}) : f_A \in \mathcal{F}_A\}$. We will call a linkage $\mathcal{V}_{AA'}$, symmetric iff $\mathcal{V}_{AA'} \supseteq I_{AA'} \cap (\mathcal{V}_{AA'} \circ A)$ and $\mathcal{V}_{AA'} = (\mathcal{V}_{AA'})_{A'A}$, i.e., if $f_A \in \mathcal{V}_{AA'} \circ A$, then $(f_A, f_{A'}) \in \mathcal{V}_{AA'}$ and if $(f_A, g_{A'}) \in \mathcal{V}_{AA'}$ then $(g_A, f_{A'}) \in \mathcal{V}_{AA'}$.

**Problem 8.** Prove the following result regarding pseudoidentity.

**Lemma 11.** 1. If $\mathcal{V}_{AA'}$ is symmetric and $(f_A, g_{A'})$, $(g_A, h_{A'}) \in \mathcal{V}_{AA'}$, then $(f_A, h_{A'}) \in \mathcal{V}_{AA'}$.

2. If $\mathcal{V}_{AA'}$ is symmetric, $\mathcal{V}_{AA'}$ is a pseudoidentity for a linkage $\mathcal{V}_{AB}$ iff $\mathcal{V}_{AA'} \circ A \supseteq \mathcal{V}_{AB} \circ A$ and $\mathcal{V}_{AA'} \times A \subseteq \mathcal{V}_{AB} \times A$.

3. $\mathcal{V}_{AP} \leftrightarrow (\mathcal{V}_{AP})_{A'P}$, where $A'$ is a copy of $A$ is a symmetric pseudoidentity for $\mathcal{V}_{AB}$, if $\mathcal{V}_{AP} \circ A \supseteq \mathcal{V}_{AB} \circ A$, $\mathcal{V}_{AP} \times A \subseteq \mathcal{V}_{AB} \times A$. In particular, $\mathcal{V}_{AB} \leftrightarrow (\mathcal{V}_{AB})_{A'B}$, where $A'$ is a copy of $A$ is a symmetric pseudoidentity for $\mathcal{V}_{AB}$.

**Answer**

*Proof.* 1. If $(f_A, g_{A'}) \in \mathcal{V}_{AA'}$, then since $(f_A, f_{A'}) \in \mathcal{V}_{AA'}$ and $\mathcal{V}_{AA'}$ is a vector space, we must have $(0_A, g_{A'} - f_{A'}) \in \mathcal{V}_{AA'}$. Since $(g_A, h_{A'}) \in \mathcal{V}_{AA'}$, we must have $(h_A, g_{A'}) \in \mathcal{V}_{AA'}$. So $(h_A, g_{A'}) - (0_A, g_{A'} - f_{A'}) = (h_A, f_{A'}) \in \mathcal{V}_{AA'}$. So $(f_A, h_{A'}) \in \mathcal{V}_{AA'}$.

2. (only if) Suppose $\mathcal{V}_{AA'} \circ A \supseteq \mathcal{V}_{AB} \circ A$. Then there exists $(f_A, g_B) \in \mathcal{V}_{AB}$ such that $f_A \notin \mathcal{V}_{AA'} \circ A$ and $f_{A'} \notin \mathcal{V}_{AA'} \circ A'$. But then $(f_{A'}, g_B) \notin (\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB})$, which contradicts the fact that $\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB} = (\mathcal{V}_{AB})_{A'B}$. Next, suppose $\mathcal{V}_{AA'} \times A \supseteq \mathcal{V}_{AB} \times A$. Then there exists $(f_A, 0_{A'}) \in \mathcal{V}_{AA'}$, such that $(f_A, 0_B) \notin \mathcal{V}_{AB}$. Now $(0_A, f_{A'}) \in \mathcal{V}_{AA'}$ and $(0_A, 0_B) \in \mathcal{V}_{AB}$. So $(f_{A'}, 0_B) \in \mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB} = (\mathcal{V}_{AB})_{A'B}$, a contradiction. (if) Let $(f_{A'}, g_B) \in (\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB})$. Then there exist $(h_A, f_{A'}) \in \mathcal{V}_{AA'}$, $(h_A, g_B) \in \mathcal{V}_{AB}$. Now $(f_A, f_{A'}) \in \mathcal{V}_{AA'}$ so that $(h_A - f_A, 0_{A'}) \in \mathcal{V}_{AA'}$. Thus $(h_A - f_A) \in \mathcal{V}_{AA'} \times A \subseteq \mathcal{V}_{AB} \times A$. Since $(h_A, g_B)$, $(h_A - f_A, 0_B) \in \mathcal{V}_{AB}$ and $\mathcal{V}_{AB}$ is a vector space, it follows that $(f_A, g_B) \in \mathcal{V}_{AB}$. Next, let $(f_A, g_B) \in \mathcal{V}_{AB}$. Since $f_A \in \mathcal{V}_{AB} \circ A \subseteq \mathcal{V}_{AA'} \circ A$, it follows from the symmetry of $\mathcal{V}_{AA'}$ that $(f_A, f_{A'}) \in \mathcal{V}_{AA'}$. But then $(f_{A'}, g_B) \in (\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB})$. It thus follows that $(\mathcal{V}_{AA'} \leftrightarrow \mathcal{V}_{AB}) = (\mathcal{V}_{AB})_{A'B}$, i.e., $\mathcal{V}_{AA'}$ is a pseudoidentity for $\mathcal{V}_{AB}$.
3. It is easily verified that $\mathcal{V}_{AP} \leftrightarrow (\mathcal{V}_{AP})_{A'P}$, is symmetric.

Also, $(\mathcal{V}_{AP} \leftrightarrow (\mathcal{V}_{AP})_{A'P}) \circ A = \mathcal{V}_{AP} \circ A$ and $(\mathcal{V}_{AP} \leftrightarrow (\mathcal{V}_{AP})_{A'P}) \times A = \mathcal{V}_{AP} \times A$. The result now follows from part 2 above. $\square$

### 5.5. Generalization of sums of maps

**Problem 9.** Generalize the notion of sums of maps to the case of linkages of the kind $\mathcal{V}_{AB}$. Prove the generalization of $(A+B)^T = A^T + B^T$.

*Answer*

Note that, in the case of maps, $(A+B)$ is defined only when we have the same domain. For linkages, the corresponding ideas are as follows.

**Definition 12.** Let $\mathcal{V}_{AB}$, $\hat{\mathcal{V}}_{AB}$ be linkages. The intersection-sum

$$ \mathcal{V}_{AB} + b \hat{\mathcal{V}}_{AB} := \{(f_A, f_B) : (f_A, f_B^1) \in \mathcal{V}_{AB}, (f_A, f_B^2) \in \hat{\mathcal{V}}_{AB}, f_B = f_B^1 + f_B^2\}. $$

Such a definition, which speaks both of ‘domain’ and ‘range’ instead of only ‘range’ in the case of ordinary maps, is natural because for ordinary maps the domain has the form $\mathcal{F}_A$ whereas for linkages, $\mathcal{V}_{AB} \circ A$ and $\hat{\mathcal{V}}_{AB} \circ A$ need not be the same. Note that, by definition, $(\mathcal{V}_{AB} + b \hat{\mathcal{V}}_{AB}) \circ A = (\mathcal{V}_{AB} \circ A) \cap (\hat{\mathcal{V}}_{AB} \circ A), (\mathcal{V}_{AB} + b \hat{\mathcal{V}}_{AB}) \times B = (\mathcal{V}_{AB} \times B) + (\hat{\mathcal{V}}_{AB} \times B)$.

An immediate consequence of the definition is the following.

**Lemma 13.** The ‘+b’ operation is associative and commutative.

We give below a useful way of visualizing the intersection-sum operation. As before, we denote by $\{[K]\}$ the space spanned by the rows of the matrix $K$. Thus

$$ \{[I_A \ I_{A'} \ I_{A''}]\} $$

denotes the collection of all vectors

$$ f_{AA'A''}, \text{ where } f_{AA'A''}|_A = (f_{AA'A''}|_{A'})_A = (f_{AA'A''}|_{A''})_A, \ (A, A', A'' \text{ being copies of each other}). $$

$$ \left\{ \begin{bmatrix} I_A & I_{A'} & 0 \\ I_A & 0 & I_{A'} \end{bmatrix} \right\} \qquad (8) $$

denotes the collection of all vectors $f_{AA'A''}$, where $f_{AA'A''}|_A = (f_{AA'A''}|_{A'})_A + (f_{AA'A''}|_{A''})_A$. It is clear that $\mathcal{V}_{AB} \leftrightarrow \{[I_A \ I_{A'}]\} = (\mathcal{V}_{AB})_{A'B}$.

Next, consider $\mathcal{V}_{A'B'} \oplus \hat{\mathcal{V}}_{A''B''}$. This space is a direct sum of copies of $\mathcal{V}_{AB}$, $\hat{\mathcal{V}}_{AB}$ built respectively on disjoint copies $A' \oplus B'$ and $A'' \oplus B''$ of $A \oplus B$. The space

$$ \mathcal{V}_{A'B'} \oplus \hat{\mathcal{V}}_{A''B''} \leftrightarrow \{[I_A \ I_{A'} \ I_{A''}]\} \oplus \left\{ \begin{bmatrix} I_B & I_{B'} & 0 \\ I_B & 0 & I_{B''} \end{bmatrix} \right\} $$

is on the set $A \cup B$ and can be seen to be the collection

$$ \{(f_A, f_B) : (f_A, f_B^1) \in \mathcal{V}_{AB}, (f_A, f_B^2) \in \hat{\mathcal{V}}_{AB}, f_B = f_B^1 + f_B^2\}. $$

[The ‘$\leftrightarrow$’ operation with $\{[I_A \ I_{A'} \ I_{A''}]\} \oplus \left\{ \begin{bmatrix} I_B & I_{B'} & 0 \\ I_B & 0 & I_{B''} \end{bmatrix} \right\}$ forces equality of the $A$ components and addition of the $B$ components.] We thus have the following lemma.

**Lemma 14.**

$$ \mathcal{V}_{AB} + b \hat{\mathcal{V}}_{AB} = \mathcal{V}_{A'B'} \oplus \hat{\mathcal{V}}_{A''B''} \leftrightarrow (\{[I_A \ I_{A'} \ I_{A''}]\} \oplus \left\{ \begin{bmatrix} I_B & I_{B'} & 0 \\ I_B & 0 & I_{B''} \end{bmatrix} \right\}). $$
2. $(\lambda_1^b + \lambda_2^b)\mathcal{Y}_{AB} = \lambda_1^b\mathcal{Y}_{AB} +_b \lambda_2^b\mathcal{Y}_{AB}.$

3. $\lambda^b\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC} = \mathcal{Y}_{AB} \leftrightarrow \lambda^c\mathcal{Y}_{BC} = \lambda^c(\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC}), \lambda \neq 0.$

4. If $\mathcal{Y}_{AB} \times B \subseteq \mathcal{Y}_{BC} \times B$, $\mathcal{Y}_{AB} \circ B \subseteq \mathcal{Y}_{BC} \circ B$, then $0^b\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC} = 0^c(\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC}) = \mathcal{Y}_{AB} \leftrightarrow 0^c\mathcal{Y}_{BC}.$

5. $(\lambda^b\mathcal{Y}_{AB})^T = \lambda^a\mathcal{Y}_{AB}^T.$

*Proof.* 1. When $\mathcal{Y}_{AB}^1 \circ A = \mathcal{Y}_{AB}^2 \circ A$, $\mathcal{Y}_{AB}^1 \times B = \mathcal{Y}_{AB}^2 \times B$, we have $\mathcal{Y}_{AB}^1 \circ A = \mathcal{Y}_{AB}^2 \circ A = (\mathcal{Y}_{AB}^1 +_b \mathcal{Y}_{AB}^2) \circ A = (\mathcal{Y}_{AB}^3 +_b (-1)^b \mathcal{Y}_{AB}^2) \circ A$, $\mathcal{Y}_{AB}^1 \times B = \mathcal{Y}_{AB}^2 \times B = (\mathcal{Y}_{AB}^1 +_b \mathcal{Y}_{AB}^2) \times B = (\mathcal{Y}_{AB}^3 +_b (-1)^b \mathcal{Y}_{AB}^2) \times B$. The result now follows from the definition of ‘+_b’ operation.

(Note however that in general

$$ (\mathcal{Y}_{AB}^3 +_b (-1)^b \mathcal{Y}_{AB}^2) \circ A = \mathcal{Y}_{AB}^3 \circ A \cap \mathcal{Y}_{AB}^2 \circ A \text{ which may not equal } \mathcal{Y}_{AB}^1 \circ A, $$

$$ (\mathcal{Y}_{AB}^3 +_b (-1)^b \mathcal{Y}_{AB}^2) \times B = \mathcal{Y}_{AB}^3 \times B + \mathcal{Y}_{AB}^2 \times B \text{ which may not equal } \mathcal{Y}_{AB}^1 \times B.) $$

2. is routine when $\lambda_1, \lambda_2, \lambda_1 + \lambda_2$ are all not equal to zero.

Suppose $\lambda_1 = 0$. Then the LHS is $\lambda_2^b\mathcal{Y}_{AB} + \mathcal{Y}_{AB} \times B = \lambda_2^b\mathcal{Y}_{AB}$ equal to RHS.

Suppose $\lambda_1 + \lambda_2 = 0$. Then the LHS is $\lambda_1^b\mathcal{Y}_{AB} +_b (-\lambda_1^b)\mathcal{Y}_{AB}$. By definition of the ‘+_b’ operation this is equal to $\mathcal{Y}_{AB} \circ A \oplus \mathcal{Y}_{AB} \times B$ which is equal to the RHS.

3. is routine.

4. If $\mathcal{Y}_{AB} \times B \subseteq \mathcal{Y}_{BC} \times B$, we must have $0^b\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC} = (\mathcal{Y}_{AB} \circ A \oplus \mathcal{Y}_{AB} \times B) \leftrightarrow \mathcal{Y}_{BC} = (\mathcal{Y}_{AB} \circ A) \oplus (\mathcal{Y}_{AB} \times B \leftrightarrow \mathcal{Y}_{BC}) = \mathcal{Y}_{AB} \circ A \oplus \mathcal{Y}_{BC} \times C$.

Similarly, if $\mathcal{Y}_{AB} \circ B \subseteq \mathcal{Y}_{BC} \circ B$, $\mathcal{Y}_{AB} \leftrightarrow 0^c\mathcal{Y}_{BC} = \mathcal{Y}_{AB} \leftrightarrow (\mathcal{Y}_{BC} \circ B \oplus \mathcal{Y}_{BC} \times C) = \mathcal{Y}_{AB} \circ A \oplus \mathcal{Y}_{BC} \times C$.

Next, if $\mathcal{Y}_{AB} \times B \subseteq \mathcal{Y}_{BC} \times B$, we have $(\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC}) \times C = \mathcal{Y}_{BC} \times C$, and if $\mathcal{Y}_{AB} \circ B \subseteq \mathcal{Y}_{BC} \circ B$, then $(\mathcal{Y}_{AB} \leftrightarrow \mathcal{Y}_{BC}) \circ A = \mathcal{Y}_{AB} \circ A$. The result follows.

5. Let $\lambda = 0$. The LHS reduces to $(\mathcal{Y}_{AB} \circ A \oplus \mathcal{Y}_{AB} \times B)^T = (\mathcal{V}_{AB}^T \times A \oplus \mathcal{V}_{AB}^T \circ B)$, which is the RHS by definition of $\lambda^a\mathcal{Y}_{AB}^T$.

Next, let $\lambda \neq 0$. We have $\lambda^b\mathcal{Y}_{AB} \equiv \mathcal{Y}_{A(\lambda b)} = (\mathcal{Y}_{AB} \leftrightarrow \{[I_B \ \lambda I_{B'}]\})_{AB}$.

We have by Theorem 10, $(\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ})^T = \mathcal{Y}_{SP}^T \leftrightarrow \mathcal{Y}_{PQ}^T$. Therefore,

$$ (\lambda^b \mathcal{Y}_{AB})^T = ((\mathcal{Y}_{AB} \leftrightarrow \{[I_B \ \lambda I_{B'}]\})_{AB})^T = (\mathcal{V}_{AB}^T \leftrightarrow \{[I_B \ \lambda I_{B'}]\})^T_{AB} \\ = (\mathcal{V}_{AB}^T \leftrightarrow \{[\lambda I_B \ I_{B'}]\})_{AB} = \lambda^a \mathcal{Y}_{AB}^T, $$

where we have made use of the fact that $\{[I_B \ \lambda I_{B'}]\}^T = \{[\lambda I_B \ I_{B'}]\}$.

□

### 5.7. Distributivity of composition of linkages over intersection-sums

**Problem 11.** The matched composition operation acts similar to the operation of product of maps, but under some relaxations. For ordinary maps we have the distributivity of addition over composition and scalar multiplication. Because of this fact we are able to develop the rich spectral theory of operators. Prove the following result which states the conditions for distributivity of ‘$\leftrightarrow$’ over intersection-sum to hold. This proves adequate for developing a spectral theory of the subclass of linkages which are ‘generalized operators’ (see Section 14 of the present paper, also [14]).

**Theorem 18.** Let $\mathcal{Y}_{AB}, \mathcal{Y}_{AB}^T, \mathcal{Y}_{BC}$, be linkages, A, B, C, being pairwise disjoint.

1. If $\mathcal{Y}_{BC} \times B \subseteq \mathcal{Y}_{AB} \times B$, then

$$ \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_a \mathcal{Y}_{AB}) = (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_a (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^T). $$

2. If $\mathcal{Y}_{BC} \times B \subseteq \mathcal{Y}_{AB}^1 \times B, \dots, \mathcal{Y}_{BC} \times B \subseteq \mathcal{Y}_{AB}^{k-1} \times B$, then

$$ \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB}^1 +_a \dots +_a \mathcal{Y}_{AB}^k) = (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^1) +_a \dots +_a (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^k). $$

3. Dually, if $\mathcal{Y}_{BC} \circ B \supseteq \mathcal{Y}_{AB} \circ B$, then

$$ \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_b \mathcal{Y}_{AB}^T) = (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_c (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^T). $$
4. If $\mathcal{Y}_{BC} \circ B \supseteq \mathcal{Y}_{AB}^1 \circ B, \dots, \mathcal{Y}_{BC} \circ B \supseteq \mathcal{Y}_{AB}^{k-1} \circ B$, then $\mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB}^1 +_b \dots +_b \mathcal{Y}_{AB}^k) = (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^1) +_c \dots +_c (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}^k)$.

The corresponding result for scalar multiplication is straight forward and we state it but skip its proof.

**Theorem 19.**

$$ \lambda^b(\mathcal{Y}_{AB} +_b \mathcal{Y}_{AB}) = (\lambda^b \mathcal{Y}_{AB}) +_b (\lambda^b \mathcal{Y}_{AB}), $$

Answer

*Proof.* 1. Let $(f_A, h_C) \in \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_a \mathcal{Y}_{AB})$. Then there exist vectors

$$ (g_B, h_C) \in \mathcal{Y}_{BC}, (f_A^1, g_B) \in \mathcal{Y}_{AB}, (f_A^2, g_B) \in \mathcal{Y}_{AB}, \text{ such that } f_A = f_A^1 + f_A^2. $$

This means $(f_A^1, h_C) \in (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB})$ and $(f_A^2, h_C) \in (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB})$ and therefore

$$ (f_A, h_C) \in (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_a (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}). $$

Next, let $(f_A, h_C) \in (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_a (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB})$. This means there exist vectors

$$ (f_A^1, h_C), (f_A^2, h_C) \in (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}), (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) \text{ with } f_A = f_A^1 + f_A^2. $$

Therefore there exist vectors $(f_A^1, f_B^1)$, $(f_B^1, h_C) \in \mathcal{Y}_{AB}, \mathcal{Y}_{BC}$ respectively and vectors $(f_A^2, f_B^2)$, $(f_B^2, h_C) \in \mathcal{Y}_{AB}, \mathcal{Y}_{BC}$, respectively.

Therefore $(f_B^1 - f_B^2, 0_C) \in \mathcal{Y}_{BC}$, i.e., $f_B^1 - f_B^2 \in \mathcal{Y}_{BC} \times B \subseteq \mathcal{Y}_{AB} \times B$.

Hence, $(0_A, f_B^1 - f_B^2) \in \mathcal{Y}_{AB}$. Now $(f_A^1, f_B^1) \in \mathcal{Y}_{AB}$. Therefore $(f_A^1, f_B^2) \in \mathcal{Y}_{AB}$.

We already have that $(f_A^2, f_B^2) \in \mathcal{Y}_{AB}$.

Hence

$$ (f_A^1 + f_A^2, f_B^2) = (f_A, f_B^2) \in (\mathcal{Y}_{AB} +_a \mathcal{Y}_{AB}). $$

We know that $(f_B^2, h_C) \in \mathcal{Y}_{BC}$. Therefore

$$ (f_A, h_C) \in \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_a \mathcal{Y}_{AB}). $$

2. The proof is by induction on the number of terms within the bracket on the left hand side.

3. By the first part of the theorem we have if $\mathcal{Y}_{BC}^T \times B \subseteq \mathcal{Y}_{AB}^T \times B$, then

$$ \mathcal{Y}_{BC}^T \leftrightarrow (\mathcal{Y}_{AB}^T +_a \mathcal{Y}_{AB}^T) = (\mathcal{Y}_{BC}^T \leftrightarrow \mathcal{Y}_{AB}^T) +_a (\mathcal{Y}_{BC}^T \leftrightarrow \mathcal{Y}_{AB}^T). $$

Hence, if $(\mathcal{Y}_{BC}^T \times B)^T \supseteq (\mathcal{Y}_{AB}^T \times B)^T$, then

$$ (\mathcal{Y}_{BC}^T \leftrightarrow (\mathcal{Y}_{AB}^T +_a \mathcal{Y}_{AB}^T))^T = ((\mathcal{Y}_{BC}^T \leftrightarrow \mathcal{Y}_{AB}^T) +_a (\mathcal{Y}_{BC}^T \leftrightarrow \mathcal{Y}_{AB}^T))^T, $$

i.e., if $\mathcal{Y}_{BC}^{TT} \circ B \supseteq \mathcal{Y}_{AB}^{TT} \circ B$, then

$$ \mathcal{Y}_{BC}^{TT} \leftrightarrow (\mathcal{Y}_{AB}^{TT} +_b \mathcal{Y}_{AB}^{TT}) = (\mathcal{Y}_{BC}^{TT} \leftrightarrow \mathcal{Y}_{AB}^{TT}) +_c (\mathcal{Y}_{BC}^{TT} \leftrightarrow \mathcal{Y}_{AB}^{TT}), $$

i.e., if $\mathcal{Y}_{BC} \circ B \supseteq \mathcal{Y}_{AB} \circ B$, then

$$ \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_b \mathcal{Y}_{AB}) = (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_c (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}). $$

4. The proof is by induction on the number of terms within the bracket on the left hand side. $\square$

**Remark 4.** To see that the statement of the theorem fails without the ‘dot-cross’ conditions, take $\mathcal{Y}_{BC}$ to be spanned by $(g_B^1, f_C)$, $(g_B^2, f_C)$, $\mathcal{Y}_{AB}$ to be spanned by $(h_A^1, g_B^1)$, $\mathcal{Y}_{AB}$ to be spanned by $(h_A^2, g_B^2)$, and take $g_B^1, g_B^2$, independent of each other, $h_A^1 + h_A^2 \neq 0_A$.

It can be seen that in this case

$$ \mathcal{Y}_{BC} \leftrightarrow (\mathcal{Y}_{AB} +_b \mathcal{Y}_{AB}) \neq (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}) +_a (\mathcal{Y}_{BC} \leftrightarrow \mathcal{Y}_{AB}). $$
# 6. Computing the basic operations

## 6.1. Representation of vector spaces

A vector space $\mathcal{V}_A$ may be specified explicitly in one of the two following ways:

1. Through generator set for $\mathcal{V}_A$:

$$f_A^T = \lambda^T [R_A],$$

where the rows of $R_A$ generate $\mathcal{V}_A$ by linear combination. When the rows of $R_A$ are linearly independent $R_A$ is called a **representative matrix** of $\mathcal{V}_A$.

2. Through constraint equations:

$$[S_A] f_A = 0,$$

where the rows of $S_A$ generate $\mathcal{V}_A^\perp$. The solution space of this equation is $(\mathcal{V}_A^\perp)^\perp = \mathcal{V}_A$.

One or the other of the representations above, might be convenient depending upon the context. In what follows, the operations have been described in terms of constraint equations.

A vector space $\mathcal{V}_A := \mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$, may be specified implicitly through constraint equations for $\mathcal{V}_{AB}, \mathcal{V}_B$. This is described in Subsection 6.5.

**Problem 12.** Show how to compute the basic operations on vector spaces, namely restriction, contraction, intersection, sum, generalized minor explicitly. Assuming that the vector spaces are given implicitly as generalized minor of other spaces, show how to compute intersection and sum implicitly.

Answer

The answer is given in the following subsections.

## 6.2. Computing $\mathcal{V}_{AB} \circ A$ and $\mathcal{V}_{AB} \times B$ explicitly

Let $\mathcal{V}_{AB}$ be defined through

$$[S_A \quad S_B] \begin{pmatrix} f_A \\ f_B \end{pmatrix} = 0.$$

We do row operations so that the coefficient matrix is in the form

$$\begin{bmatrix} S_{1A} & 0 \\ S_{2A} & S_{2B} \end{bmatrix},$$

where the rows of $S_{2B}$ are linearly independent (or, if more convenient, columns of $S_{2A}$ are dependent on columns of $S_{2B}$). Then $[S_{1A}]f_A = 0$ defines $\mathcal{V}_{AB} \circ A$ and $[S_{2B}]f_B = 0$ defines $\mathcal{V}_{AB} \times B$. The statement about $\mathcal{V}_{AB} \circ A$ may be seen as follows: Clearly if any $(f_A, f_B) \in \mathcal{V}_{AB}$, then $f_A$ satisfies $[S_{1A}]f_A = 0$ so that $\mathcal{V}_{AB} \circ A$ is contained in the solution space of the latter. Next, let $f_A$ satisfy $[S_{1A}]f_A = 0$. If rows of $S_{2B}$ are linearly independent or if columns of $S_{2A}$ are linearly dependent on columns of $S_{2B}$, the equation

$$[S_{2B}] f_B = - [S_{2A}] f_A$$

has a solution $\hat{f}_B$. Thus for any solution of $[S_{1A}]f_A = 0$, we can always find $\hat{f}_B$ such that $(f_A, \hat{f}_B) \in \mathcal{V}_{AB}$. This completes the proof that $\mathcal{V}_{AB} \circ A$ is the solution space of $[S_{1A}]f_A = 0$.

The statement about $\mathcal{V}_{AB} \times B$ is routine.
### 6.3. Computing $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$ Explicitly

Suppose $[S_A^1]f_A = 0$, $[S_A^2]f_A = 0$ define $\mathcal{V}_A^1, \mathcal{V}_A^2$ respectively. Let $A', A''$ be copies of $A$ with $A, A', A''$ disjoint. Build the space $\mathcal{V}_{AA'A''}$ defined through

$$ \begin{bmatrix} S_A^1 & 0 & 0 \\ 0 & S_A^2 & 0 \\ 0 & I & -I \\ I & 0 & -I \end{bmatrix} \begin{pmatrix} f_{A'}^1 \\ f_{A''}^2 \\ f_A \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \qquad (10) $$

It is clear that the vectors $f_A$ are precisely those in both $\mathcal{V}_A^1$ and $\mathcal{V}_A^2$. Thus $\mathcal{V}_{AA'A''} \circ A$ is $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$. The explicit construction of the dot operation has been discussed above.

### 6.4. Computing $\mathcal{V}_A^1 + \mathcal{V}_A^2$ Explicitly

Let $\mathcal{V}_A^1$ and $\mathcal{V}_A^2$ be defined as above. We define $\hat{\mathcal{V}}_{AA'A''}$ through

$$ \begin{bmatrix} S_A^1 & 0 & 0 \\ 0 & S_A^2 & 0 \\ -I & -I & I \end{bmatrix} \begin{pmatrix} f_{A'}^1 \\ f_{A''}^2 \\ f_A \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}. \qquad (11) $$

In this case again it is easy to see that $\hat{\mathcal{V}}_{AA'A''} \circ A = \mathcal{V}_A^1 + \mathcal{V}_A^2$ and we complete the explicit construction as above.

Often the spaces $\mathcal{V}_A^1, \mathcal{V}_A^2$ may themselves be available to us only implicitly — usually in the form of a generalized minor $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$. We discuss this situation below after we discuss the computation of the generalized minor.

### 6.5. Computing $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$ Implicitly

Let $\mathcal{V}_{AB}$ be defined by

$$ [S_A \quad S_B] \begin{pmatrix} f_A \\ f_B \end{pmatrix} = 0 $$

and $\mathcal{V}_B$ by

$$ [\hat{S}_B] f_B = 0. $$

Let $\hat{\mathcal{V}}_{AB}$ be defined by

$$ \begin{bmatrix} S_A & S_B \\ 0 & \hat{S}_B \end{bmatrix} \begin{pmatrix} f_A \\ f_B \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (12) $$

Then

$$ \begin{aligned} \hat{\mathcal{V}}_{AB} \circ A &\equiv \{f_A \mid (f_A, f_B) \in \mathcal{V}_{AB}, f_B \in \mathcal{V}_B\} \\ &= \mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B. \end{aligned} $$

### 6.6. Computing $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$ Explicitly

In order to explicitly represent $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$ as the solution space of an equation

$$ [\tilde{S}_A] f_A = 0, \qquad (13) $$
one has to do row operations and recast (12) as

$$ \begin{bmatrix} S'_{1A} & S'_{1B} \\ S'_{2A} & 0 \\ 0 & \hat{S}_B \end{bmatrix} \begin{pmatrix} f_A \\ f_B \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \qquad (14) $$

where the rows of $S'_{1B}$ together with those of $\hat{S}_B$ are independent. The solution space of

$$ [S'_{2A}] f_A = 0, $$

is clearly $\mathcal{V}_{AB} \circ A$ ($\mathcal{V}_{AB}$ as in Equation 12) that is, $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$.

In general when one is performing operations such as intersection or sum with vector spaces, their representation may not be explicitly available but in the form $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$.

Let $\hat{f}_B \in (\mathcal{V}_{AB} \cap \mathcal{V}_B) \circ B$. To find $\mathcal{V}_{AB} \leftrightarrow \{\hat{f}_B\}$ we first find one solution $\hat{f}_A$ to the equation using the first rows of (14)

$$ \begin{bmatrix} S'_{1A} \\ S'_{2A} \end{bmatrix} \hat{f}_A = \begin{bmatrix} S'_{1B} \hat{f}_B \\ 0 \end{bmatrix}. $$

Then

$$ \mathcal{V}_{AB} \leftrightarrow \{\hat{f}_B\} = \hat{f}_A + \mathcal{V}_{AB} \times A. $$

$\mathcal{V}_{AB} \times A$ can be seen to be the solution to

$$ \begin{bmatrix} S'_{1A} \\ S'_{2A} \end{bmatrix} \tilde{f}_A = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$

and $\mathcal{V}_{AB} \leftrightarrow \{\hat{f}_B\}$ as the collection of all solutions to

$$ \begin{bmatrix} S'_{1A} \\ S'_{2A} \end{bmatrix} f_A = \begin{bmatrix} S'_{1B} \hat{f}_B \\ 0 \end{bmatrix}. $$

### 6.7. Computing $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$ Implicitly

Suppose $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$ is to be computed where

$$ \mathcal{V}_A^1 = \mathcal{V}_{AB}^1 \leftrightarrow \mathcal{V}_B^1 $$

$$ \mathcal{V}_A^2 = \mathcal{V}_{AB}^2 \leftrightarrow \mathcal{V}_B^2. $$

Let $\mathcal{V}_{AB}^1, \mathcal{V}_{AB}^2$ be defined respectively through

$$ [S_A^1 \quad S_B^1] \begin{pmatrix} f_A^1 \\ f_B^1 \end{pmatrix} = 0, $$

$$ [S_A^2 \quad S_B^2] \begin{pmatrix} f_A^2 \\ f_B^2 \end{pmatrix} = 0. $$

Let $\mathcal{V}_B^1, \mathcal{V}_B^2$ be defined respectively through

$$ [\hat{S}_B^1] f_B = 0, $$

$$ [\hat{S}_B^2] f_B = 0. $$
We proceed now as in (10) by first copying set A into A', A'' and B into B', B'' and write the final equations as

$$ \begin{bmatrix} S_A^1 & S_B^1 & 0 & 0 & 0 \\ 0 & \hat{S}_B^1 & 0 & 0 & 0 \\ 0 & 0 & S_A^2 & S_B^2 & 0 \\ 0 & 0 & 0 & \hat{S}_B^2 & 0 \\ 0 & 0 & +I & 0 & -I \\ I & 0 & 0 & 0 & -I \end{bmatrix} \begin{pmatrix} f_{A'}^1 \\ f_{B'}^1 \\ f_{A''}^2 \\ f_{B''}^2 \\ f_A \end{pmatrix} = 0 \quad (15) $$

If the above equation has the solution space $\mathcal{V}_{AA'A''B'B''}$ then we can show that

$$ \mathcal{V}_{AA'A''B'B''} \circ A = \mathcal{V}_A^1 \cap \mathcal{V}_A^2. $$

To see this, note that $\mathcal{V}_A^1$ is the collection of all $f_{A'}^1$, which can be part of a solution vector $(f_{A'}^1, f_{B'}^1)$ of the first two rows of (15). $\mathcal{V}_A^2$ is the space of all vectors $f_{A''}^2$ which can be a part of the solution vector $(f_{A''}^2, f_{B''}^2)$ of the next two rows of (15). Now $f_A$, by the last two rows of the equation, is seen to a copy of both $f_{A'}^1$ as well as $f_{A''}^2$. Any such vector therefore belongs to $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$. Conversely any vector in $\mathcal{V}_A^1 \cap \mathcal{V}_A^2$ can clearly be a copy of a part of some solution vector of the first two rows and therefore of the middle two rows also — which means it is a part of a solution vector of (15).

### 6.8. Computing $\mathcal{V}_A^1 + \mathcal{V}_A^2$ Implicitly

By similar arguments, we can show that we can write the constraints for $\mathcal{V}_A^1 + \mathcal{V}_A^2$ as an implicit version (11) as follows:

$$ \begin{bmatrix} S_A^1 & S_B^1 & 0 & 0 & 0 \\ 0 & \hat{S}_B^1 & 0 & 0 & 0 \\ 0 & 0 & S_A^2 & S_B^2 & 0 \\ 0 & 0 & 0 & \hat{S}_B^2 & 0 \\ -I & 0 & -I & 0 & I \end{bmatrix} \begin{pmatrix} f_{A'}^1 \\ f_{B'}^1 \\ f_{A''}^2 \\ f_{B''}^2 \\ f_A \end{pmatrix} = 0 \quad (16) $$

If $\tilde{\mathcal{V}}_{AA'A''B'B''}$ is the solution space of the above equation then

$$ \mathcal{V}_A^1 + \mathcal{V}_A^2 = \tilde{\mathcal{V}}_{AA'A''B'B''} \circ A. $$

## 7. Multiports and multiport decomposition of electrical networks

\* (This section uses IIT, IDT (Theorems 1,2), Theorem 6 and the definitions of electrical network and multiport from Section 2.)

### 7.1. Implicit inversion for affine spaces and electrical multiports

**Problem 13.** Apply implicit inversion for affine spaces (Theorem 6) to electrical multiports with affine device-characteristic.

**Answer**

We have the following corollary of Theorem 6 for electrical multiports.

**Theorem 20.** Let $\mathcal{N}_P^1, \mathcal{N}_P^2$ be multiports on the same graph $\mathcal{G}_{EP}$ but with device-characteristics $\mathcal{A}_{EE'}$, $\mathcal{V}_{EE'}$, respectively where $\mathcal{V}_{EE'}$, is the vector space translate of the affine space $\mathcal{A}_{EE'}$, and with port behaviours $\mathcal{A}_{PP'} := [(\mathcal{V}^v(\mathcal{G}_{EP}))_{EP} \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P}] \leftrightarrow \mathcal{A}_{EE'}$, $\mathcal{V}_{PP'} := [(\mathcal{V}^v(\mathcal{G}_{EP}))_{EP} \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P}] \leftrightarrow \mathcal{V}_{EE'}$, respectively. If $\mathcal{A}_{PP'} \neq \emptyset$, then $\mathcal{V}_{PP'} = [(\mathcal{V}^v(\mathcal{G}_{EP}))_{EP} \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P}] \leftrightarrow \mathcal{V}_{EE'}$, is the vector space translate of $\mathcal{A}_{PP'}$.

**Remark 5.** In order to be consistent with electrical network theory literature, in Subsection 9.3, we define port behaviour to be $\tilde{\mathcal{A}}_{PP'} := (\mathcal{A}_{PP'})(-P')P$ (see Definition 30). But we use this definition only for problems in Subsection 9.3, Section 10 and Section 11. For general ideas related to multiport decomposition, this change of sign of the current variable corresponding to $P'$ is unnecessary.
### 7.2. Internal model relative to ports

**Definition 21.** Let $\mathcal{H}_S$ be a collection of real vectors on $S$ and let $\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_S = \mathcal{H}_P$. The internal model of $(\mathcal{V}_{SP}, \mathcal{H}_S)$ relative to $P$ is defined to be $\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P$.

**Problem 14.** (a) Prove the following result about internal models.

**Lemma 22.** 1. Let $\mathcal{V}_{SP}$ be a vector space on $S \uplus P$ and $\mathcal{H}_S$ be an arbitrary collection of vectors on $S$. Let $\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_S = \mathcal{H}_P$. Then $\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P = (\mathcal{H}_S + \mathcal{V}_{SP} \times S) \cap \mathcal{V}_{SP} \circ S = (\mathcal{H}_S \cap \mathcal{V}_{SP} \circ S) + \mathcal{V}_{SP} \times S$.

2. Let $\mathcal{V}_{EPE'P'} := \mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}$, $E, P, E', P'$ being mutually disjoint and let $\mathcal{H}_{PP'} = \mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{H}_{EE'}$. Then $\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{H}_{PP'} = [\mathcal{H}_{EE'} \cap (\mathcal{V}^v(\mathcal{G}_{EP} \circ E) \oplus (\mathcal{V}^i(\mathcal{G}_{EP} \times E))_{E'})] + [\mathcal{V}^v(\mathcal{G}_{EP} \times E) \oplus (\mathcal{V}^i(\mathcal{G}_{EP} \circ E))_{E'}]$.

(b) Define 'internal model' of a multiport $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$ consistent with Definition 21.

**Answer**

(a) We need the following result, which is used to prove Theorem 1 in [19].

**Lemma 23.** 1. Let $\mathcal{H}_{SP}, \mathcal{H}_{SQ}$ be zero-member collections of vectors on $S \uplus P, S \uplus Q$ respectively. Then there exists a zero-member collection of vectors $\mathcal{H}_{PQ}$ on $P \uplus Q$ s.t. $\mathcal{H}_{SP} \leftrightarrow \mathcal{H}_{PQ} = \mathcal{H}_{SQ}$, only if $\mathcal{H}_{SP} \circ S \supseteq \mathcal{H}_{SQ} \circ S$ and $\mathcal{H}_{SP} \times S \subseteq \mathcal{H}_{SQ} \times S$.

2. Let $\mathcal{H}_{SP}$ be a zero-member collection of vectors closed under subtraction on $S \uplus P$ and let $\mathcal{H}_{SQ}$ be a zero-member collection of vectors on $S \uplus Q$, closed under addition. Then the collection of vectors $\mathcal{H}_{SP} \leftrightarrow \mathcal{H}_{SQ}$, is closed under addition, with $0_{PQ}$ as a member

Further, let $\mathcal{H}_{SP} \times S \subseteq \mathcal{H}_{SQ} \times S$ and $\mathcal{H}_{SP} \circ S \supseteq \mathcal{H}_{SQ} \circ S$. Then $\mathcal{H}_{SP} \leftrightarrow (\mathcal{H}_{SP} \leftrightarrow \mathcal{H}_{SQ}) = \mathcal{H}_{SQ}$.

*Proof.* (of Lemma 22) 1. By Lemma 23 above, it is clear that $\mathcal{V}_{SP} \circ S \supseteq \mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P \supseteq \mathcal{V}_{SP} \times S$. The result follows.

2. This is immediate from part 1 above, replacing $\mathcal{V}_{SP}$ by $\mathcal{V}_{EPE'P'}$, $\mathcal{H}_S, \mathcal{H}_P$, respectively by $\mathcal{H}_{EE'}$, $\mathcal{H}_{PP'}$ and noting that $((\mathcal{V}^v(\mathcal{G}_{EP}) \circ E)_E \oplus (\mathcal{V}^i(\mathcal{G}_{EP}) \circ E)_{E'}) = ((\mathcal{V}^v(\mathcal{G}_{EP} \circ E)_E \oplus (\mathcal{V}^i(\mathcal{G}_{EP} \times E)_{E'})), ((\mathcal{V}^v(\mathcal{G}_{EP}) \times E)_E \oplus (\mathcal{V}^i(\mathcal{G}_{EP}) \times E)_{E'}) = ((\mathcal{V}^v(\mathcal{G}_{EP} \times E)_E \oplus (\mathcal{V}^i(\mathcal{G}_{EP} \circ E)_{E'}))$. $\square$

(b) The internal model of a multiport $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$, relative to $P$ is $[\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^v(\mathcal{G}_{EP})_{E'P'})] \leftrightarrow \mathcal{H}_{PP'}, \text{where } \mathcal{H}_{PP'} := [\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^v(\mathcal{G}_{EP})_{E'P'})] \leftrightarrow \mathcal{H}_{EE'}, \text{and } \mathcal{H}_{EE'} = \mathcal{D}_E$.

### 7.3. Port transformation

**Definition 24.** Vector spaces $\mathcal{V}_{SP}, \mathcal{V}_{SQ}$ are *port transformations* of each other with respect to $S$, iff $\mathcal{V}_{SP} \times S = \mathcal{V}_{SQ} \times S$ and $\mathcal{V}_{SP} \circ S = \mathcal{V}_{SQ} \circ S$.

**Problem 15.** Justify the definition of port transformation (Definition 24) and prove the following.

**Lemma 25.** Let $S, P, Q$, be pairwise disjoint. The spaces $\mathcal{V}_{SP}, \mathcal{V}_{SQ}$ are port transformations of each other with respect to $S$, iff there exists $\mathcal{V}_{PQ}$ such that $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} = \mathcal{V}_{SQ}$ and such that $\mathcal{V}_{SP} \circ P = \mathcal{V}_{PQ} \circ P, \mathcal{V}_{SP} \times P = \mathcal{V}_{PQ} \times P$.

**Answer**

By Lemma 22, we know that when $\mathcal{H}_P := \mathcal{V}_{SP} \leftrightarrow \mathcal{H}_S$, we have $\mathcal{V}_{SP} \leftrightarrow \mathcal{H}_P = (\mathcal{H}_S + \mathcal{V}_{SP} \times S) \cap \mathcal{V}_{SP} \circ S = (\mathcal{H}_S \cap \mathcal{V}_{SP} \circ S) + \mathcal{V}_{SP} \times S$ and when $\mathcal{H}_Q := \mathcal{V}_{SQ} \leftrightarrow \mathcal{H}_S$, we have $\mathcal{V}_{SQ} \leftrightarrow \mathcal{H}_Q = (\mathcal{H}_S + \mathcal{V}_{SQ} \times S) \cap \mathcal{V}_{SQ} \circ S = (\mathcal{H}_S \cap \mathcal{V}_{SQ} \circ S) + \mathcal{V}_{SQ} \times S$. It follows that $\mathcal{H}_P, \mathcal{H}_Q$, correspond to the same internal model iff $\mathcal{V}_{SP} \times S = \mathcal{V}_{SQ} \times S$ and $\mathcal{V}_{SP} \circ S = \mathcal{V}_{SQ} \circ S$. Therefore $\mathcal{V}_{SP}, \mathcal{V}_{SQ}$ could be regarded as port transformations of each other with respect to $S$.
**Proof.** (Proof of Lemma 25)

(if) By Theorem 3, we have that $\mathcal{V}_{AB} \leftrightarrow (\mathcal{V}_{BC} \leftrightarrow \mathcal{V}_C) = (\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_{BC}) \leftrightarrow \mathcal{V}_C$, when A, B, C, are pairwise disjoint. It is also easy to see that $\mathcal{V}_{AB} \leftrightarrow (\mathcal{V}_{AB} \times B) = \mathcal{V}_{AB} \times A$ and $\mathcal{V}_{AB} \leftrightarrow (\mathcal{V}_{AB} \circ B) = \mathcal{V}_{AB} \circ A$.
Therefore, $\mathcal{V}_{SQ} \times S \equiv \mathcal{V}_{SQ} \leftrightarrow \mathbf{0}_Q = (\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ}) \leftrightarrow \mathbf{0}_Q = \mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_{PQ} \leftrightarrow \mathbf{0}_Q) = \mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_{PQ} \times P) = \mathcal{V}_{SP} \leftrightarrow (\mathcal{V}_{SP} \times P) = \mathcal{V}_{SP} \times S$.

By replacing $\mathbf{0}_Q$ in the above argument by $\mathcal{F}_Q$, we see that $\mathcal{V}_{SQ} \circ S = \mathcal{V}_{SP} \circ S$.

(only if) We define $\mathcal{V}_{PQ} \equiv \mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{SQ}$. Since $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{SQ} = \mathcal{V}_{PQ}$ and $\mathcal{V}_{SP} \times S = \mathcal{V}_{SQ} \times S$, $\mathcal{V}_{SP} \circ S = \mathcal{V}_{SQ} \circ S$, by Theorem 6, we have $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{PQ} = \mathcal{V}_{SQ}$. Next, starting from $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_{SQ} = \mathcal{V}_{PQ}$, by using the argument of the previous part, but interchanging the roles of S, P and $\mathcal{V}_{PQ}$, $\mathcal{V}_{SQ}$, we get
$$ \mathcal{V}_{SP} \circ P = \mathcal{V}_{PQ} \circ P, \mathcal{V}_{SP} \times P = \mathcal{V}_{PQ} \times P. \quad \square $$

**Problem 16.** Show that the definition of 'port transformation' of a multiport $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$ consistent with Definition 24 is

'$\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$, $\mathcal{N}_Q := (\mathcal{G}_{EQ}, \mathcal{D}_E)$, are port transformations of each other iff
$\mathcal{G}_{EP} \circ E = \mathcal{G}_{EQ} \circ E, \mathcal{G}_{EP} \times E = \mathcal{G}_{EQ} \times E$.'

**Answer**

Let $\mathcal{N}_Q := (\mathcal{G}_{EQ}, \mathcal{D}_E)$. In order to be consistent with Definition 24, we should define $\mathcal{N}_Q$ to be a port transformation of $\mathcal{N}_P$ iff $[\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}] \circ EE' = [\mathcal{V}^v(\mathcal{G}_{EQ}) \oplus (\mathcal{V}^i(\mathcal{G}_{EQ}))_{E'Q'}] \circ EE'$, and $[\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}] \times EE' = [\mathcal{V}^v(\mathcal{G}_{EQ}) \oplus (\mathcal{V}^i(\mathcal{G}_{EQ}))_{E'Q'}] \times EE'$. Since $\mathcal{V}^v(\mathcal{G}_{EP}) \times E = \mathcal{V}^v(\mathcal{G}_{EP} \times E)$, $\mathcal{V}^v(\mathcal{G}_{EP}) \circ E = \mathcal{V}^v(\mathcal{G}_{EP} \circ E)$, $\mathcal{V}^i(\mathcal{G}_{EP}) \times E = \mathcal{V}^i(\mathcal{G}_{EP} \circ E)$, $\mathcal{V}^i(\mathcal{G}_{EP}) \circ E = \mathcal{V}^i(\mathcal{G}_{EP} \times E)$, the port transformation condition reduces to '$\mathcal{N}_P, \mathcal{N}_Q$ are port transformations of each other iff $\mathcal{G}_{EP} \circ E = \mathcal{G}_{EQ} \circ E, \mathcal{G}_{EP} \times E = \mathcal{G}_{EQ} \times E$.'

### 7.4. Graph algorithms for port minimization and minimal multiport decomposition

*(This subsection is based on material from the subsection on multiports in [19].)

**Problem 17.** Given a multiport $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{D}_E)$ construct a port transformation $\mathcal{N}_{\tilde{P}} := (\mathcal{G}_{E\tilde{P}}, \mathcal{D}_E)$ through a linear time graph based algorithm such that $|\tilde{P}|$ is the minimum possible. Justify the algorithm.

**Answer**

We note that $|P| \ge r(\mathcal{G}_{EP} \circ P) - r(\mathcal{G}_{EP} \times P) = r(\mathcal{G}_{EP} \circ E) - r(\mathcal{G}_{EP} \times E)$. Therefore, if the size of the set of ports equals $r(\mathcal{G}_{EP} \circ E) - r(\mathcal{G}_{EP} \times E)$, the port set would be minimal.

We give an algorithm for building a graph $\mathcal{G}_{E\tilde{P}}$ such that $\mathcal{V}^v(\mathcal{G}_{EP}) \circ E = \mathcal{V}^v(\mathcal{G}_{E\tilde{P}}) \circ E$, $\mathcal{V}^v(\mathcal{G}_{EP}) \times E = \mathcal{V}^v(\mathcal{G}_{E\tilde{P}}) \times E$ and such that $|\tilde{P}|$ is the minimum possible.

**Algorithm**

Input: A graph $\mathcal{G}_{EP}$ on edge set $E \uplus P$.

Output: A graph $\mathcal{G}_{E\tilde{P}}$ on edge set $E \uplus \tilde{P}$, such that

$$ \mathcal{V}^v(\mathcal{G}_{E\tilde{P}}) \times E = \mathcal{V}^v(\mathcal{G}_{EP}) \times E, \mathcal{V}^v(\mathcal{G}_{E\tilde{P}}) \circ E = \mathcal{V}^v(\mathcal{G}_{EP}) \circ E, |\tilde{P}| = r(\mathcal{G}_{EP} \circ E) - r(\mathcal{G}_{EP} \times E). $$

Step 1. Build a tree $t_1$ of $\mathcal{G}_{EP} \circ E$, and grow this into a tree $t_1 \uplus t_2$ of $\mathcal{G}_{EP}$.

Step 2. Grow $t_2$ into a tree $\tilde{t}_2$ of $\mathcal{G}_{EP} \circ P$.

Step 3. Take $\tilde{P} := \tilde{t}_2 - t_2$. Build the graph $\mathcal{G}_{E\tilde{P}} := \mathcal{G}_{EP} \circ (E \uplus \tilde{t}_2) \times (E \uplus (\tilde{t}_2 - t_2))$.

STOP

**Justification for the algorithm**

We use the following facts from graph theory.

Fact 0. $\mathcal{V}^v(\mathcal{G}), \mathcal{V}^i(\mathcal{G})$ are determined entirely by the set of circuits (cutsets) and the relative orientation of the edges with respect to the circuits (cutsets) of $\mathcal{G}$.

Fact 1. For any graph $\mathcal{G}_{EP}$, if a tree $t$ contains a tree $t_1$ of $\mathcal{G}_{EP} \circ E$, then $t - t_1$ is a tree of $\mathcal{G}_{EP} \times P$.

Fact 2. If $t_1$ is a tree of $\mathcal{G}_{EP} \circ E$ and $t_2$, a tree of $\mathcal{G}_{EP} \times P$, then $t_1 \uplus t_2$ is a tree of $\mathcal{G}_{EP}$.

If $t_2$ is contracted in $\mathcal{G}_{EP}$, loops of $\mathcal{G}_{EP}$ within $E$, continue to remain as loops, the relative orientation of edges with respect to that of the loops remains unchanged, and further, no new loops are created in $E$. Equivalently, $[\mathcal{V}^v(\mathcal{G}_{EP} \times (E \uplus (P - t_2)))] \circ E = (\mathcal{V}^v(\mathcal{G}_{EP})) \circ E$.
Fact 3. If $\hat{t}_2$ is a tree of $\mathcal{G}_{EP} \circ P$, then if $P - \hat{t}_2$ is deleted in $\mathcal{G}_{EP}$, cutsets of $\mathcal{G}_{EP}$ within $E$, continue to
remain as cutsets, the relative orientation of edges with respect to that of the cutsets remains unchanged,
and further, no new cutsets are created in $E$. Equivalently, $[\mathcal{V}^v(\mathcal{G}_{EP} \circ (E \uplus \hat{t}_2))] \times E = (\mathcal{V}^v(\mathcal{G}_{EP})) \times E$.

We have $\mathcal{G}_{E\tilde{P}} \coloneqq \mathcal{G}_{EP} \circ (E \uplus \hat{t}_2) \times (E \uplus (\hat{t}_2 - t_2)) = \mathcal{G}_{EP} \times (E \uplus (P - t_2)) \circ (E \uplus (\hat{t}_2 - t_2))$.

Therefore, $[\mathcal{V}^v(\mathcal{G}_{EP})] \circ E = [\mathcal{V}^v(\mathcal{G}_{EP} \times (E \uplus (P-t_2))) \circ (E \uplus (\hat{t}_2-t_2))] \circ E = [\mathcal{V}^v(\mathcal{G}_{EP} \times (E \uplus (P-t_2)))] \circ E = [\mathcal{V}^v(\mathcal{G}_{EP})] \circ E$ (by Fact 2. above).

Next, $[\mathcal{V}^v(\mathcal{G}_{E\tilde{P}})] \times E = [\mathcal{V}^v(\mathcal{G}_{EP} \circ (E \uplus \hat{t}_2)) \times (E \uplus (\hat{t}_2 - t_2))] \times E = [\mathcal{V}^v(\mathcal{G}_{EP} \circ (E \uplus \hat{t}_2))] \times E = [\mathcal{V}^v(\mathcal{G}_{EP})] \times E$ (by Fact 3. above). Finally, $|\tilde{P}| = r(\mathcal{G}_{E\tilde{P}} \circ \tilde{P}), r(\mathcal{G}_{E\tilde{P}} \times \tilde{P}) = 0$, and

$$
r(\mathcal{G}_{EP} \circ E) - r(\mathcal{G}_{EP} \times E) = r(\mathcal{G}_{E\tilde{P}} \circ E) - r(\mathcal{G}_{E\tilde{P}} \times E) = r(\mathcal{G}_{E\tilde{P}} \circ \tilde{P}) - r(\mathcal{G}_{E\tilde{P}} \times \tilde{P}) = |\tilde{P}|.
$$

**Problem 18.** For a graph $\mathcal{G}_{E_1 E_2}$ on edges $E_1 \uplus E_2$, give a linear time algorithm for minimal (number of ports) decomposition into multiports $\mathcal{G}_{E_1 P_1}, \mathcal{G}_{E_2 P_2}$, and port connection diagram $\mathcal{G}_{P_1 P_2}$, such that
$\mathcal{V}^v(\mathcal{G}_{E_1 E_2}) = (\mathcal{V}^v(\mathcal{G}_{E_1 P_1}) \oplus \mathcal{V}^v(\mathcal{G}_{P_2 E_2})) \leftrightarrow \mathcal{V}^v(\mathcal{G}_{P_1 P_2})$.

Answer

We need to repeat the graph algorithm of the previous problem three times.

First build copies $\mathcal{G}_{E_1 E'_2}$, $\mathcal{G}_{E'_1 E_2}$ of $\mathcal{G}_{E_1 E_2}$, where $E_1, E_2, E'_1, E'_2$, are pairwise disjoint.

Step 1. Treating $E'_2$ as ports in $\mathcal{G}_{E_1 E'_2}$ apply the algorithm to yield graph $\mathcal{G}_{E_1 P_1}$ (some edges of $E'_2$ get contracted or deleted and $E'_2$ gets converted to $P_2$).

Step 2. Treating $E'_1$ as ports in $\mathcal{G}_{E'_1 E_2}$ apply the algorithm to yield graph $\mathcal{G}_{E_2 P_2}$ (some edges of $E'_1$ get contracted or deleted and $E'_1$ gets converted to $P_2$).

Step 3. Treating $E_1$ as ports in $\mathcal{G}_{E_1 P_1}$ apply the algorithm as in Step 2, to yield graph $\mathcal{G}_{P_1 P_2}$ (contract $T_1 \subseteq E_1$ and delete $T_2 \subseteq E_1$ if $T'_1$ is contracted and $T'_2$ is deleted in Step 2),

or equivalently,

treating $E_2$ as ports in $\mathcal{G}_{E_2 P_2}$ apply the algorithm as in Step 1, to yield graph $\mathcal{G}_{P_1 P_2}$ (contract $T_1 \subseteq E_2$ and delete $T_2 \subseteq E_2$ if $T'_1$ is contracted and $T'_2$ is deleted in Step 1).

Justification for this algorithm is given in the chapter on multiport decomposition in [8].

7.5. Rigid electrical multiports

A general purpose circuit simulator such as SPICE ([4]) is intended to compute the solution to an
electrical network with an affine device-characteristic provided the solution is unique. If we wish to compute
the port behaviour of an affine multiport, as a subroutine, we have to terminate it at the ports suitably with
another affine multiport so that the resulting network has a unique solution. Rigid multiports are precisely
the linear multiports whose port characteristics can be computed using circuit simulators. They capture the
property of uniqueness+existence of solutions of multiports when suitably terminated. Electrical multiports
with affine device-characteristic are said to be rigid iff solutions always exist for arbitrary interior sources
and port conditions uniquely determine interior conditions. More formally, we have the following definition.

**Definition 26.** An affine electrical multiport ($\mathcal{V}_{EPE'P'}$, $\mathcal{A}_{EE'}$), where

$\mathcal{V}_{EPE'P'} \coloneqq \mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}$, $E, E'$ and $P, P'$ being copies of each other with the four sets being pairwise disjoint is said to be rigid, iff

1. when $\mathcal{A}_{EE'}$ is a 'translate' of $\mathcal{V}_{EE'}$, i.e., $\mathcal{A}_{EE'} \coloneqq \mathcal{V}_{EE'} + \alpha_{EE'}$, for some $\alpha_{EE'}$, ($\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{A}_{EE'}$) is a translate of ($\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{V}_{EE'}$);

2. when $f_{PP'} \in \mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{A}_{EE'}$, there is a unique $f_{EE'}$ such that ($f_{EE'}$, $f_{PP'}$) $\in \mathcal{V}_{EPE'P'}$.

**Problem 19.** 1. Give examples of multiports which are rigid and of multiports which are not rigid.

2. Give an example to show that when we short circuit (contract) or open circuit (delete) the ports of a rigid multiport, the resulting network may not have a unique solution. (In the Thevenin-Norton theorem, in order to compute the port behaviour, we compute the solution of networks obtained by short circuiting or open circuiting port branches. This computation cannot be done with circuit simulators which need the solution to be unique for them to function. So to exploit the flexibility provided by rigidity of multiports we need a more sophisticated scheme of computation than the one provided by Thevenin-Norton theorem. This is given in Section 10 .)
Answer

1. A multiport $\mathcal{N}_P$ is rigid in the following cases. There are no topological conditions on the port edges $P$. They may contain loops and cutsets. (A cutset is a minimal set of edges whose deletion increases the number of connected components in the graph.)

(a) $\mathcal{N}_P$ has only positive resistors, voltage and current sources and the voltage sources do not form loops and current sources do not form cutsets. In this case the dimension of the port behaviour $\mathcal{A}_{PP'}$ is $|P|$.

(b) $\mathcal{N}_P$ has only resistors and norators which form neither loops nor cutsets. In this case the dimension of the port behaviour $\mathcal{V}_{PP'}$ can be as large as $2|P|$. (Example: start with a resistor and norator in parallel and add a port edge in parallel to the combination.)

(c) $\mathcal{N}_P$ has only resistors and nullators. In this case the dimension of the port behaviour $\mathcal{V}_{PP'}$ can be as small as 0. (Example: start with a resistor and nullator in parallel and add a port edge in parallel to the combination.)

$\mathcal{N}_P$ is not rigid in the following cases.

(i) $\mathcal{N}_P$ has voltage sources that form loops or current sources that form cutsets. In this case the multiport will have no solution for some choice of source values.

(ii) $\mathcal{N}_P$ has norators which contain loops or cutsets. In this case the port conditions cannot determine the internal conditions uniquely.

2. Build the multiport $\mathcal{N}_P$ as follows. First build a loop with resistors $R, -R, R_1$, where $R, R_1$ are nonzero resistors. Next, put a port branch in parallel with $R_1$. The resulting multiport $\mathcal{N}_P$ is rigid. (Since there are no sources, solution always exists. If we know the voltage and current of the port branch in parallel with $R_1$, the voltage across $R_1$ and the current through the series combination of $R, -R$ are uniquely determined.) Suppose the port branch is short circuited. The resulting circuit contains a parallel combination of $R, -R$ and can have any current circulating within the parallel combination.

Let $\mathcal{N}_P$ be built by first putting $R, -R, R_1$, in parallel and then introducing the port branch in series with $R_1$. In this case again $\mathcal{N}_P$ can be seen to be rigid. (Since there are no sources, solution always exists. If we know the voltage and current of the port branch in series with $R_1$, the current through $R_1$ and the voltage across the parallel combination of $R, -R$ is uniquely determined.) Suppose the port branch is open circuited. The resulting circuit contains a parallel combination of $R, -R$ and can have any current circulating within the parallel combination.

**Problem 20.** Let $\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'})$, and let $\mathcal{V}_{EE'}$ be the vector space translate of $\mathcal{A}_{EE'}$. We say $\mathcal{A}_{EE'}$ is proper iff $\mathcal{V}_{EE'}$ has dimension $|E|$ and that the network $\mathcal{N} := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'})$ is proper iff $\mathcal{A}_{EE'}$ is proper.

Prove the following.

1. A proper network $\mathcal{N} := (\mathcal{G}_E, \mathcal{A}_{EE'})$, has a unique solution iff $\mathcal{N}^{\text{hom}} := (\mathcal{G}_E, \mathcal{V}_{EE'})$, has a unique solution.

2. $\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'})$ is rigid iff $(\mathcal{V}_{EPE'P'} \circ \mathcal{E}E') + \mathcal{V}_{EE'} = \mathcal{F}_{EE'}$ and $(\mathcal{V}_{EPE'P'} \times \mathcal{E}E') \cap \mathcal{V}_{EE'} = \mathbf{0}_{EE'}$.

3. $\mathcal{N}_P$ is rigid iff $\mathcal{N}_P^{\text{hom}} := (\mathcal{V}_{EPE'P'}, \mathcal{V}_{EE'})$ is rigid.

Answer

We remind the reader that Tellegen's Theorem states that $(\mathcal{V}^v\mathcal{G})^{\perp} = \mathcal{V}^i(\mathcal{G})$.

1. Let $\mathcal{N} := (\mathcal{G}_E, \mathcal{A}_{EE'})$, $\mathcal{N}^{\text{hom}} := (\mathcal{G}_E, \mathcal{V}_{EE'})$. We have $r(\mathcal{V}^v(\mathcal{G}_E) \oplus (\mathcal{V}^i(\mathcal{G}_E))_{E'}) = |E|$ (using Theorem 4, Tellegen's Theorem) and $r(\mathcal{V}_{EE'}) = |E|$. Both $\mathcal{N}$ as well as $\mathcal{N}^{\text{hom}}$ have the same $2|E| \times 2|E|$ coefficient matrix of the network equations. The networks have unique solutions iff the matrix is nonsingular. Parts 2. and 3. are handled more generally below.

**Definition 27.** Let $\mathcal{A}_{AB}, \mathcal{A}_B$ be affine spaces on sets $A \uplus B, B$, respectively, $A, B$ being pairwise disjoint. Further, let $\mathcal{A}_{AB}, \mathcal{A}_B$ have vector space translates $\mathcal{V}_{AB}, \mathcal{V}_B$, respectively.

We say the pair $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$ has the **full sum property** iff $\mathcal{V}_{AB} \circ B + \mathcal{V}_B = \mathcal{F}_B$.
We say the pair {$\mathcal{A}_{AB}, \mathcal{A}_B$} has the **zero-intersection property** iff $\mathcal{V}_{AB} \times B \cap \mathcal{V}_B = \mathbf{0}_B$.

We say $\mathcal{A}_{AB}$ is **rigid with respect to** $\mathcal{A}_B$, or that the pair $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$ is **rigid**, iff it has the full sum property and the zero-intersection property.

Note that in the above definition, rigidity of {$\mathcal{A}_{AB}, \mathcal{A}_B$} is taken to be the rigidity of {$\mathcal{V}_{AB}, \mathcal{V}_B$}.
The definition of rigidity in the case of multiports, was in terms of existence of solutions and the capability of port conditions to uniquely fix interior conditions. In the following result we show that these ideas are equivalent to each other.

**Theorem 28.** Let {$\mathcal{A}_{AB}, \mathcal{A}_B$} be a rigid pair and let $\mathcal{V}_{AB}, \mathcal{V}_B$ be the vector space translates of $\mathcal{A}_{AB}, \mathcal{A}_B$, respectively. Then

1. The full sum property of {$\mathcal{A}_{AB}, \mathcal{A}_B$} is equivalent to $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ being nonvoid. whenever $\mathcal{V}_{AB}, \mathcal{V}_B$ are the vector space translates of $\hat{\mathcal{A}}_{AB}, \hat{\mathcal{A}}_B$, respectively. Further, when the full sum property holds for {$\mathcal{A}_{AB}, \mathcal{A}_B$}, $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ has vector space translate $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$.

2. The zero-intersection property of {$\mathcal{A}_{AB}, \mathcal{A}_B$} is equivalent to the statement that, if $f_A \in \mathcal{A}_{AB} \leftrightarrow \mathcal{A}_B$ and $(f_A, f_B), (f_A, f'_B) \in \mathcal{A}_{AB} \cap \mathcal{A}_B$, then $f_B = f'_B$.

*Proof.* 1. Let $\hat{\mathcal{A}}_{AB} = (\alpha_A, \alpha_B) + \mathcal{V}_{AB}, \hat{\mathcal{A}}_B = \beta_B + \mathcal{V}_B$.

By the definition of matched composition, $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ is nonvoid iff $\hat{\mathcal{A}}_{AB} \cap \hat{\mathcal{A}}_B$ is nonvoid, i.e., iff $\hat{\mathcal{A}}_{AB} \circ B \cap \hat{\mathcal{A}}_B$ is nonvoid, i.e., iff there exist $\lambda_B \in \mathcal{V}_{AB} \circ B, \sigma_B \in \mathcal{V}_B$, such that $\alpha_B + \lambda_B = \beta_B + \sigma_B$, i.e., such that $\alpha_B - \beta_B = \sigma_B - \lambda_B$. Clearly when $\mathcal{V}_{AB} \circ B + \mathcal{V}_B = \mathcal{F}_B$, there exist $\lambda_B \in \mathcal{V}_{AB} \circ B, \sigma_B \in \mathcal{V}_B$, such that $\alpha_B - \beta_B = \sigma_B - \lambda_B$ so that $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ is nonvoid.

On the other hand, if $\mathcal{V}_{AB} \circ B + \mathcal{V}_B \neq \mathcal{F}_B$, there exist $\alpha_B, \beta_B$ such that $\alpha_B - \beta_B \notin \mathcal{V}_{AB} \circ B + \mathcal{V}_B$, so that $\hat{\mathcal{A}}_{AB} \cap \hat{\mathcal{A}}_B$ and therefore $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ is void.

By Theorem 6, if $\hat{\mathcal{A}}_{AB} \leftrightarrow \hat{\mathcal{A}}_B$ is nonvoid, its vector space translate is $\mathcal{V}_{AB} \leftrightarrow \mathcal{V}_B$.

2. Let $(\mathcal{V}_{AB} \times B) \cap \mathcal{V}_B = \mathbf{0}_B$. If $f_A \in \mathcal{A}_{AB} \leftrightarrow \mathcal{A}_B$ and $(f_A, f_B), (f_A, f'_B) \in \mathcal{A}_{AB} \cap \mathcal{A}_B$, then $(0_A, (f_B - f'_B)) \in \mathcal{V}_{AB}$, and similarly $(f_B - f'_B) \in \mathcal{V}_B$, so that $(f_B - f'_B) \in (\mathcal{V}_{AB} \times B) \cap \mathcal{V}_B = \mathbf{0}_B$. Next, suppose whenever $f_A \in \mathcal{A}_{AB} \leftrightarrow \mathcal{A}_B$ and $(f_A, f_B), (f_A, f'_B) \in \mathcal{A}_{AB} \cap \mathcal{A}_B$, we have $f_B = f'_B$. Suppose $(\mathcal{V}_{AB} \times B) \cap \mathcal{V}_B \neq \mathbf{0}_B$. Let $g_B \in (\mathcal{V}_{AB} \times B) \cap \mathcal{V}_B$ and let $g_B \neq \mathbf{0}_B$.

If $f_A \in \mathcal{A}_{AB} \leftrightarrow \mathcal{A}_B$, then there exists $f_B$ such that $(f_A, f_B) \in \mathcal{A}_{AB}$ and $f_B \in \mathcal{A}_B$. Clearly $(f_A, f_B) + (0_A, g_B) = (f_A, f_B + g_B) \in \mathcal{A}_{AB}$ and $(f_B + g_B) \in \mathcal{A}_B$, so that we must have $(f_A, f_B + g_B) \in \mathcal{A}_{AB} \cap \mathcal{A}_B$. But this means $f_B = f_B + g_B$, a contradiction. We conclude that $(\mathcal{V}_{AB} \times B) \cap \mathcal{V}_B = \mathbf{0}_B$. $\square$

# 8. Topological transformation

*(This section is based on material from the subsection on topological transformations in [19].)
The problems in this section are from [7] and Chapter 7 of [8].

## 8.1. Minimal common extension of vector spaces

We say $\mathcal{V}_{SP}$ is an extension of $\mathcal{V}_S$ iff there exists a $\mathcal{V}_P$ such that $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P = \mathcal{V}_S$. It is a minimal extension iff $|P|$ is the minimum possible. We say $\mathcal{V}_{SP}$ is a common extension of $\mathcal{V}_S, i = 1, \dots, k$, iff it is an extension of each of $\mathcal{V}_S^i$. It is a minimal common extension of $\mathcal{V}_S^i, i = 1, \dots, k$, iff there exist $\mathcal{V}_P^i, i = 1, \dots, k$, such that $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^i = \mathcal{V}_S^i, i = 1, \dots, k$, and $|P|$ is the minimum possible.

**Problem 21.** Given vector spaces $\mathcal{V}_S^1, \dots, \mathcal{V}_S^k$, show that if $\mathcal{V}_{SP}$ is to be a common extension of $\mathcal{V}_S^i$ through spaces $\mathcal{V}_P^i$ then $|P| \ge r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$.

Give a construction for $\mathcal{V}_{SP}, \mathcal{V}_P^i$ such that $|P| = r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$.
Answer

We remind the reader that a generator matrix for $\mathcal{V}$ is a matrix with not necessarily independent rows whose row space is $\mathcal{V}$.

If $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P = \mathcal{V}_S$, then by Theorem 1, $\mathcal{V}_{SP} \circ S \supseteq \mathcal{V}_S$ and $\mathcal{V}_{SP} \times S \subseteq \mathcal{V}_S$.

In the present problem, it is therefore clear that $\mathcal{V}_{SP} \cdot S \supseteq \sum_i \mathcal{V}_S^i$ and $\mathcal{V}_{SP} \times S \subseteq \bigcap_i \mathcal{V}_S^i$.

Hence, $r(\mathcal{V}_{SP} \cdot S) - r(\mathcal{V}_{SP} \times S) \geq r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$. But

$r(\mathcal{V}_{SP} \cdot S) - r(\mathcal{V}_{SP} \times S) = r(\mathcal{V}_{SP} \cdot P) - r(\mathcal{V}_{SP} \times P) \leq |P|$. Thus, $|P| \geq r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$.

We now give a construction of $\mathcal{V}_{SP}, \mathcal{V}_P^i$ such that $|P| = r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$ and $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^i = \mathcal{V}_S^i$, for each $i$. Let the representative matrix for $\mathcal{V}_{SP}$ be the matrix $R := \begin{pmatrix} R_{+S} & I \\ R_{\cap S} & 0 \end{pmatrix}$, where $\begin{pmatrix} R_{+S} \\ R_{\cap S} \end{pmatrix}$ is a representative matrix for $\sum_i \mathcal{V}_S^i$ and $(R_{\cap S})$ is a representative matrix for $\bigcap_i \mathcal{V}_S^i$.

Let $R_S^i := (K_1^i \ K_2^i) \begin{pmatrix} R_{+S} \\ R_{\cap S} \end{pmatrix}$ generate the space $\mathcal{V}_S^i$, for each $i$. Now $(K_1^i \ K_2^i) \begin{pmatrix} R_{+S} & I \\ R_{\cap S} & 0 \end{pmatrix} = (R_S^i \ K_1^i)$.

Let $K_1^i$ be the generator matrix for $\mathcal{V}_P^i$. It is clear that $\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^i$ is generated by the rows of $R_S^i$. Therefore $\mathcal{V}_S^i = \mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P^i$. Further, $|P|$ is the number of rows of $(R_{+S})$ which equals $r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$.

**Problem 22.** Minimal extension of graphic spaces not always graphic: Construct a simple example (two graphs each of two parallel edges, one with directions aligned and the other with directions opposite), where the minimal extension $\mathcal{V}_{EP}$ of $\mathcal{V}^v(\mathcal{G}_E), \mathcal{V}^v(\mathcal{G}'_E)$, where $\mathcal{G}_E, \mathcal{G}'_E$ are given graphs, is not the voltage space of a graph and show that this is so.

Answer

Let $\mathcal{G}_E$ be composed of two edges $e_1, e_2$ in parallel with same direction and let $\mathcal{G}'_E$ have $e_1, e_2$ in parallel directed oppositely.

To make both $\mathcal{G}_E$ and $\mathcal{G}'_E$ the minors of a graph $\mathcal{G}_{EP}$, we may think of $P$ as composed of $P_1 \uplus P_2$. When edges of $P_1$ are shorted and those of $P_2$ opened, we should get $\mathcal{G}_E$ and when edges of $P_2$ are shorted and those of $P_1$ opened, $\mathcal{G}'_E$. It can be seen that this requires four edges. Starting from $\mathcal{G}_E$ we first introduce two edges in series with $e_2$ one at its tail end and the other at the head end. These would be $P_1$. Now add an edge from the tail of $e_2$ to the head of $e_1$ and an edge from the head of $e_2$ to the tail of $e_1$. These would be $P_2$. The reason we cannot do with less number of edges in $P$ is that to reverse $e_2$ both its endpoints have to be detached and reattached. However, our construction clearly requires

$$r(\mathcal{V}^v(\mathcal{G}_E) + \mathcal{V}^v(\mathcal{G}'_E)) - r(\mathcal{V}^v(\mathcal{G}_E) \cap \mathcal{V}^v(\mathcal{G}'_E)) = 2$$

elements in $P$. So $\mathcal{V}_{EP}$ with $|P| = 2$ cannot be the voltage space of a graph.

**Problem 23.** A metric on vector spaces on $S$: Define the distance between two vector spaces $\mathcal{V}_S$ and $\mathcal{V}'_S$ by $d(\mathcal{V}_S, \mathcal{V}'_S) = r(\mathcal{V}_S + \mathcal{V}'_S) - r(\mathcal{V}_S \cap \mathcal{V}'_S)$.

1. Show that $d(\cdot, \cdot)$ is a metric on the space of all vector spaces on $S$, i.e., $d(\mathcal{V}_S, \mathcal{V}_S) = 0, d(\mathcal{V}_S, \mathcal{V}'_S) = d(\mathcal{V}'_S, \mathcal{V}_S), d(\mathcal{V}_S, \mathcal{V}'_S) + d(\mathcal{V}'_S, \mathcal{V}^v_S) \geq d(\mathcal{V}_S, \mathcal{V}^v_S)$.

2. Show that $d(\mathcal{V}_S, \mathcal{V}'_S) = d(\mathcal{V}_S^\perp, (\mathcal{V}'_S)^\perp)$

Answer

1. We will only verify the triangle inequality. We have,

$$d(\mathcal{V}_S, \mathcal{V}'_S) + d(\mathcal{V}'_S, \mathcal{V}^v_S) = r(\mathcal{V}_S + \mathcal{V}'_S) + r(\mathcal{V}'_S + \mathcal{V}^v_S) - r(\mathcal{V}_S \cap \mathcal{V}'_S) - r(\mathcal{V}'_S \cap \mathcal{V}^v_S) \\ d(\mathcal{V}_S, \mathcal{V}^v_S) = r(\mathcal{V}_S + \mathcal{V}^v_S) - r(\mathcal{V}_S \cap \mathcal{V}^v_S).$$

We use the identity,

$$r(\mathcal{V}_1) + r(\mathcal{V}_2) = r(\mathcal{V}_1 \cap \mathcal{V}_2) + r(\mathcal{V}_1 + \mathcal{V}_2).$$
Hence,

$$d(\mathcal{Y}_S, \mathcal{Y}'_S) + d(\mathcal{Y}'_S, \mathcal{Y}''_S) - d(\mathcal{Y}_S, \mathcal{Y}''_S) = 2[(r(\mathcal{Y}'_S) - r(\mathcal{Y}_S \cap \mathcal{Y}'_S + \mathcal{Y}'_S \cap \mathcal{Y}''_S)) + (r(\mathcal{Y}_S \cap \mathcal{Y}''_S) - r(\mathcal{Y}_S \cap \mathcal{Y}'_S \cap \mathcal{Y}''_S))] \geq 0.$$

2. This follows from the fact that $(\mathcal{Y}_S + \mathcal{Y}'_S)^\perp = \mathcal{Y}_S^\perp \cap (\mathcal{Y}'_S)^\perp$ and $r(\mathcal{Y}_S)^\perp = |S| - r(\mathcal{Y}_S)$.

**Problem 24.** 1. Let $\mathcal{Y}_{SP}$ be a common extension of both $\mathcal{V}_S^1$ and $\mathcal{V}_S^2$. Then $\mathcal{Y}_{SP}$ is a common extension of $\mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^1$ and $\mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^2$.

2. Distance between spaces does not change when we take generalized minor with respect to an extension: Let $d(\cdots, \mathcal{V}_S^j, \cdots)$ denote $r(\sum \mathcal{V}_S^j) - r(\cap \mathcal{V}_S^j)$. If $\mathcal{Y}_{SP}$ is an extension of $\mathcal{V}_S^1, \mathcal{V}_S^2, \cdots, \mathcal{V}_S^k$,

$$d(\mathcal{V}_S^1, \mathcal{V}_S^2, \cdots, \mathcal{V}_S^k) = d((\mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^1), (\mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^2), \cdots, (\mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^k)).$$

3. Suppose $\mathcal{Y}_{SP}$ is a common extension of $\mathcal{V}_S^1, \mathcal{V}_S^2, \cdots, \mathcal{V}_S^k$. Show that, to find a minimal extension, the following procedure is valid. Let $\mathcal{Y}_P^i = \mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^i, i = 1, \cdots, k$. Let $\mathcal{Y}_{PQ}$ be a minimal extension of $\mathcal{Y}_P^1, \mathcal{Y}_P^2, \cdots, \mathcal{Y}_P^k$. Then, $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ}$ is a minimal extension of $\mathcal{V}_S^1, \mathcal{V}_S^2, \cdots, \mathcal{V}_S^k$.

Answer

1. Obvious.

2. Let $\mathcal{Y}_{SP}$ be a common extension of $\mathcal{V}_S^1, \cdots, \mathcal{V}_S^k$ and let $\mathcal{Y}_P^i := \mathcal{Y}_{SP} \leftrightarrow \mathcal{V}_S^i, i = 1, \cdots, k$.

By Theorem 1, it is clear that $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_P^i = \mathcal{Y}_S^i, i = 1, \cdots, k$.

Grow a basis for $\sum \mathcal{V}_S^i$ starting with vectors in $\bigcap_i \mathcal{V}_S^i$ and using vectors which belong to some $\mathcal{V}_S^i$. Let $f_S^1, \cdots, f_S^r$ be the vectors of this basis which are outside $\bigcap_i \mathcal{V}_S^i$ and let them belong to spaces $\mathcal{Y}_{S1}, \cdots, \mathcal{Y}_{Sr}$ respectively where the $\mathcal{Y}_{Si}$ are not necessarily distinct and are each equal to one of $\mathcal{V}_S^j$. Then there exist $f_P^1, \cdots, f_P^r$ in $\mathcal{Y}_{P1}, \cdots, \mathcal{Y}_{Pr}$ respectively such that $f_S^1 \oplus f_P^1, \cdots, f_S^r \oplus f_P^r$ belong to $\mathcal{Y}_{SP}$. (Here $\mathcal{Y}_{Pi}$ are spaces not necessarily distinct each equal to one of the $\mathcal{Y}_P^j$). Suppose $f_P^1, \cdots, f_P^r$ are dependent modulo $(\bigcap_i \mathcal{Y}_P^i)$. Then there is a linear combination $f_S = \lambda_1 f_S^1 + \cdots + \lambda_r f_S^r$ which does not belong to $\bigcap_i \mathcal{V}_S^i$ but $f_P = \lambda_1 f_P^1 + \cdots + \lambda_r f_P^r \in \bigcap_i \mathcal{Y}_P^i$. Now the vector $f_S \in \mathcal{Y}_{SP} \leftrightarrow (\bigcap_i \mathcal{Y}_P^i) \subseteq \bigcap_i (\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_P^i)$ but $f_S \notin \bigcap_i \mathcal{V}_S^i$. This is a contradiction. We conclude therefore, that

$$r(\sum_i \mathcal{Y}_P^i) - r(\bigcap_i \mathcal{Y}_P^i) \geq r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$$

The reverse inequality follows by repeating the argument interchanging $S$ and $P$.

3. We have $\mathcal{Y}_P^i = \mathcal{Y}_{PQ} \leftrightarrow \mathcal{Y}_Q^i$, for some $\mathcal{Y}_Q^i$, for each $i = 1, \cdots, k$. Therefore $(\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ}) \leftrightarrow \mathcal{Y}_Q^i = \mathcal{Y}_{SP} \leftrightarrow (\mathcal{Y}_{PQ} \leftrightarrow \mathcal{Y}_Q^i) = \mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_P^i = \mathcal{V}_S^i$ (using Theorem 3), for each $i = 1, \cdots, k$. Thus $\mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ}$ is a common extension of $\mathcal{V}_S^1, \cdots, \mathcal{V}_S^k$.

To see that it is a minimal extension, when $\mathcal{Y}_{PQ}$ is a minimal common extension of $\mathcal{Y}_P^i$, we note that, by Problem 21, $|Q| = r(\sum_i \mathcal{Y}_P^i) - r(\bigcap_i \mathcal{Y}_P^i)$. Since $\mathcal{Y}_{SP}$ is a minimal common extension of $\mathcal{Y}_S^i$, by part 2 above, $r(\sum_i \mathcal{Y}_P^i) - r(\bigcap_i \mathcal{Y}_P^i) = r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$. Therefore we have that $|Q| = r(\sum_i \mathcal{V}_S^i) - r(\bigcap_i \mathcal{V}_S^i)$. Thus, $\mathcal{Y}_{SQ} \equiv \mathcal{Y}_{SP} \leftrightarrow \mathcal{Y}_{PQ}$ is a minimal extension of $\mathcal{V}_S^1, \cdots, \mathcal{V}_S^k$.

## 8.2. Efficient topological transformations

In the method of topological transformations, the current equations of the original network are rewritten as

$$\begin{pmatrix} R_1 & I & \mathbf{0} \\ R_2 & \mathbf{0} & R_{P_2} \end{pmatrix} \begin{pmatrix} i_E \\ i_{P_1} \\ i_{P_2} \end{pmatrix} = \begin{pmatrix} \mathbf{0} \\ \mathbf{0} \end{pmatrix}, \qquad (17)$$
where $i_{P_1} = 0$ and $i_{P_2}$ is arbitrary. The voltage equations of the original network is rewritten as

$$ \begin{pmatrix} I & -R_2^T & -R_1^T & 0 \\ 0 & -R_{P_2}^T & 0 & I \end{pmatrix} \begin{pmatrix} v_E \\ v'_n \\ v_{P_1} \\ v_{P_2} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \qquad (18) $$

where $v_{P_2} = 0$ and $v_{P_1}$ is arbitrary.

We would like $R_2$ to be the representative matrix of the voltage space of a directed graph which has desirable properties (such as being in several 2- connected pieces) but which can also be obtained simply from the original graph and for which $R_1, R_{P_2}$ can be obtained efficiently.

**Problem 25.** Suppose $\mathcal{G}'_E$ is made up only of coloops (selfloops). What would the matrices $\mathbf{R}_1, \mathbf{R}_{P_2}$, be ?

Answer

If $\mathcal{G}'_E$ is made up only of coloops, then $\mathcal{V}^v(\mathcal{G}'_E) \supseteq \mathcal{V}^v(\mathcal{G}_E)$. Hence, $\mathbf{R}_1$ would have zero rows, i.e., would not exist. The KVE of $\mathcal{G}_E$ can be written as the two constraints

$$ \mathbf{v}_E = (\mathbf{A}_r')^T \mathbf{v}_n' \quad \text{and} \quad \mathbf{R}_{P_2}^T \mathbf{v}_n' = \mathbf{0}, $$

where $\mathbf{A}_r'$ is the reduced incidence matrix of $\mathcal{G}'_E$. But $\mathbf{A}_r'$ is the unit matrix since $\mathcal{G}'_E$ is made up of coloops. So the KVE of $\mathcal{G}_E$ is equivalent to $\mathbf{R}_{P_2}^T \mathbf{v}_E = 0$. Further, the columns of $\mathbf{R}_{P_2}$ are linearly independent. Thus, $\mathbf{R}_{P_2}^T$ must be a representative matrix of $\mathcal{V}^i(\mathcal{G}_E)$.

If $\mathcal{G}'_E$ is made up entirely of self loops, $\mathbf{A}_r'$ will have no rows, i.e., would not exist. Neither would $\mathbf{R}_{P_2}$. The matrix $\mathbf{R}_1$ would be the same as the reduced incidence matrix $\mathbf{A}_r$ of $\mathcal{G}_E$.

**Problem 26.** (Problem 7.9 in [8].) Let $\mathcal{G}_E$ be a directed graph and let $\{E_1, \dots, E_k\}$ be a partition of E. For the following cases build $\mathbf{R}_1, \mathbf{R}_{P_2}$ efficiently: Let $\mathcal{G}'_E$ be

$$ 1. \oplus_i \mathcal{G} \circ E_i $$

$$ 2. \oplus_i \mathcal{G} \times E_i $$

3. obtained from $\mathcal{G}_E$ by fusing nodes,

4. obtained from $\mathcal{G}_E$ by node splitting,

5. obtained from $\mathcal{G}_E$ by first fusing certain nodes and then splitting some nodes of the resulting graph.

Answer

1. This is a special case of part 4 of the present problem, whose solution is given below.

2. $\mathcal{G}'_E \equiv \oplus i\mathcal{G}_E \times E_i$, where $E_1, \dots, E_k$ is a partition of E. Now,

$$ \begin{aligned} \mathcal{V}^v(\oplus i\mathcal{G}_E \times E_i) &= \oplus i\mathcal{V}^v(\mathcal{G} \times E_i) \\ &= \oplus i(\mathcal{V}^v(\mathcal{G}_E) \times E_i). \end{aligned} $$

Any vector of the form $\mathbf{f}_{E_i} \oplus \mathbf{0}_{E_i-E_i}$, where $\mathbf{f}_{E_i} \in (\mathcal{V}^v(\mathcal{G}_E)) \times E_i$ is also in $\mathcal{V}^v(\mathcal{G}_E)$ by the definition of contraction.

So $\mathcal{V}^v(\oplus i\mathcal{G}_E \times E_i) \subseteq \mathcal{V}^v(\mathcal{G}_E)$. Clearly $\mathbf{R}_{P_2}$ cannot exist in this case. We show how to build $\mathbf{R}_1$. Select a forest $T$ of $\mathcal{G}'_E \equiv \oplus i\mathcal{G}_E \times E_i$. Build the graph $\mathcal{G}_E \times (E-T)$. Let $\hat{\mathbf{A}}_{1r}$ be the reduced incidence matrix of $\mathcal{G}_E \times (E-T)$. Let $\mathbf{A}_{1r} \equiv (\hat{\mathbf{A}}_{1r} \mathbf{0})$, where the zero submatrix corresponds to the set $T$. We claim $\mathbf{A}_{1r}$ can be chosen as the matrix $\mathbf{R}_1$. To prove this statement we first observe that if $(\mathbf{A}_{1r} \mathbf{A}_{r'})$ is a representative
matrix of $\mathcal{G}_E$ with $\mathbf{A}'_r$, a representative matrix of $\mathcal{G}'_E$, then $\mathbf{R}_1$ can be taken to be $\mathbf{A}_{1r}$. The rows of $\mathbf{A}_{1r}$ are voltage vectors of $\mathcal{G}_E$ since $\mathcal{G}_E \times (E-T)$ is a contraction of $\mathcal{G}_E$. The columns $T$ are independent in the reduced incidence matrix $\mathbf{A}'_r$ of $\mathcal{G}'_E$, whereas they are zero in $\mathbf{A}_{1r}$. Hence, the matrix $\begin{pmatrix} \mathbf{A}_{1r} \\ \mathbf{A}'_r \end{pmatrix}$ has linearly independent rows.

Next, $r(\mathcal{G}_E \times (E-T)) + r(\mathcal{G}_E \circ T) = r(\mathcal{G}_E)$.

Hence, $r(\mathcal{G}_E \times (E-T)) + |T| = r(\mathcal{G}_E)$.

Thus, the above matrix must have $r(\mathcal{G}_E)$ rows and is therefore a representative matrix of $\mathcal{G}_E$.

This completes the proof that $\mathbf{R}_1$ can be taken to be $\mathbf{A}_{1r}$. The labour involved is to build $\mathcal{G}_E \times (E-T)$ and its reduced incidence matrix. So the algorithm is $O(|E|)$.

3. Let $\mathcal{G}'_E$ be obtained from $\mathcal{G}_E$ by fusing nodes. Then every voltage vector of $\mathcal{G}'_E$ can be derived from a node potential vector of $\mathcal{G}_E$ by assigning the same potential to each group of nodes of $\mathcal{G}_E$ which make up a node of $\mathcal{G}'_E$. Hence,

$$ \mathcal{V}^v(\mathcal{G}'_E) \subseteq \mathcal{V}^v(\mathcal{G}_E). $$

Thus, the method of the previous section of this problem can be used to show the following: Let $T$ be a forest of $\mathcal{G}'_E$. Let $\hat{\mathbf{A}}_{1r}$ be the reduced incidence matrix of $\mathcal{G}_E \times (E-T)$. Then $\mathbf{R}_1$ can be taken to be $(\hat{\mathbf{A}}_{1r} \mathbf{0})$, with zero submatrix corresponding to $T$.

4. Since $\mathcal{G}'_E$ is obtained from $\mathcal{G}_E$ by node splitting, $\mathcal{V}^v(\mathcal{G}'_E) \supseteq \mathcal{V}^v(\mathcal{G}_E)$. The matrix $\mathbf{R}_1$ is composed of row vectors which belong to $\mathcal{V}^v(\mathcal{G}_E)$ and not to $\mathcal{V}^v(\mathcal{G}'_E)$. Hence, in this case $\mathbf{R}_1$ would not exist. We have to construct $\mathbf{R}_{P_2}$ through a fast algorithm.

It is clear that imposing KVL for $\mathcal{G}_E$ is equivalent to

$$ \mathbf{v}_E - (\mathbf{A}'_r)^T \mathbf{v}_n' = \mathbf{0} \qquad (*) $$

$$ \mathbf{R}_{P_2}^T \mathbf{v}_n' = \mathbf{0} \qquad (**) $$

The equation (*) represents the KVL conditions for $\mathcal{G}'_E$. It expresses the branch voltages of $\mathcal{G}'_E$ in terms of the node voltages. Suppose $\mathcal{G}'_E$ is made up of $m$ connected components. For each connected component we choose a pseudo datum node. The node voltage vector $\mathbf{v}_n'$ represents the voltages of the nodes in each component with respect to the pseudo datum node voltage. We could draw additional edges between each node and the corresponding pseudo datum node with the arrow directed towards the latter. The voltages of these additional branches $E_a$ would be given by $\mathbf{v}_n'$. Let us call the graphs obtained by adding $E_a$ to $\mathcal{G}'_E$ and that by adding $E_a$ to $\mathcal{G}_E$ respectively $\mathcal{G}'_a, \mathcal{G}_a$. ($\mathcal{G}_a$ is obtained by performing those node fusions on $\mathcal{G}'_a$ through which $\mathcal{G}'_E$ becomes $\mathcal{G}_E$.) In $\mathcal{G}'_E$ there are no voltage constraints on $E_a$. The voltage constraints on $E_a$ in the graph $\mathcal{G}_a$ would be equivalent to $\mathbf{R}_{P_2}^T \mathbf{v}_n' = \mathbf{0}$. But these constraints are precisely the voltage constraints of $\mathcal{G}_a \circ E_a$. Thus, $\mathbf{R}_{P_2}^T$ may be taken to be an f-circuit matrix of $\mathcal{G}_a \circ E_a$. The complexity of this construction is $O(\text{number of nonzero entries of } \mathbf{R}_{P_2})$. This is bounded above by $\nu(\mathcal{G}_E \circ E_a) + (\nu(\mathcal{G}_E \circ E_a)) \times (|E_a| - \nu(\mathcal{G}_E \circ E_a))$, where $\nu(\mathcal{G})$ is the number of cotree branches in the graph. Usually however the effort required would be much less particularly if we choose a variation of the mesh matrix.

5. Let $\mathcal{G}''_E$ be obtained from $\mathcal{G}_E$ by fusing some nodes and $\mathcal{G}'_E$ from $\mathcal{G}''_E$ by splitting some nodes of $\mathcal{G}''_E$. Let $\mathcal{G}_E$ have KCE $\mathbf{A}_r \mathbf{i}_E = 0$ and KVL constraints $\mathbf{A}_r^T \mathbf{v}_n = \mathbf{v}_E$. Then, KCE of $\mathcal{G}_E$ can be written as

$$ \mathbf{A}_r'' \mathbf{i}_E'' = \mathbf{0} \qquad (&) $$

$$ \mathbf{i}_E'' - \mathbf{i}_E = \mathbf{0} \qquad (&) $$

$$ \mathbf{R}_1 \mathbf{i}_E = \mathbf{0}, \qquad (&) $$
where $\mathbf{A}_r$ is the reduced incidence matrix of $\mathscr{G}_E$ and $\begin{pmatrix} \mathbf{R}_1 \\ \mathbf{A}_r \end{pmatrix}$ is a representative matrix of $\mathscr{V}^v(\mathscr{G}_E)$.

Observe that the set of equations ($\&$) are the KCE of $\mathscr{G}_E$. Since $\mathscr{G}_E$ is obtained by fusing vertices of $\mathscr{G}_E$, we can use the procedure outlined in the solution of parts 2 and 3 of the present problem to construct the matrix $\mathbf{R}_1$.

The KVL of $\mathscr{G}_E$ is imposed by

$$((\mathbf{A}_r)^T \quad \mathbf{R}_1^T)_{\mathbf{v}_{P_1}}^{\mathbf{v}_n} - \mathbf{v}_E = \mathbf{0}.$$

Let us define $\mathbf{v}''_E \equiv (\mathbf{A}_r'')^T \mathbf{v}_n''$. So the KVL of $\mathscr{G}_E$ can be written as

$$(\mathbf{A}_r'')^T \mathbf{v}_n'' - \mathbf{v}''_E = \mathbf{0} \qquad (\&\&)$$

$$\mathbf{v}''_E + \mathbf{R}_1^T \mathbf{v}_{P_1} - \mathbf{v}_E = \mathbf{0}. \qquad (\&\&)$$

Observe that the first set of equations of ($\&\&$) above are the KVE of $\mathscr{G}_E$.

Now let $\mathscr{G}_E'$ be obtained from $\mathscr{G}_E$ by splitting nodes. Then KCE of $\mathscr{G}_E'$ can be written as

$$\mathbf{A}_r' \mathbf{i}_E'' + \mathbf{R}_{P_2} \mathbf{i}_{P_2} = \mathbf{0}$$

and the KVE of $\mathscr{G}_E'$ can be written as

$$(\mathbf{A}_r'')^T \mathbf{v}_n'' - \mathbf{v}''_E = \mathbf{0}$$

$$\mathbf{R}_{P_2}^T \mathbf{v}_n'' = \mathbf{0},$$

where $\mathbf{A}_r'$ is the reduced incidence matrix of $\mathscr{G}_E'$. The matrix $\mathbf{R}_{P_2}$ can be constructed therefore by using the procedure outlined in the solution of part 4 above. Observe that the result of the above procedure is that KCL and KVL constraints of $\mathscr{G}_E'$ are written equivalently (as far as $\mathbf{i}_E, \mathbf{v}_E$ are concerned) as

$$\mathbf{A}_r' \mathbf{i}_E + \mathbf{R}_{P_2} \mathbf{i}_{P_2} = \mathbf{0}$$

$$\mathbf{R}_1 \mathbf{i}_E = \mathbf{0}$$

$$(\mathbf{A}_r'')^T \mathbf{v}_n'' + \mathbf{R}_1^T \mathbf{v}_{P_1} - \mathbf{v}_E = \mathbf{0}$$

$$\mathbf{R}_{P_2}^T \mathbf{v}_n'' = \mathbf{0}.$$

# 9. Transpose and adjoint

## 9.1. Computing a set of entries of the input-output matrix efficiently

**Problem 27.** Let us suppose, as in the section on 'Transpose' in [19], the cost of computing a row or a column of a matrix is unit. If we have to compute a set of entries of a matrix, what is the minimum cost of the computation?

### Answer

We need to compute the minimum number of rows and columns which together contain all the required entries. Build a bipartite graph with $V_1, V_2$, the 'left' and 'right' vertices representing the set of rows and the set of columns respectively. Join vertex $i \in V_1$ to $j \in V_2$, if the $(i, j)$ entry has to be computed. The minimum cover of this bipartite graph is a minimum sized set of vertices $V_1' \cup V_2''$, where $V_1' \subseteq V_1, V_2' \subseteq V_2$, such that every edge of the bipartite graph is incident on some vertex in $V_1' \cup V_2''$. Computing the minimum cover for a bipartite graph is a well known problem which can be solved efficiently, where, for instance, one can use the 'max flow - min cut' theorem (see Chapter 10 of [8]).
<figure><img src="image_2.png" /><figcaption>Figure 1: Block diagrams B and B'</figcaption></figure>

## 9.2. Application to block diagrams

**Problem 28.** Let a block diagram B made up of vector summers, vector connection points and vector block constraints $z_y^j = K_j z_u^j$, have the overall input-output relationship $y = Ku$. Show that the block diagram B' (see Figure 1) obtained by reversing all arrows, replacing connection points by summers, summers by connection points, block constraints $z_y^j = K_j z_u^j$ by $\hat{z}_y^j = K_j^T \hat{z}_u^j$ has the overall input-output relationship $\hat{y} = K^T \hat{u}$.

### Answer

We fix some convenient notation for this problem. Let $F(z) = 0$ be a linear homogeneous equation in the vector variable $z$. The solution space of this equation is a vector space $\mathcal{V}_z$. Let $F^{\perp}(z) = 0$ denote the equation whose solution space is the vector space $\mathcal{V}_z^{\perp}$.

Let the topological constraints of the block diagram be in terms of summers and connection points. The summer (see Figure 1) has several vector inputs say $x_1, \dots, x_n$, and a single vector output $v$. The constraint is $x_1 + \dots + x_n = v$. Let us denote this constraint by $F_{\Sigma}(x_1, \dots, x_n, v) = 0$. This constraint has the form

$$ (I \quad \cdots \quad I \quad -I) \begin{pmatrix} x_1 \\ \vdots \\ x_n \\ v \end{pmatrix} = 0. \qquad (19) $$

Let the solution space of this equation be $\mathcal{S}_{XV}$ where $X = X_1 \uplus \cdots \uplus X_n$.

The connection point (see Figure 1) has a single vector input $x'$ and several vector outputs say $v'_1, \dots, v'_n$. The constraint is $x' = v'_1, x' = v'_2, \dots, x' = v'_n$. Let us denote this constraint by $F_{\mathcal{C}}(v'_1, \dots, v'_n, x') = 0$. This
constraint has the form

$$ \begin{pmatrix} -I & \mathbf{0} & \cdots & \cdots & \mathbf{0} & I \\ \mathbf{0} & -I & \mathbf{0} & \cdots & \mathbf{0} & I \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \mathbf{0} & \cdots & \mathbf{0} & \cdots & -I & I \end{pmatrix} \begin{pmatrix} v'_1 \\ v'_2 \\ \vdots \\ v'_n \\ x' \end{pmatrix} = \mathbf{0}. \qquad (20) $$

Let the solution space of this equation be $\mathcal{C}_{X'V'}$, where $V' = V'_1 \uplus \cdots \uplus V'_n$.

We note that $F_{\Sigma}^{\perp}(-v'_1, \cdots, -v'_n, x') = 0$, is the constraint $F_{\mathcal{C}}(v'_1, \cdots, v'_n, x') = 0$, with the solution space $\mathcal{C}_{X'V'} = (\mathcal{S}_{\tilde{X}V})_{(-V')X'}$. (The rows of the coefficient matrices of $F_{\Sigma}(x_1, \cdots, x_n, v) = 0$ and $F_{\mathcal{C}}(-v'_1, \cdots, -v'_n, x') = 0$, are orthogonal and their dimensions add up to the number of columns of the coefficient matrix.) The constraint $F_{\Sigma}^{\perp}(-v'_1, \cdots, -v'_n, x') = 0$, reverses the arrows in the summer, replacing the single output $v$ by the single input $x'$, and the many inputs $x_i$ by the many outputs $v'_i$, resulting in a connection point. The constraint $F_{\mathcal{C}}^{\perp}(-x'_1, \cdots, -x'_n, v') = 0$, reverses the arrows in the connection point, replacing the single input $x$ by the single output $v'$ and the many outputs $v'_i$ by many inputs $x'_i$, resulting in a summer.

The device-characteristic is made up of blocks whose constraints have the form $z_y = K z_u$. Let us denote this constraint by $F_{\mathcal{B}}(z_u, z_y) = 0$, and the solution space of this equation by $\mathcal{B}_{Z_u Z_y}$. The constraint $F_{\mathcal{B}}^{\perp}(z'_y, -z'_u) = 0$, has the form $z'_y = K^T z'_u$ and has the solution space $(\mathcal{B}_{Z_u Z_y})_{Z'_y(-Z'_u)}$.

We make the following 'decoupling' assumptions about block diagrams.

* No two blocks have common variables and similarly no two of summers and connection points have common variables.

* The input variables occur only in summer constraints and output variables, only in connection points.

If the original block diagram $B$ is not decoupled, it can be converted into a decoupled block diagram $B_d$ without altering the overall input-output relationship by introducing dummy constraints $\beta = I\alpha$, where $\beta$ is a new variable which replaces the variable $\alpha$ in one of the constraints. The dummy constraint can be regarded as a block constraint or as a summer / connection point as required. For instance, if $\alpha$ is common to two topological constraints or to two block constraints we replace $\alpha$ by the new variable $\beta$ in one of the constraints. The dummy constraint $\beta = I\alpha$ is here treated as a block constraint in the former case and as a summer / connection point in the latter case.

Let us denote by $F_{\Sigma}^{\oplus}(\cdot)$, direct sums of summer constraints and similarly let $F_{\mathcal{C}}^{\oplus}(\cdot)$, $F_{\mathcal{B}}^{\oplus}(\cdot)$, denote direct sums of corresponding constraints. Under this condition the original constraints have the form
$$F_{\Sigma}^{\oplus}(u, z_u) = 0, F_{\mathcal{C}}^{\oplus}(y, z_y) = 0 \quad (\text{topological}),$$
$$F_{\mathcal{B}}^{\oplus}(z_u, z_y) = 0 \quad (\text{device characteristic}).$$

Let the solution spaces of the topological and device-characteristic constraints be respectively $\mathcal{V}_{UZ_uZ_yY}, \mathcal{V}_{Z_uZ_y}$. The space of possible $(u, y)$ vectors would then be $\mathcal{V}_{UY} := \mathcal{V}_{UZ_uZ_yY} \leftrightarrow \mathcal{V}_{Z_uZ_y}$. We then have, by the implicit duality theorem, $\mathcal{V}_{UY} := \mathcal{V}_{UZ_uZ_yY} \leftrightarrow \mathcal{V}_{Z_uZ_y}$.

Therefore $(\mathcal{V}_{UY}^{\perp})(-Y')U' = (\mathcal{V}_{UZ_uZ_yY}^{\perp})(-Y')Z'_y(-Z'_u)U' \leftrightarrow (\mathcal{V}_{Z_uZ_y}^{\perp})Z'_y(-Z'_u)$.

Now $(\mathcal{V}_{UZ_uZ_yY}^{\perp})(-Y')Z'_y(-Z'_u)U'$ is the solution space of the constraints $(F_{\Sigma}^{\oplus})^{\perp}(-y', z'_y) = 0, (F_{\mathcal{C}}^{\oplus})^{\perp}(u', -z'_u) = 0$, i.e., of the constraints

$F_{\mathcal{C}}^{\oplus}(y', z'_y) = 0, F_{\Sigma}^{\oplus}(u', z'_u) = 0$, and $(\mathcal{V}_{Z_uZ_y}^{\perp})_{Z'_y(-Z'_u)}$ is the solution space of the constraint $(F_{\mathcal{B}}^{\oplus})^{\perp}(z'_y, -z'_u) = 0$. Note that if $F_{\mathcal{B}}^{\oplus}(z_u, z_y) = 0$ is the constraint $z_y = K_{\mathcal{B}}z_u$ then $(F_{\mathcal{B}}^{\oplus})^{\perp}(z'_y, -z'_u) = 0$. is the constraint $z'_y = K_{\mathcal{B}}^T z'_u$.

It is clear that that the constraints $F_{\mathcal{C}}^{\oplus}(y', z'_y) = 0, F_{\Sigma}^{\oplus}(u', z'_u) = 0, (F_{\mathcal{B}}^{\oplus})^{\perp}(z'_y, -z'_u) = 0$ are the constraints of $B'$, obtained from block diagram $B$ by reversing all arrows, replacing connection points by summers, summers by connection points, block constraints $z'_y = K_j z'_u$ by $\hat{z}'_y = K_j^T \hat{z}'_u$ and $B'$ has the overall input-output relationship $\hat{y} = K^T \hat{u}$. Suppose the original block diagram before decoupling is $B_{orig}$. We know that this has the same overall input-output relationship as $B$, i.e., $y = Ku$. Suppose, in $B_{orig}$, we reverse
<figure><img src="image_3.png" /><figcaption>Figure 2: Convention for port voltages and currents</figcaption></figure>

all arrows, replacing connection points by summers, summers by connection points, block constraints by the transpose constraints to obtain the block diagram $B'_{orig}$. It is clear that this is the same as the block diagram obtained by undoing the decoupling process in $B'$. Therefore $B'_{orig}$ has the overall input-output relationship $\hat{y} = K^T \hat{u}$.

### 9.3. Electrical multiports and adjoints

*(This subsection uses IIT, IDT (Theorems 1,2), Theorem 6 and the definitions of electrical network and multiport from Section 2.)

Let $\mathcal{A}_{EE'}$, where $E, E'$, are disjoint copies of each other, be an affine space with vector space traanslate $\mathcal{V}_{EE'}$. The dirac dual $\mathcal{A}_{EE'}^d$ of $\mathcal{A}_{EE'}$ is built by building the orthogonal dual of $\mathcal{V}_{EE'}$ and interchanging primed and unprimed variables, i.e., $\mathcal{A}_{EE'}^d := (\mathcal{V}_{EE'}^{\perp})_{E'E}$. The adjoint of $\mathcal{A}_{EE'}^{adj}$ of $\mathcal{A}_{EE'}$ is built by first building the orthogonal dual of $\mathcal{V}_{EE'}$, interchanging primed and unprimed variables and changing the sign of the primed variables, i.e., $\mathcal{A}_{EE'}^{adj} := (\mathcal{V}_{EE'}^{\perp})_{(-E')E}$. When $\mathcal{A}_{EE'}$ is an electrical characteristic, the primed and unprimed variables correspond respectively to current and voltage variables. In this section and in Sections 10, 11, we treat an electrical device as a multiport with the convention for voltages and currents as shown in Figure 2.

**Definition 29.** An affine electrical multiport $\mathcal{N}_P$ is a pair $(\mathcal{G}_{EP}, \mathcal{A}_{EE'})$. $\mathcal{A}_{EE'}$ is an affine space on $E \uplus E'$, $E, E'$ and $P, P'$ being copies of each other with the four sets being pairwise disjoint. The source-free multiport $\mathcal{N}_P^{hom} := (\mathcal{G}_{EP}, \mathcal{V}_{EE'})$, where $\mathcal{V}_{EE'}$ is the vector space translate of $\mathcal{A}_{EE'}$. The dirac dual multiport $\mathcal{N}_P^d$ is the pair $(\mathcal{G}_{EP}, (\mathcal{V}_{EE'}^{\perp})_{E'E})$. The adjoint multiport $\mathcal{N}_P^{adj}$ is the pair $(\mathcal{G}_{EP}, (\mathcal{V}_{EE'}^{\perp})_{(-E')E})$. Equivalently

$\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'}), \text{ where } \mathcal{V}_{EPE'P'} := \mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}, \mathcal{N}_P^{hom} := (\mathcal{V}_{EPE'P'}, \mathcal{V}_{EE'}), \mathcal{N}_P^d \text{ is the pair } ((\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}), (\mathcal{V}_{EE'}^{\perp})_{E'E}) = ((\mathcal{V}_{EPE'P'}^{\perp})_{E'P'}EP, (\mathcal{V}_{EE'}^{\perp})_{E'E}). \mathcal{N}_P^{adj} \text{ is the pair } ((\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}), (\mathcal{V}_{EE'}^{\perp})_{(-E')E}) = ((\mathcal{V}_{EPE'P'}^{\perp})_{(-E')(-P')}EP, (\mathcal{V}_{EE'}^{\perp})_{(-E')E}).$

For better readability we sometimes write $\mathcal{V}_{EPE'P'}$ as $\mathcal{V}_{vEvPiEiP}$, $\mathcal{A}_{EE'}$ as $\mathcal{A}_{vEiE}$, $\mathcal{V}_{EE'} := \mathcal{V}_{vEiE}$, $\mathcal{N}_P^{adj}$ by $((\mathcal{V}_{vEvPiEiP}^{\perp})_{(-i_E)}(-i_P)\hat{v}_E\hat{v}_P, (\mathcal{V}_{vEiE}^{\perp})_{(-i_E)}\hat{v}_E)$.

**Problem 29.** In the following cases of device-characteristics compute the adjoint and the dirac dual characteristic.

1. A source-accompanied resistor $v = Ri + \mathcal{E}$, $R$ being diagonal, with nonzero diagonal entries. Also examine the case where $R$ is a matrix.

2. The source-accompanied current controlled voltage source (CCVS) and the source-accompanied voltage controlled current source (VCCS) shown below.

$$ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & -r & 0 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ i_1 \\ i_2 \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}; \begin{pmatrix} 0 & 0 & 1 & 0 \\ -g & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ i_1 \\ i_2 \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}; \qquad (21) $$
3. The source-accompanied current controlled current source (CCCS) and the source-accompanied voltage controlled voltage source (VCVS) shown below.

$$ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & -\alpha & 1 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ i_1 \\ i_2 \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}; \begin{pmatrix} 0 & 0 & 1 & 0 \\ -\beta & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ i_1 \\ i_2 \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}. \qquad (22) $$

Answer

1. The vector space translate of the characteristic is the solution space of $v = Ri$. The orthogonal dual has the characteristic $\hat{i} = -R^T \hat{v} = -R \hat{v}$. The adjoint has the characteristic $\tilde{v} = R \tilde{i}$. Thus the source-free resistor is self adjoint or reciprocal. This would be true even if $R$ is a symmetric matrix of full rank. The Dirac dual of $v = Ri + \mathcal{E}$ has the characteristic $\tilde{v} = -R^T \tilde{i}$. Therefore the source-free device $v = Ri$ would be self Dirac dual iff $R = -R^T$.

2. The adjoints are respectively (built by first building the orthogonal dual of the source-free characteristic, interchanging current and voltage variables and changing the sign of the current variables)

$$ \begin{pmatrix} 0 & -r & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}; \begin{pmatrix} 1 & 0 & 0 & -g \\ 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (23) $$

Thus the adjoints of source-free CCVS, VCCS remain source-free CCVS,VCCS respectively, with the same parameters $r, g$ respectively, but the direction of control which was originally from port 1 to port 2 is now from port 2 to port 1.

3. The adjoints are respectively,

$$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & \alpha \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}; \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & \beta & 0 & 0 \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (24) $$

Thus the adjoints of source-free CCCS, VCVS are source-free VCVS,CCCS respectively, but the direction of control which was originally from port 1 to port 2 is now from port 2 to port 1. Also, the current gain factor is now the negative of the voltage gain factor in the CCVS to VCVS case and vice versa in VCVS to CCVS case.

In each of the above cases the dirac dual is built by first building the orthogonal dual of the source-free characteristic, interchanging current and voltage variables but not changing the sign of the current variables. For instance, in the case of CCVS and VCCS, the dirac dual is

$$ \begin{pmatrix} 0 & r & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}; \begin{pmatrix} 1 & 0 & 0 & g \\ 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \tilde{i}_1 \\ \tilde{i}_2 \\ \tilde{v}_1 \\ \tilde{v}_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (25) $$

**Definition 30.** Let $N_P := (\mathcal{G}_{EP}, \mathcal{K}_{EE'}) = (\mathcal{V}_{EPE'P'}, \mathcal{K}_{EE'})$ be a multiport. The port behaviour of $N_P$ is defined to be $\mathcal{K}_{PP'} := (\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{K}_{EE'})_{P(-P')}.$

**Remark 6.** Note that in Definition 30, the current direction is changed relative to the direction of the port edge as in Figure 2. This is done in order to be consistent with electrical network theory literature. But we use this definition only for problems in Subsection 9.3, Section 10 and Section 11. For general ideas related to multiport decomposition, this change of sign of the current variable corresponding to $P'$ is unnecessary.
<figure><img src="image_4.png" /><figcaption>Figure 3: Multiport $\mathcal{N}_P$ with multiport input-output behaviour $\mathcal{K}_{uy}$ and adjoint $\mathcal{N}_P^{adj}$ with input-output behaviour $\mathcal{K}_{\hat{u}\hat{y}}^{adj}$.</figcaption></figure>

**Problem 30.** Let $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{A}_{EE'})$, and let $\mathcal{V}_{EE'}$ be the vector space translate of $\mathcal{A}_{EE'}$. Let the port behaviour of $\mathcal{N}_P$ be $\mathcal{A}_{PP'} = (\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{A}_{EE'})_{(-P')P}$, with vector space translate $\mathcal{V}_{PP'}$. Show that the port behaviour of $\mathcal{N}_P^{hom}$, $\mathcal{N}_P^d$, $\mathcal{N}_P^{adj}$ are respectively $\mathcal{V}_{PP'}$, $\mathcal{V}_{PP'}^d$, $\mathcal{V}_{PP'}^{adj}$.

**Answer**

We have the following.

The port behaviour of $\mathcal{N}_P^{hom}$ is $(\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{V}_{EE'})_{(-P')P}$. This is the vector space translate of $(\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{A}_{EE'})_{(-P')P}$, by Theorem 6, since the latter is given to be nonvoid with vector space translate $\mathcal{V}_{PP'}$.

Similarly, the port behaviour of $\mathcal{N}_P^d$ is $((\mathcal{V}_{EPE'P'}^\perp)_{E'P'EP} \leftrightarrow (\mathcal{V}_{EE'}^\perp)_{E'E})_{(-P')P} = (\mathcal{V}_{PP'}^\perp)_{P'P} = \mathcal{V}_{PP'}^d$.

Similarly, the port behaviour of $\mathcal{N}_P^{adj}$ is $((\mathcal{V}_{EPE'P'}^\perp)_{(-E')(-P')EP} \leftrightarrow (\mathcal{V}_{EE'}^\perp)_{(-E'E)E})_{(-P')P} = (\mathcal{V}_{PP'}^\perp)_{(-P')P} = \mathcal{V}_{PP'}^{adj}$.

**Problem 31.** Figure 3 shows an input-output behaviour $\mathcal{K}_{uy}$ associated with a multiport $\mathcal{N}_P$. Let $\mathcal{V}_{uy}$ be the vector space translate of $\mathcal{K}_{uy}$. If $\mathcal{K}_{uy}$ is the solution space of

$$ \begin{pmatrix} y_1' \\ y_2'' \end{pmatrix} = \begin{pmatrix} K_{11} & K_{12} \\ K_{21} & K_{22} \end{pmatrix} \begin{pmatrix} u_1' \\ u_2'' \end{pmatrix} + \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}, \qquad (26) $$

show that the adjoint $\mathcal{V}_{\hat{u}\hat{y}}^{adj}$ of $\mathcal{V}_{uy}$ (and therefore also of $\mathcal{K}_{uy}$) associated with $\mathcal{N}_P^{adj}$ (Figure 3) would be the solution space of

$$ \begin{pmatrix} \hat{y}_1'' \\ \hat{y}_2' \end{pmatrix} = \begin{pmatrix} -K_{11}^T & K_{21}^T \\ K_{12}^T & -K_{22}^T \end{pmatrix} \begin{pmatrix} \hat{u}_1'' \\ \hat{u}_2' \end{pmatrix}. \qquad (27) $$

**Answer**

For convenience, let us rename the voltage variables of the ports as $v_1, v_2, v_3, v_4$ and the current variables of the ports as $i_1, i_2, i_3, i_4$. Thus in $\mathcal{N}_P$, $v_1 = u_1'$, $i_2 = u_2''$, $v_3 = y_1'$, $i_4 = y_2''$ and in $\mathcal{N}_P^{adj}$, $\hat{i}_1 = \hat{y}_1''$, $\hat{v}_2 = \hat{y}_2'$, $\hat{i}_3 = \hat{u}_1''$, $\hat{v}_4 = \hat{u}_2'$. We remind the reader about our notation: $\mathcal{V}_{AB}$ is the same as $\mathcal{V}_{BA}$. However, $(\mathcal{V}_{AB})_{PQ}$ refers to the vector space where the variable $(x_A, y_B)$ in $\mathcal{V}_{AB}$ is replaced by $(x_P, y_Q)$.

Suppose the port behaviour of $\mathcal{N}_P$ is $(v_P, i_P) \in \mathcal{V}_{vPiP}$. Then the port behaviour of $\mathcal{N}_P^{adj}$ is $(\hat{v}_P, \hat{i}_P) \in \mathcal{V}_{\hat{v}_P\hat{i}_P}^{adj} := (\mathcal{V}_{vPiP}^\perp)_{(-\hat{i}_P)\hat{v}_P}$. Now in $\mathcal{N}_P$, we have attached sources and sensors to the ports. The voltage sources have no constraints on currents and current sources have no constraints on voltages. The voltage
sensors carry zero currents and the current sensors carry zero voltages. Thus in $\mathcal{N}_P$ we have the constraint $(v_1, i_2, v_3, i_4) \in \check{\mathcal{V}}_{v_1i_2v_3i_4}$, where $\check{\mathcal{V}}_{v_1i_2v_3i_4} = \check{\mathcal{V}}_{v_1i_2v_3i_4} \leftrightarrow (\mathcal{F}_{i_1} \oplus \mathcal{F}_{v_2} \oplus \mathbf{0}_{i_3} \oplus \mathbf{0}_{v_4})$ and in $\mathcal{N}_P^{\text{adj}}$, we show below, we have $(\hat{i}_1, \hat{v}_2, \hat{i}_3, \hat{v}_4) \in \check{\mathcal{V}}_{\hat{i}_1\hat{v}_2\hat{i}_3\hat{v}_4}^{\text{adj}}$ where, $\check{\mathcal{V}}_{\hat{i}_1\hat{v}_2\hat{i}_3\hat{v}_4}^{\text{adj}} := \check{\mathcal{V}}_{\hat{v}_P\hat{i}_P}^{\text{adj}} \leftrightarrow (\mathbf{0}_{\hat{v}_1} \oplus \mathbf{0}_{\hat{i}_2} \oplus \mathcal{F}_{\hat{v}_3} \oplus \mathcal{F}_{\hat{i}_4})$.

Observe that the adjoint $\check{\mathcal{V}}_{\hat{i}_1\hat{v}_2\hat{i}_3\hat{v}_4}^{\text{adj}} := (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4$
$= (\check{\mathcal{V}}_{v_1i_2v_3i_4} \leftrightarrow (\mathcal{F}_{i_1} \oplus \mathcal{F}_{v_2} \oplus \mathbf{0}_{i_3} \oplus \mathbf{0}_{v_4}))^{\perp}(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4$
$= (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})^{\perp}(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4$
$= (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4 = (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4 = (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4 = (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4 = (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4$

Let us apply these ideas to the problem in question. $\check{\mathcal{V}}_{uy} := \check{\mathcal{V}}_{u'_1u_2y'_1y_2} = \check{\mathcal{V}}_{v_1i_2v_3i_4}$ is defined by

$$ \begin{pmatrix} -K_{11} & -K_{12} & I & 0 \\ -K_{21} & -K_{22} & 0 & I \end{pmatrix} \begin{pmatrix} v_1 \\ i_2 \\ v_3 \\ i_4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (28) $$

The adjoint $\check{\mathcal{V}}_{\hat{i}_1\hat{v}_2\hat{i}_3\hat{v}_4}^{\text{adj}} := (\check{\mathcal{V}}_{v_1i_2v_3i_4}^{\perp})(-\hat{i}_1)\hat{v}_2(-\hat{i}_3)\hat{v}_4$ would be the solution space of

$$ \begin{pmatrix} I & 0 & K_{11}^T & K_{21}^T \\ 0 & I & K_{12}^T & K_{22}^T \end{pmatrix} \begin{pmatrix} -\hat{i}_1 \\ \hat{v}_2 \\ -\hat{i}_3 \\ \hat{v}_4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}. \qquad (29) $$

This can be rewritten as

$$ \begin{pmatrix} I & 0 & K_{11}^T & -K_{21}^T \\ 0 & I & -K_{12}^T & K_{22}^T \end{pmatrix} \begin{pmatrix} \hat{i}_1 \\ \hat{v}_2 \\ \hat{i}_3 \\ \hat{v}_4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \qquad (30) $$

Noting that we have renamed $\hat{i}_1 = \hat{y}_1$", $\hat{v}_2 = \hat{y}'_2$, $\hat{i}_3 = \hat{u}_1$", $\hat{v}_4 = \hat{u}'_2$, we get

$$ \begin{pmatrix} I & 0 & K_{11}^T & -K_{21}^T \\ 0 & I & -K_{12}^T & K_{22}^T \end{pmatrix} \begin{pmatrix} \hat{y}_1 \\ \hat{y}'_2 \\ \hat{u}_1 \\ \hat{u}'_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \qquad (31) $$

which can be rewritten as (i.e., $\check{\mathcal{V}}_{\hat{u}\hat{y}}^{\text{adj}}$ can be rewritten as)

$$ \begin{pmatrix} \hat{y}_1 \\ \hat{y}'_2 \end{pmatrix} = \begin{pmatrix} -K_{11}^T & K_{21}^T \\ K_{12}^T & -K_{22}^T \end{pmatrix} \begin{pmatrix} \hat{u}_1 \\ \hat{u}'_2 \end{pmatrix}. \qquad (32) $$

## 9.4. Reciprocal and Dirac structures

**Problem 32.** Give a general framework for the proofs of statements of the type 'generalized minors of reciprocal structures are reciprocal' ([11]).

### Answer

Let $\$,$ $\dagger$ be two operations on vector spaces satisfying the following.

1. If $\mathcal{V}$ is a vector space on $E$, so are $\mathcal{V}^\$,$ $\mathcal{V}^\dagger$.
2. $(\mathcal{V}^S)^S = \mathcal{V}, (\mathcal{V}^\dagger)^\dagger = \mathcal{V}$.

3. $(\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P)^S = \mathcal{V}_{SP}^S \leftrightarrow \mathcal{V}_P^S$; $(\mathcal{V}_{SP} \leftrightarrow \mathcal{V}_P)^\dagger = \mathcal{V}_{SP}^\dagger \leftrightarrow \mathcal{V}_P^\dagger$.

Let us call a vector space $\mathcal{V}$, which satisfies $\mathcal{V}^S = \mathcal{V}^\dagger$, g-reciprocal. Then it is clear that the generalized minor of g-reciprocal vector spaces is also a g-reciprocal space.

## 10. Rigid multiport port behaviour computation: generalized Thevenin-Norton Theorem

*(This section depends on Subsections 7.5,9.3.)*

A useful artifice for processing a multiport through a conventional circuit simulator, is to terminate it appropriately so that the resulting network, if it has a solution, has a unique solution. This solution would also contain a solution to the original multiport. This is possible only for rigid networks. We now describe this technique in detail following [17]. We first need to establish that the adjoints of rigid multiports are rigid. We remind the reader that pair $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$ has the full sum property iff $\mathcal{V}_{AB} \circ B + \mathcal{V}_B = \mathcal{F}_B$, $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$ has the zero-intersection property iff $\mathcal{V}_{AB} \times B \cap \mathcal{V}_B = \mathbf{0}_B$, $\mathcal{A}_{AB}$ is rigid with respect to $\mathcal{A}_B$, iff it has the full sum property and the zero-intersection property.

**Problem 33.** Prove that $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{A}_{EE'})$ is rigid iff $\mathcal{N}_P^{adj} := (\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}, (\mathcal{V}^\perp_{EE'})(-E')E)$, is rigid.

*Answer*

If $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$ is rigid, we have $(\mathcal{V}_{AB} \circ B + \mathcal{V}_B)^\perp = \mathcal{V}^\perp_{AB} \cap \mathcal{V}^\perp_B = \mathcal{F}^\perp_B = \mathbf{0}_B$, and $(\mathcal{V}_{AB} \times B \cap \mathcal{V}_B)^\perp = \mathcal{V}^\perp_{AB} \circ B + \mathcal{V}^\perp_B = \mathbf{0}_B^\perp = \mathcal{F}_B$, so that $\{\mathcal{V}^\perp_{AB}, \mathcal{V}^\perp_B\}$ is also rigid. Since $(\mathcal{V}^\perp)^\perp = \mathcal{V}$, it is clear, if $\{\mathcal{V}^\perp_{AB}, \mathcal{V}^\perp_B\}$ is rigid, so is $\{\mathcal{V}_{AB}, \mathcal{V}_B\}$ and therefore also $\{\mathcal{A}_{AB}, \mathcal{A}_B\}$.

The rigidity of $\mathcal{N}_P := (\mathcal{G}_{EP}, \mathcal{A}_{EE'})$ is, by definition, the rigidity of $(\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}, \mathcal{V}_{EE'})$. By the discussion above this is equivalent to the rigidity of $((\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'})^\perp, \mathcal{V}^\perp_{EE'})$, i.e., to the rigidity of $((\mathcal{V}^i(\mathcal{G}_{EP})) \oplus (\mathcal{V}^v(\mathcal{G}_{EP}))_{E'P'}, \mathcal{V}^\perp_{EE'})$ (using Tellegen's Theorem), i.e., to the rigidity of $\mathcal{N}_P^{adj} := (\mathcal{V}^v(\mathcal{G}_{EP}) \oplus (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}, (\mathcal{V}^\perp_{EE'})(-E')E)$.

**Problem 34.** Let the multiport behaviour $\tilde{\mathcal{A}}_{PP'}$ be the solution space of the equation $Bv_P - Qi_{P'} = s$, with linearly independent rows. Let the dual multiport behaviour $\tilde{\mathcal{V}}_{PP'}$ be the solution space of equation $B'v_P - Q'i_{P'} = 0$, where the rows of $(B' | -Q')$ form a basis for the space complementary orthogonal to the row space of $(B' | -Q)$.

1. Show that the adjoint multiport behaviour $\tilde{\mathcal{V}}_{PP'}^{adj}$ is $Q'v_P + B'i_{P'} = 0$.

2. The constraints of the primal and dual multiport behaviours together give the following equation. Show that this equation has a unique solution.

$$ \begin{pmatrix} B & \cdots & -Q \\ B' & \cdots & -Q' \end{pmatrix} \begin{pmatrix} v_P \\ i_{P'} \end{pmatrix} = \begin{pmatrix} s \\ 0 \end{pmatrix}. \qquad (33) $$

*Answer*

1. We have $\tilde{\mathcal{V}}_{PP'}^{adj} = (\tilde{\mathcal{V}}_{PP'}^\perp)(-P')P$. Therefore the constraint of $\tilde{\mathcal{V}}_{PP'}^{adj}$ is $B'(-i_{P'}) - Q'v_P = 0$, i.e., the constraint is $Q'v_P + B'i_{P'} = 0$.

2. Suppose $(\lambda_1 \quad \lambda_2) \begin{pmatrix} B & -Q \\ B' & -Q' \end{pmatrix} = 0$. Since it is given that the rows of $(B | -Q)$ and the rows of $(B' | -Q')$ are linearly independent, neither $\lambda_1$, nor $\lambda_2$ can be zero. But then the real nonzero vector $(\lambda_1) (B | -Q) = -\lambda_2 (B' | -Q')$ is orthogonal to itself, a contradiction. We conclude the rows of the coefficient matrix of Equation 33 are linearly independent. Further, for this matrix, the number of rows equals the number of columns, since for any vector space $\mathcal{V}_S$, $r(\mathcal{V}_S) + r(\mathcal{V}_S^\perp) = |S|$. It follows that Equation 33 has a unique solution.
**Definition 31.** We say $\mathcal{V}_{E\hat{E}E'\hat{E}'}$ is a gyrometer iff $v_E = -Ri_{\hat{E}'}$; $v_{\hat{E}} = Ri_{E'}$, where $E, \hat{E}, E', \hat{E}'$ are pairwise disjoint copies of each other and $R$ is a positive diagonal matrix. We denote by $g^{E\hat{E}}$, the unit gyrometer where $R$ is the identity matrix, denote by $g_{tv}^{E\hat{E}}$, the unit gyrometer accompanied by a voltage source, the device with characteristic $v_E + \mathcal{E}_t = -i_{\hat{E}'}$; $v_{\hat{E}} = i_{E'}$, where $\mathcal{E}_t$ is the column vector with $\mathcal{E}(j) = 0, j \neq t, \mathcal{E}(j) = 1, j = t$, $g_{ti}^{E\hat{E}}$, the unit gyrometer accompanied by a current source, the device with characteristic $v_E = -i_{\hat{E}'}$; $v_{\hat{E}} = i_{E'} + \mathbf{J}_t$, where $\mathbf{J}_t$ is the column vector with $\mathbf{J}(j) = 0, j \neq t, \mathcal{E}(j) = 1, j = t$.

**Problem 35.** Let the multiport behaviour $\mathcal{A}_{PP'}$ be defined by the equation $Bv_P - Qi_{P'} = s$, with linearly independent rows. Its vector space translate $\mathcal{V}_{PP'}$ is defined by the equation $Bv_P - Qi_{P'} = 0$. Let $\mathcal{V}_{PP'}$ be defined by $B'v_P - Q'i_{P'} = 0$. Then $\mathcal{V}_{PP'}^{adj}$ is defined by $Q'v_P + B'i_{P'} = 0$. Let $P, P', \tilde{P}, \tilde{P}'$ be pairwise disjoint copies of each other. Show that each of $(\mathcal{A}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP', (\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP', (\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP', (\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP' \text{ is a single vector and therefore also that each of } (\mathcal{A}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP' \text{ is a single vector.}$

Answer

The constraint of $\mathcal{A}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}$ is

$$ \begin{pmatrix} B & 0 & -Q & 0 \\ I & 0 & 0 & I \\ 0 & I & -I & 0 \\ 0 & Q' & 0 & B' \end{pmatrix} \begin{pmatrix} v_P \\ v_{\tilde{P}} \\ i_{P'} \\ i_{\tilde{P}'} \end{pmatrix} = \begin{pmatrix} s \\ 0 \\ 0 \\ 0 \end{pmatrix}. \qquad (34) $$

This is equivalent to

$$ \begin{pmatrix} B & 0 & -Q & 0 \\ I & 0 & 0 & I \\ 0 & I & -I & 0 \\ B' & 0 & -Q' & 0 \end{pmatrix} \begin{pmatrix} v_P \\ v_{\tilde{P}} \\ i_{P'} \\ i_{\tilde{P}'} \end{pmatrix} = \begin{pmatrix} s \\ 0 \\ 0 \\ 0 \end{pmatrix}. \qquad (35) $$

Therefore the constraint of $(\mathcal{A}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g^{P\tilde{P}}) \circ PP'$ is

$$ \begin{pmatrix} B & -Q \\ B' & -Q' \end{pmatrix} \begin{pmatrix} v_P \\ i_{P'} \end{pmatrix} = \begin{pmatrix} s \\ 0 \end{pmatrix}. \qquad (36) $$

Arguing as in Problem 34, Equation 36 has a unique solution. Therefore Equations 35, 34 have a unique solution.

It is clear that the coefficient matrix of the constraint for $(\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g_{tv}^{P\tilde{P}}) \circ PP', (\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g_{ti}^{P\tilde{P}}) \circ PP'$ is the same as the coefficient matrix in Equation 36. Therefore each of these is a single vector. Arguing as above, $(\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g_{tv}^{P\tilde{P}}), (\mathcal{V}_{PP'} \cap (\mathcal{V}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap g_{ti}^{P\tilde{P}})$ are also single vectors.

**Definition 32.** Let $\mathcal{N}_{P_1 P_2} := (\mathcal{V}_{E_1 P_1 P_2 E'_1 P'_1 P'_2}, \mathcal{K}_{E_1 E'_1}^1)$, $\mathcal{N}_{P_2 P_3} := (\mathcal{V}_{E_2 P_2 P_3 E'_2 P'_2 P'_3}, \mathcal{K}_{E_2 E'_2}^2)$ be multiports, with $E_1, E'_1, E_2, E'_2, P_1, P_2, P'_1, P'_2, P_3, P'_3$ being pairwise disjoint. The multiport $\mathcal{N}_{P_1 P_3} = \mathcal{N}_{P_1 P_2} \cap \mathcal{N}_{P_2 P_3}$ is defined to be the multiport obtained by putting the ports $P_2$ of $\mathcal{N}_{P_1 P_2}, \mathcal{N}_{P_2 P_3}$ in parallel, i.e., voltages of corresponding ports of the two multiports set equal and the currents of corresponding ports of the two multiports set to be negatives of each other. Formally

$$ \mathcal{N}_{P_1 P_3} = \mathcal{N}_{P_1 P_2} \cap \mathcal{N}_{P_2 P_3} = ((\mathcal{V}_{E_1 P_1 P_2 E'_1 P'_1 P'_2} \cap \mathcal{V}_{E_2 P_2 P_3 E'_2 P'_3}(-P'_2)P'_3) \circ E_1 P_1 E'_1 P'_1 E_2 P_3 E'_2 P'_3, \mathcal{K}_{E_1 E'_1}^1 \oplus \mathcal{K}_{E_2 E'_2}^2). $$
When there are no common ports $P_2$, we refer to $\mathcal{N}_{P_1} \cap \mathcal{N}_{P_3}$ by $\mathcal{N}_{P_1} \oplus \mathcal{N}_{P_3}$.

**Problem 36.** Let $\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'})$ be a rigid affine multiport with $\mathcal{V}_{EPE'P'}^{adj} = \mathcal{V}_{EPE'P'}$ and let $\hat{E}, \hat{P}$ be copies of $E, P$, respectively with $E, P, \hat{E}, \hat{P}, E', P', \hat{E}, \hat{P}, \hat{E}', \hat{P}'$ being pairwise disjoint.

Let $\mathcal{N}_P^{adj} := ((\mathcal{V}_{EPE'P'})_{\tilde{E}\tilde{P}\tilde{E}'\tilde{P}'}, (\mathcal{V}_{EE'}^{adj})_{\tilde{E}\tilde{E}'})$. We study the networks

$$ (\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap g^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap g_{tv}^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap g_{ti}^{P\tilde{P}} \text{ in this problem. Prove the following.} $$
<figure><img src="image_5.png" /><figcaption>Figure 4: To illustrate the procedure of generalized Thevenin-Norton theorem</figcaption></figure>

1. The restrictions $(v_P, -i_{P'}), (v_P^{tv}, -i_{P'}^{tv}), (v_P^{ti}, -i_{P'}^{ti})$, to $P \uplus P'$ of the solutions of networks $(\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{tv}^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{ti}^{P\tilde{P}}$, for $t = 1, \dots, |P|$ are unique. Therefore the solutions of these networks are unique.

2. The vectors $(v_P^{tv}, i_{P'}^{tv}), (v_P^{ti}, i_{P'}^{ti})$, $t = 1, \dots, |P|$, span $\check{\mathcal{V}}_{PP'}$ and $\mathcal{A}_{PP'} = (v_P, i_{P'}) + \check{\mathcal{V}}_{PP'}$.

3. Generalize Thevenin-Norton Theorem for rigid multiports.

Answer

1. Let $\mathcal{N}_P := (\mathcal{V}_{EPE'P'}, \mathcal{A}_{EE'})$ and let $\mathcal{V}_{EE'}$ be the vector space translate of $\mathcal{A}_{EE'}$. Since $\mathcal{N}_P$ is rigid, by Theorem 28, so are $\mathcal{N}_P^{hom}, \mathcal{N}_{\tilde{P}}^{adj}$. The port behaviour of $\mathcal{N}_P$ is $\mathcal{A}_{PP'} = (\mathcal{V}_{EPE'P'} \leftrightarrow \mathcal{A}_{EE'})(-P')P$, with vector space translate $\check{\mathcal{V}}_{PP'}$. The port behaviours of $\mathcal{N}_P^{hom}, \mathcal{N}_{\tilde{P}}^{adj}$ are respectively $\check{\mathcal{V}}_{PP'}, \check{\mathcal{V}}_{\tilde{P}\tilde{P}'}^{adj}$ (see Problem 30). We saw in Problem 35 that each of

$(\mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap \mathbf{g}^{P\tilde{P}}) \circ PP', (\check{\mathcal{V}}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap \mathbf{g}_{tv}^{P\tilde{P}}) \circ PP'$,

$(\check{\mathcal{V}}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} \cap \mathbf{g}_{ti}^{P\tilde{P}}) \circ PP'$ is a single vector. These vectors are the restrictions

$(v_P, -i_{P'}), (v_P^{tv}, -i_{P'}^{tv}), (v_P^{ti}, -i_{P'}^{ti})$, to $P \uplus P'$ of the solutions of networks

$(\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{tv}^{P\tilde{P}}, (\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{ti}^{P\tilde{P}}$. By the constraints of $\mathbf{g}^{P\tilde{P}}, \mathbf{g}_{tv}^{P\tilde{P}}, \mathbf{g}_{ti}^{P\tilde{P}}$, the restrictions of these solutions to $\tilde{P} \uplus \tilde{P}'$ are unique and equal to $(v_{\tilde{P}}, -i_{\tilde{P}'})$, $(v_{\tilde{P}}^{tv}, -i_{\tilde{P}'}^{tv})$, $(v_{\tilde{P}}^{ti}, -i_{\tilde{P}'}^{ti})$.

Since the multiports $\mathcal{N}_P, \mathcal{N}_{\tilde{P}}^{hom}, \mathcal{N}_{\tilde{P}}^{adj}$ are rigid, for a given port condition $(\check{v}_P, \check{i}_P)$, we have a unique solution $(\hat{v}_E, \check{v}_P, \hat{i}_{E'}, -\check{i}_{P'})$, $(\check{v}_E^a, \check{v}_P^a, \check{i}_{E'}^a, -\check{i}_{P'}^a)$ of $\mathcal{N}_P, \mathcal{N}_{\tilde{P}}^{adj}$, respectively and for a given port condition $(v_P, i_P)$, we have a unique solution $(v_E, v_P, i_{E'}, -i_{P'})$, $(v_E^a, v_P^a, i_{E'}^a, -i_{P'}^a)$ of $\mathcal{N}_P^{hom}, \mathcal{N}_{\tilde{P}}^{adj}$, respectively.

Therefore solutions of $(\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}^{P\tilde{P}}, (\mathcal{N}_{\tilde{P}}^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{tv}^{P\tilde{P}}, (\mathcal{N}_{\tilde{P}}^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}) \cap \mathbf{g}_{ti}^{P\tilde{P}}$, for $t = 1, \dots, |P|$ are unique.

2. Below, we prove in brief that vectors $(v_P^{tv}, i_{P'}^{tv}), (v_P^{ti}, i_{P'}^{ti}), t = 1, \dots, |P|$, span $\check{\mathcal{V}}_{PP'}$ and $\mathcal{A}_{PP'} = (v_P, i_{P'}) + \check{\mathcal{V}}_{PP'}$. More details may be found in [13].
Let $\check{\mathcal{V}}_{PP'}$ be the solution space of $Bv_P - Qi_{P'} = 0$ and let $(\check{\mathcal{V}}_{PP'}^{adj})_{\tilde{P}\tilde{P}'} = (\check{\mathcal{V}}_{PP'}^{\perp})_{(-\tilde{P}')\tilde{P}}$, be the solution space of $Q'v_P + B'\hat{i}_{\tilde{P}'} = 0$, where $(B'| - Q'), (B'| - Q')$ have linearly independent rows and span complementary orthogonal spaces. Let $(\hat{v}_P^{tv}, -\hat{i}_P^{tv}), (\hat{v}_P^{ti}, -\hat{i}_P^{ti})$, be respectively restriction of a solution of $[\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}] \cap \mathbf{g}_{tv}^{P\tilde{P}}$ and of $[\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}] \cap \mathbf{g}_{ti}^{P\tilde{P}}$. Let $(\hat{v}_P, \hat{i}_{P'})$ be a vector in $\check{\mathcal{V}}_{PP'}$. It can be seen that $(\hat{v}_P^{tv}, \hat{i}_P^{tv}), (\hat{v}_P^{ti}, \hat{i}_P^{ti}), (\hat{v}_P, \hat{i}_{P'})$ are respectively solutions of the following equations. (We denote by $I^t$, the $t^{th}$ column of the identity matrix $I$.)

$$ \begin{pmatrix} B & -Q \\ B' & -Q' \end{pmatrix} \begin{pmatrix} v_P \\ i_{P'} \end{pmatrix} = \begin{pmatrix} 0 \\ -B' I^t \end{pmatrix}, \begin{pmatrix} B & -Q \\ B' & -Q' \end{pmatrix} \begin{pmatrix} v_P \\ i_{P'} \end{pmatrix} = \begin{pmatrix} 0 \\ Q' I^t \end{pmatrix}, \begin{pmatrix} B & -Q \\ B' & -Q' \end{pmatrix} \begin{pmatrix} v_P \\ i_{P'} \end{pmatrix} = \begin{pmatrix} 0 \\ x \end{pmatrix} \quad (37) $$

for some vector $x$. Since the vector $x$ is a linear combination of the columns of $(B'| - Q')$, it follows that $(\hat{v}_P, \hat{i}_{P'})$ is a linear combination of $(\hat{v}_P^{tv}, \hat{i}_P^{tv}), (\hat{v}_P^{ti}, \hat{i}_P^{ti})$, as $t$ takes values $1, \dots, |P|$.

3. We summarize our generalization of **Thevenin-Norton Theorem** for rigid multiports below. Step 1. Compute the unique solution of $[\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{adj}] \cap \mathbf{g}^{P\tilde{P}}$. Restriction to port variables (changing sign of $i_{P'}$) yields a vector of $\check{\mathcal{A}}_{PP'}$.

Step 2. For $t = 1, \dots, |P|$, compute the unique solutions of $[\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}] \cap \mathbf{g}_{tv}^{P\tilde{P}}, [\mathcal{N}_P^{hom} \oplus \mathcal{N}_{\tilde{P}}^{adj}] \cap \mathbf{g}_{ti}^{P\tilde{P}}$. Restriction to port variables (changing sign of $i_{P'}$) yields a generating set of $\check{\mathcal{V}}_{PP'}$.

**Problem 37. Why is the generalization of Thevenin-Norton Theorem required?**

*Answer*

Given the constraints of an affine multiport $\mathcal{N}_P$, one can always use linear algebraic methods to either compute $\check{\mathcal{A}}_{PP'}$ or prove that the constraints do not have a solution. Both the Thevenin-Norton theorem as well as our generalization proceed under the assumption that the calculation must be by repeated solution of networks resulting from suitable terminations of $\mathcal{N}_P$. This has the advantage that we can use the very efficient circuit simulators which are currently available.

Usual method of computing Thevenin-Norton equivalent assumes that the port characteristic has the hybrid form

$$ \begin{pmatrix} v_{P_1} \\ i_{P_2} \end{pmatrix} = \begin{pmatrix} h_{11} & h_{12} \\ h_{21} & h_{22} \end{pmatrix} \begin{pmatrix} i_{P_1} \\ v_{P_2} \end{pmatrix} + \begin{pmatrix} s_1 \\ s_2 \end{pmatrix}, \quad (38) $$

where the port edges are partitioned into $P_1, P_2$. One then computes the matrix $\begin{pmatrix} h_{11} & h_{12} \\ h_{21} & h_{22} \end{pmatrix}$ and the vector $\begin{pmatrix} s_1 \\ s_2 \end{pmatrix}$ as follows.

1. Set all internal sources to zero, keep one port at a time 'active' and the rest inactive. Solve the resulting circuit and determine $\begin{pmatrix} v_{P_1} \\ i_{P_2} \end{pmatrix}$. This would yield the relevant column of $\begin{pmatrix} h_{11} & h_{12} \\ h_{21} & h_{22} \end{pmatrix}$. Keeping a port $p_k$ in $P_1$ active means that $i_{p_k} = 1, i_{p_j} = 0, p_j \in P_1, j \neq k, v_{p_j} = 0, p_j \in P_2$, and keeping a port $p_k$ in $P_2$ active means that $v_{p_k} = 1, v_{p_j} = 0, p_j \in P_2, j \neq k, i_{p_j} = 0, p_j \in P_1$.

2. Set $\begin{pmatrix} i_{P_1} \\ v_{P_2} \end{pmatrix} = 0$, i.e., open circuit ports in $P_1$ and short circuit ports in $P_2$. Solve the resulting circuit and determine $\begin{pmatrix} v_{P_1} \\ i_{P_2} \end{pmatrix}$. This would yield $\begin{pmatrix} s_1 \\ s_2 \end{pmatrix}$.

It is not immediately clear how one should proceed if hybrid form exists for the given multiport but the partition $P_1, P_2$ is unknown, or if the hybrid form is not known to exist for the given multiport.

1. In our generalization, we assume the given multiport is rigid. If at any stage of our procedure the circuit simulator gives an error message, it means that this assumption is wrong. Rigid multiports are
an extremely general class of affine multiports. They permit the translate $\mathcal{V}_{PP'}$ of $\mathcal{A}_{PP'}$ to have rank varying from 0 to $2|P|$, whereas Thevenin-Norton theorem permits the rank of $\mathcal{V}_{PP'}$ to be only $|P|$ and further $\mathcal{V}_{PP'}^\perp$ has to have the hybrid form $$ \begin{pmatrix} I_{P_1} & 0_{P'_1} & -h_{1P'_1} & -h_{1P'_2} \\ 0_{P_2} & I_{P'_2} & -h_{2P'_1} & -h_{2P'_2} \end{pmatrix} $$

2. Thevenin-Norton theorem uses only two types of terminations: open circuiting ports or short circuiting ports. Even when the multiport is rigid these terminations may not yield a network with unique solution (see part 2 of Problem 19) so that the circuit simulator may output an error message.

## 11. Stationarity of power transfer for affine multiports

*(This section depends on Section 10.)*

The original version of the maximum power transfer theorem states that a linear 1-port transfers maximum power to a load, if the latter has value equal to the adjoint (conjugate transpose) of the Thevenin impedance of the 1-port. In the multiport case, the Thevenin equivalent is an impedance matrix whose adjoint has to be connected to the multiport for maximum power transfer. These should be regarded as restricted forms of the theorem since they do not handle the case where the Thevenin equivalent does not exist. In this subsection our aim is to prove a general version of maximum power transfer theorem for affine multiports: we show that the maximum power transfer possible at the ports, occurs when we terminate the affine multiport by its adjoint through an ideal transformer. Since we deal with general affine multiports, we can only hope for stationarity of power transfer. We follow [17] for the material in this subsection.

**Notation** We fix some preliminary notation needed for the discussion of the maximum power transfer theorem. For any matrix $Q$, we take $\overline{Q}$ to be the conjugate. When $x_S, y_S$ are complex vectors the inner product $\langle\langle x_S, y_S \rangle\rangle := \sum_{e \in S} x(e)y(e)$, whereas the dot product $\langle x_S, y_S \rangle := \sum_{e \in S} x(e)y(e)$. We assume that the port behaviour $\mathcal{A}_{PP'}$ is over the complex field. As usual $\mathcal{V}_{PP'}$ would denote its vector space translate. We denote $\mathcal{V}_{PP'}^\perp$ by $\mathcal{V}_{PP'}^*$. The adjoint $\mathcal{A}_{PP'}^{adj}$ in this case is $(\mathcal{V}_{PP'}^*)(-P')P$. Our convention for the sign of power associated with a multiport behaviour is that when $(\check{v}_P, \check{i}_{P'}) \in \mathcal{A}_{PP'}$, the **power absorbed** by the multiport behaviour $\mathcal{A}_{PP'}$ is $(\langle\langle \check{v}_P, \check{i}_{P'} \rangle\rangle + \langle\langle \check{i}_{P'}, \check{v}_P \rangle\rangle) = \check{v}_P^T \check{\check{i}}_{P'} + \check{i}_{P'}^T \check{\overline{v}_P} = \overline{\check{v}_P^T \check{i}_{P'}} + \overline{\check{i}_{P'}^T \check{v}_P}$. (We omit the scale factor $\frac{1}{2}$ for better readability of the expressions involved.) The **power delivered** by it, is therefore the negative of this quantity.

**Problem 38.** Let the port behaviour $\mathcal{A}_{PP'}$ of multiport $N_P$ be defined by $B\check{v}_P - Q\check{i}_{P'} = s$. The maximum power transfer problem is

$$ \text{minimize} \quad (\overline{\check{v}_P^T \check{i}_{P'}} + \overline{\check{i}_{P'}^T \check{v}_P}) \qquad (39) $$

$$ (\check{v}_P, \check{i}_{P'}) \in \mathcal{A}_{PP'}, \text{ or equivalently, } B\check{v}_P - Q\check{i}_{P'} = s. \qquad (40) $$

We say $(\check{v}_P^{stat}, \check{i}_{P'}^{stat})$, is a stationary point for the maximum power transfer problem iff the stationarity condition

$$ (\check{i}_{P'}^{stat})^T \delta \check{v}_P + (\check{v}_P^{stat})^T \delta \overline{\check{i}_{P'}} + (\overline{\check{i}_{P'}^{stat}})^T \delta \check{v}_P + (\overline{\check{v}_P^{stat}})^T \delta \overline{\check{i}_{P'}} = 0, \qquad (41) $$

for every vector $(\delta \check{v}_P, \delta \check{i}_{P'})$, such that $(B(\delta \check{v}_P) - Q(\delta \check{i}_{P'})) = 0$. Prove the following.

**Theorem 33.** 1. $(\check{v}_P^{stat}, \check{i}_{P'}^{stat})$, is a stationary point for the maximum power transfer problem iff, for some vector $\lambda$, $((\check{v}_P^{stat})^T | (\check{i}_{P'}^{stat})^T) - \lambda^T(-\overline{Q}|\overline{B}) = 0$.

2. The stationarity condition is equivalent to each of the following statements:

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

$$ (B - Q) \begin{pmatrix} -\overline{Q}^T \\ \overline{B}^T \end{pmatrix} \lambda = s, \qquad (42) $$
• $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ belongs to $\mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')}.$

3. In the case where the multiport has a Thevenin impedance Z and Thevenin voltage E, the above stationarity condition reduces to the condition $(Z + \bar{Z}^T)(-\check{i}_{P'}^{\text{stat}}) = E$.

Answer

*Proof.* 1. When $x_S, y_S$ are complex vectors the inner product $\langle\langle x_S, y_S \rangle\rangle := \sum_{e \in S} x(e)y(e)$, whereas the dot product $\langle x_S, y_S \rangle := \sum_{e \in S} x(e)y(e)$. Thus $\langle\langle x_S, y_S \rangle\rangle = 0$ iff $\langle \bar{x}_S, y_S \rangle = 0 = \langle \bar{y}_S, x_S \rangle$. It is clear that the inner product $\langle\langle x_S, y_S \rangle\rangle$ is zero iff $\langle\langle y_S, x_S \rangle\rangle$ is zero. From this it follows that $\langle\langle x_S, y_S \rangle\rangle$ is zero iff $\langle\langle x_S, y_S \rangle\rangle + \langle\langle y_S, x_S \rangle\rangle$ is zero, i.e., $\bar{x}_S, y_S$ as well as $x_S, \bar{y}_S$ are orthogonal iff $\langle\langle x_S, y_S \rangle\rangle + \langle\langle y_S, x_S \rangle\rangle$ is zero. Therefore the stationarity condition is equivalent to $(\check{i}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ being orthogonal to every vector $(\delta\check{v}_P, \delta\check{i}_{P'})$, such that $(B(\delta\check{v}_P) - Q(\delta\check{i}_{P'})) = 0 = (\bar{B}(\delta\bar{v}_P) - \bar{Q}(\delta\bar{i}_P))$. It follows that the stationarity condition is equivalent to $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ belonging to the row space of $(-\bar{Q}|\bar{B})$, i.e., to the condition that for some vector $\lambda$, $((\check{v}_P^{\text{stat}})^T | (\check{i}_P^{\text{stat}})^T) - \lambda^T(-\bar{Q}|\bar{B}) = 0$. Thus the stationarity at $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$, is equivalent to $((\check{v}_P^{\text{stat}})^T | (\check{i}_{P'}^{\text{stat}})^T) - \lambda^T(-\bar{Q}|\bar{B}) = 0$.

2. Since $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}) \in \mathcal{A}_{PP'}$, we must have $B\check{v}_P^{\text{stat}} - Q\check{i}_{P'}^{\text{stat}} = s$, and the stationarity condition reduces to $(B - Q)\begin{pmatrix} -\bar{Q}^T \\ \bar{B}^T \end{pmatrix} = s$. The vector space translate, $\check{\mathcal{V}}_{PP'}$ of $\mathcal{A}_{PP'}$ is the solution space of the equation, $B\check{v}_P - Q\check{i}_{P'} = 0$, and $(\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')} := (\check{\mathcal{V}}_{PP'}^*)_{P'P}$, is the row space of $(-\bar{Q}|\bar{B})$. Thus, the stationarity condition says that $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ belongs to $\mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')}.$

3. In the case where the multiport has a Thevenin equivalent, its port behaviour would have the form
$\check{v}_P = Z\check{i}_{P'} + E$, i.e., the form $\check{v}_P - Z\check{i}_{P'} = E$, so that the stationarity condition reduces to $(I - Z)\begin{pmatrix} -\bar{Z}^T \\ I \end{pmatrix} = E$, i.e., to $(Z + \bar{Z}^T)(-\lambda) = E$. The condition $((\check{i}_{P'}^{\text{stat}})^T | (\check{v}_P^{\text{stat}})^T) - \lambda^T(\bar{B} - \bar{Q}) = 0$ reduces to $((\check{i}_{P'}^{\text{stat}})^T | (\check{v}_P^{\text{stat}})^T) - \lambda^T(I - \bar{Z}) = 0$, so that $-\lambda = -\check{i}_{P'}^{\text{stat}}$ and $\check{v}_P^{\text{stat}} = \bar{Z}^T(-\check{i}_{P'}^{\text{stat}})$. Thus $-\lambda$ is the current flowing out of the multiport when we terminate it by $\bar{Z}^T$. $\square$

**Problem 39.** We note that, even when the multiport is rigid, Equation 42 may have no solution, in which case we have no stationary vectors for power transfer. If the equation has a unique solution, using that $\lambda$ vector we get a unique stationary vector $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$. Show that the stationarity condition is achieved at the ports of the multiport $\mathcal{N}_P$, if we terminate it by $\mathcal{N}_{\bar{P}}^{\text{adj}}$ through the ideal transformer $\mathbf{T}^{\bar{P}}$ resulting in the network $[\mathcal{N}_P \oplus \mathcal{N}_{\bar{P}}^{\text{adj}}] \cap \mathbf{T}^{\bar{P}}$, where the ideal transformer $\mathbf{T}^{\bar{P}}$ satisfies the equations $v_P = v_{\bar{P}}; i_P = -i_{\bar{P}}$.

Answer

**Theorem 34.** Let $\mathcal{N}_P$, on directed graph $\mathcal{G}_{EP}$ and device-characteristic $\mathcal{A}_{EE'}$, have the port behaviour $\mathcal{A}_{PP'}$. Let $\mathcal{V}_{EE'}$, $\check{\mathcal{V}}_{PP'}$ be the vector space translates of $\mathcal{A}_{EE'}$, $\mathcal{A}_{PP'}$, respectively. Let $\mathcal{N}_{\bar{P}}^{\text{adj}}$ be on the disjoint copy $\mathcal{G}_{\bar{E}\bar{P}}$ of $\mathcal{G}_{EP}$, with device-characteristic $\mathcal{V}_{\bar{E}\bar{E}'}^{\text{adj}} := (\mathcal{V}_{EE'}^{\text{adj}})_{\bar{E}\bar{E}'}$. Let $(v_P^1, -i_{P'}^1)$ be the restriction of a solution of the multiport $\mathcal{N}_P$, to $P \uplus P'$. Then $(v_P^1, i_{P'}^1)$ satisfies the stationarity condition with respect to the power absorbed by $\mathcal{A}_{PP'}$ iff $(v_P^1, -i_{P'}^1)$ is the restriction of a solution of the network $[\mathcal{N}_P \oplus \mathcal{N}_{\bar{P}}^{\text{adj}}] \cap \mathbf{T}^{\bar{P}}$, to $P \uplus P'$.

*Proof.* The restriction of the set of solutions of $\mathcal{N}_P$ on graph $\mathcal{G}_{EP}$ to $P \uplus P'$, is $[(\mathcal{V}_{EP} \oplus (\mathcal{V}_{\bar{E}P}^*)_{E'P'}) \cap \mathcal{A}_{EE'}] \circ PP'$. This is the same as $(\mathcal{A}_{PP'}^{\text{adj}})_{P(-P')}$.

The restriction of the set of solutions of $\mathcal{N}_{\bar{P}}^{\text{adj}}$ on the disjoint copy $\mathcal{G}_{\tilde{E}\tilde{P}}$ of $\mathcal{G}_{EP}$, to $\tilde{P} \uplus \tilde{P}'$ is $[(\mathcal{V}_{\tilde{E}\tilde{P}} \oplus (\mathcal{V}_{\bar{E}\tilde{P}}^*)_{\tilde{E}'\tilde{P}'}) \cap \mathcal{V}_{\bar{E}\tilde{E}'}^{\text{adj}}] \circ \tilde{P}\tilde{P}'$. This we know, by use of Theorem 2 (see Problem 30), to be the same as $(\check{\mathcal{V}}_{PP'}^{\text{adj}})_{\tilde{P}-\tilde{P}'}$.
We thus have, $$ ((\mathcal{V}_{\tilde{E}\tilde{P}} \oplus (\mathcal{V}_{\tilde{E}\tilde{P}}^* \tilde{E}'\tilde{P}')) \cap \mathcal{V}_{\tilde{E}\tilde{E}'}^{\text{adj}}) \cap \mathbf{T}^{\tilde{P}\tilde{P}} ] \circ PP' = [ ((\mathcal{V}_{\tilde{E}\tilde{P}} \oplus (\mathcal{V}_{\tilde{E}\tilde{P}}^* \tilde{E}'\tilde{P}')) \cap \mathcal{V}_{\tilde{E}\tilde{E}'}^{\text{adj}}) \circ \tilde{P}\tilde{P}']_{P(-P')} $$
= $\check{\mathcal{V}}_{PP'}^{\text{adj}}$, since vectors in $\mathbf{T}^{\tilde{P}\tilde{P}}$ are precisely the ones that satisfy $v_P = v_{\tilde{P}'}, i_{P'} = -i_{\tilde{P}'}$.

The restriction of the set of solutions of $[\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{\text{adj}}] \cap \mathbf{T}^{\tilde{P}\tilde{P}}$, to $P \uplus P'$ is therefore equal to

$$ [[(\mathcal{V}_{EP} \oplus (\mathcal{V}_{EP}^*_{E'P'})) \cap \mathcal{A}_{EE'}] \circ PP'] \cap [[(\mathcal{V}_{\tilde{E}\tilde{P}} \oplus (\mathcal{V}_{\tilde{E}\tilde{P}}^* \tilde{E}'\tilde{P}')) \cap \mathcal{V}_{\tilde{E}\tilde{E}'}^{\text{adj}} \cap \mathbf{T}^{\tilde{P}\tilde{P}}] \circ PP'] $$

= $(\mathcal{A}_{PP'}^*_{P(-P')}) \cap \check{\mathcal{V}}_{PP'}^{\text{adj}} = [\mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')}]_{P(-P')}. From the discussion preceding the theorem we know that $\mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')}$ is the collection of all vectors that satisfy the stationarity condition with respect to the power absorbed by $\mathcal{A}_{PP'}$. This proves the result. $\square$

### 11.1. Maximum Power Transfer Theorem for passive multiports

In this subsection we show that the stationarity conditions reduce to maximum power transfer conditions when the multiport is passive. Our vectors are over the complex field. The **power absorbed** by a vector $(v_E, i_{E'})$ is given by $\langle\langle v_E, i_{E'} \rangle\rangle + \langle\langle i_{E'}, v_E \rangle\rangle$. A vector space $\mathcal{V}_{EE'}$ is **passive**, iff the power absorbed by $(x_E, y_{E'})$ is nonnegative, whenever $(x_E, y_{E'}) \in \mathcal{V}_{EE'}$. It is **strictly passive** iff the power absorbed by every nonzero vector in $\mathcal{V}_{EE'}$ is positive. An affine space $\mathcal{A}_{EE'}$ is (strictly) passive iff its vector space translate is (strictly) passive. A multiport is (strictly) passive iff its port behaviour is (strictly) passive.

**Problem 40.** Prove the following result which links passivity of the device-characteristic of a multiport to its port behaviour. (We remind the reader that a cutset of a graph is a minimal set of edges which when deleted increases the number of connected components of the graph, equivalently, in the case of a connected graph, is a minimal set of edges not contained in any cotree.)

**Lemma 35.** Let $\mathcal{N}_P$ be a multiport on directed graph $\mathcal{G}_{EP}$ with device-characteristic $\mathcal{A}_{EE'}$.

1. If $\mathcal{A}_{EE'}$ is passive so is the port behaviour $\mathcal{A}_{PP'}$ of $\mathcal{N}_P$.

2. If $\mathcal{A}_{EE'}$ is strictly passive and $P$ contains no loops or cutsets of $\mathcal{G}_{EP}$, then the port behaviour $\mathcal{A}_{PP'}$ of $\mathcal{N}_P$ is also strictly passive.

**Answer**

*Proof.* 1. We assume that $\mathcal{A}_{PP'}$ is nonvoid. We have, $\mathcal{A}_{PP'} = ((\mathcal{V}_{EP} \oplus (\mathcal{V}_{EP}^*_{E'P'})) \leftrightarrow \mathcal{A}_{EE'}_{P(-P')}$, where $\mathcal{V}_{EP} := \mathcal{V}^v(\mathcal{G}_{EP})$.

By Tellegen's Theorem, $\mathcal{V}_{E'P'}^* = (\mathcal{V}^i(\mathcal{G}_{EP}))_{E'P'}$. By Theorem 6, it follows that the vector space translate of $\mathcal{A}_{PP'}$ is $\check{\mathcal{V}}_{PP'} = ((\mathcal{V}_{EP} \oplus (\mathcal{V}_{EP}^*_{E'P'})) \leftrightarrow \mathcal{V}_{EE'}_{P(-P')}$. Let $(v_P, -i_{P'})$ belong to $\check{\mathcal{V}}_{PP'}$. Then there exist $(v_E, v_P) \in \mathcal{V}_{EP}$ and $(i_{E'}, i_{P'}) \in (\mathcal{V}_{EP}^*_{E'P'})$, such that $(v_E, i_{E'}) \in \mathcal{V}_{EE'}$. By the orthogonality of $\mathcal{V}_{EP}, \mathcal{V}_{EP}^*$, it follows that $\langle\langle (v_E, v_P), (i_{E'}, i_{P'}) \rangle\rangle = \langle\langle v_E, i_{E'} \rangle\rangle + \langle\langle v_P, i_{P'} \rangle\rangle = 0$, and by the passivity of $\mathcal{V}_{EE'}$, it follows that $\langle\langle v_E, i_{E'} \rangle\rangle + \langle\langle i_{E'}, v_E \rangle\rangle \ge 0$. Therefore $\langle\langle v_P, -i_{P'} \rangle\rangle + \langle\langle -i_{P'}, v_P \rangle\rangle \ge 0$.

2. Without loss of generality, we assume that the graph $\mathcal{G}_{EP}$ is connected. If $P$ contains no cutset or circuit of $\mathcal{G}_{EP}$, then $E$ contains both a tree as well as a cotree of $\mathcal{G}_{EP}$. If the voltages assigned to the branches of a tree are zero, the branches in its complement will have zero voltage. Therefore $\mathcal{V}^v(\mathcal{G}_{EP}) \times P = \mathcal{V}_{EP} \times P$ must necessarily be a zero vector space. If the currents in the branches of a cotree are zero the branches in its complement will have zero current. Therefore $(\mathcal{V}^i(\mathcal{G}_{EP}) \times P)_{P'} = \mathcal{V}_{E'P'}^* \times P'$ must necessarily be a zero vector space. Now let $(v_P, -i_{P'}) \in \check{\mathcal{V}}_{PP'}$, $(v_P, -i_{P'}) \ne 0_{PP'}$. As in part 1 above, there exist $(v_E, v_P) \in \mathcal{V}_{EP}$ and $(i_{E'}, i_{P'}) \in \mathcal{V}_{EP}^*$, such that $(v_E, i_{E'}) \in \mathcal{V}_{EE'}$. Since $\mathcal{V}_{EP} \times P$ and $\mathcal{V}_{EP}^* \times P$ are both zero vector spaces, we must have that $(v_E, i_{E'}) \ne 0_{EE'}$ so that, by strict passivity of $\mathcal{V}_{EE'}$, we have $\langle\langle v_E, i_{E'} \rangle\rangle + \langle\langle i_{E'}, v_E \rangle\rangle > 0$. Further $\langle\langle (v_E, v_P), (i_{E'}, i_{P'}) \rangle\rangle = 0$, so that we can conclude $\langle\langle v_P, -i_{P'} \rangle\rangle + \langle\langle -i_{P'}, v_P \rangle\rangle > 0$. $\square$

**Problem 41.** 1. Prove the following result which states that when a port behaviour is passive or strictly passive, the stationarity condition implies a maximum power delivery condition.

**Theorem 36.** Let $\mathcal{N}_P$, on directed graph $\mathcal{G}_{EP}$ and with passive device-characteristic $\mathcal{A}_{EE'}$, have the port behaviour $\mathcal{A}_{PP'}$. Let $\mathcal{V}_{EE'}$ be the vector space translate of $\mathcal{A}_{EE'}$. Let $\mathcal{N}_{\tilde{P}}^{\text{adj}}$ be on the disjoint copy $\mathcal{G}_{\tilde{E}\tilde{P}}$ of $\mathcal{G}_{EP}$, with device-characteristic $\mathcal{V}_{\tilde{E}\tilde{E}'}^{\text{adj}}$.
(a) Let $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}) \in \mathcal{A}_{PP'}$. Then $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ satisfies

$$ \text{maximize} \quad \langle\langle\check{v}_P, -\check{i}_{P'}\rangle\rangle + \langle\langle -\check{i}_{P'}, \check{v}_P\rangle\rangle, \quad (\check{v}_P, \check{i}_{P'}) \in \mathcal{A}_{PP'}, \quad (43) $$

$$ \text{iff } (\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}) \in \mathcal{A}_{PP'} \cap (\check{\mathcal{V}}_{PP'}^{\text{adj}})_{P(-P')}. $$

(b) Let $(\check{v}_P^{\text{stat}}, -\check{i}_{P'}^{\text{stat}})$ be the restriction of a solution of the multiport $\mathcal{N}_P$, to $P \uplus P'$. Then $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ satisfies the optimization condition in Equation 43, iff $(\check{v}_P^{\text{stat}}, -\check{i}_{P'}^{\text{stat}})$ is the restriction of a solution of the network $[\mathcal{N}_P \oplus \mathcal{N}_{\tilde{P}}^{\text{adj}}] \cap \mathbf{T}^{P\tilde{P}}$, to $P \uplus P'$.

## 2. When the multiport is strictly passive show that the maximum power transfer port condition is unique.

### Answer

**Proof.** (a) We take into account second order terms, to show that the stationarity condition implies a maximum power delivery condition.

Let $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}) \in \mathcal{A}_{PP'}$, satisfy the stationarity condition $((\check{v}_P^{\text{stat}})^T, (\check{i}_{P'}^{\text{stat}})^T) = \lambda^T(-\overline{Q}|\overline{B})$, for some $\lambda$. For any $(\check{v}_P, \check{i}_{P'}) \in \mathcal{A}_{PP'}$, i.e., such that $B\check{v}_P - \check{Q}\check{i}_{P'} = s$, we can write $(\check{v}_P, \check{i}_{P'}) = (\check{v}_P^{\text{stat}} + \Delta\check{v}_P, \check{i}_{P'}^{\text{stat}} + \Delta\check{i}_{P'})$. We then have $B\Delta\check{v}_P - Q\Delta\check{i}_{P'} = 0$ and $[\overline{B}(\Delta\check{v}_P) - \overline{Q}(\Delta\check{i}_{P'})] = 0$. Therefore $\langle\langle\check{v}_P, \check{i}_{P'}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P\rangle\rangle = \langle\langle\check{v}_P, \check{i}_{P'}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P\rangle\rangle - \lambda^T[B(\Delta\check{v}_P) - Q(\Delta\check{i}_{P'})] - \lambda^T[\overline{B}(\Delta\check{v}_P) - \overline{Q}(\Delta\check{i}_{P'})] = \langle\langle\check{v}_P, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P^{\text{stat}}\rangle\rangle + (\Delta\check{v}_P)^T\check{i}_{P'}^{\text{stat}} + (\check{v}_P^{\text{stat}})^T(\Delta\check{i}_{P'}) + (\check{i}_{P'}^{\text{stat}})^T(\Delta\check{v}_P) + (\Delta\check{i}_{P'})^T\check{v}_P^{\text{stat}} + \langle\langle\Delta\check{v}_P, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\Delta\check{i}_{P'}, \Delta\check{v}_P\rangle\rangle - \lambda^T[\overline{B}(\Delta\check{v}_P) - \overline{Q}(\Delta\check{i}_{P'})] - \lambda^T[B(\Delta\check{v}_P) - Q(\Delta\check{i}_{P'})]$. We can rewrite the right side as

$$ \begin{aligned} & \langle\langle\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\Delta\check{v}_P, \check{i}_{P'}^{\text{stat}}\rangle\rangle + ((\check{v}_P^{\text{stat}})^T + \lambda^T\overline{Q})\overline{\Delta\check{i}_{P'}} + ((\check{i}_{P'}^{\text{stat}})^T - \lambda^T\overline{B})\overline{\Delta\check{v}_P} \\ & + \langle\langle\check{i}_{P'}^{\text{stat}}, \check{v}_P^{\text{stat}}\rangle\rangle + \langle\langle\Delta\check{i}_{P'}, \Delta\check{v}_P\rangle\rangle + ((\check{v}_P^{\text{stat}})^T + \lambda^T\overline{Q})\overline{\Delta\check{i}_{P'}} + ((\check{i}_{P'}^{\text{stat}})^T - \lambda^T\overline{B})\overline{\Delta\check{v}_P}. \\ \text{Applying the condition } ((\check{v}_P^{\text{stat}})^T, (\check{i}_{P'}^{\text{stat}})^T) = \lambda^T(-\overline{Q}|\overline{B}), \text{ this expression reduces to} \\ & \langle\langle\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\check{i}_{P'}^{\text{stat}}, \check{v}_P^{\text{stat}}\rangle\rangle + \langle\langle\Delta\check{v}_P, \Delta\check{i}_{P'}\rangle\rangle + \langle\langle\Delta\check{i}_{P'}, \Delta\check{v}_P\rangle\rangle. \text{ Therefore, } \langle\langle\check{v}_P, \check{i}_{P'}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P\rangle\rangle \\ & = \langle\langle\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\check{i}_{P'}^{\text{stat}}, \check{v}_P^{\text{stat}}\rangle\rangle + \langle\langle\Delta\check{v}_P, \Delta\check{i}_{P'}\rangle\rangle + \langle\langle\Delta\check{i}_{P'}, \Delta\check{v}_P\rangle\rangle. \end{aligned} $$

If $\mathcal{A}_{PP'}$ is passive we have $\langle\langle\Delta\check{v}_P, \Delta\check{i}_{P'}\rangle\rangle + \langle\langle\Delta\check{i}_{P'}, \Delta\check{v}_P\rangle\rangle \ge 0$, so that $\langle\langle\check{v}_P, \check{i}_{P'}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P\rangle\rangle \ge \langle\langle\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\check{i}_{P'}^{\text{stat}}, \check{v}_P^{\text{stat}}\rangle\rangle$.

Equivalently, the power delivered by $\mathcal{A}_{PP'}$, is maximum when $(\check{v}_P, \check{i}_{P'}) = (\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$.

If $\mathcal{A}_{PP'}$ is strictly passive we have $\langle\langle\check{v}_P, \check{i}_{P'}\rangle\rangle + \langle\langle\check{i}_{P'}, \check{v}_P\rangle\rangle > \langle\langle\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}}\rangle\rangle + \langle\langle\check{i}_{P'}^{\text{stat}}, \check{v}_P^{\text{stat}}\rangle\rangle$ whenever $(\Delta\check{v}_P, \Delta\check{i}_{P'}) \ne 0$, so that $(\check{v}_P^{\text{stat}}, \check{i}_{P'}^{\text{stat}})$ is the unique maximum delivery vector in $\mathcal{A}_{PP'}$.

By Lemma 35, if a multiport $\mathcal{N}_P$ is passive, so is its port behaviour. Therefore, Equation 42 also gives the condition for maximum power transfer from a passive $\mathcal{N}_P$. Part (a) now follows by using part 2 of Theorem 33.

(b) The result follows using Theorem 34.

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

2. Let $\check{\mathcal{V}}_{PP'}$ be strictly passive. If $(0_P, \check{i}_{P'})$ or $(v_P, 0_{P'})$ belongs to $\check{\mathcal{V}}_{PP'}$, its strict passivity is violated. Therefore $r(\check{\mathcal{V}}_{PP'} \times P)$ as well as $r(\check{\mathcal{V}}_{PP'} \times P')$ must be zero and consequently $r(\check{\mathcal{V}}_{PP'} \circ P')$ as well as $r(\check{\mathcal{V}}_{PP'} \circ P)$ must equal $|P|$, using Theorem 4. Let $(C_P|E_{P'})$ be the representative matrix of $\check{\mathcal{V}}_{PP'}$. It is clear that $C_P, E_{P'}$ are nonsingular so that by invertible row transformation, we can reduce $(C_P|E_{P'})$ to the form $(Z^T|I)$ or $(I|Y^T)$. We then have $\langle\langle v_P, \check{i}_{P'}\rangle\rangle + \langle\langle \check{i}_{P'}, v_P\rangle\rangle = v_P^T\check{i}_{P'} + \check{i}_{P'}^T\overline{v_P} = \check{i}_{P'}^T Z^T \check{i}_{P'} + \check{i}_{P'}^T Z \check{i}_{P'} = \langle\langle \check{i}_{P'}, (Z+Z^*)\check{i}_{P'}\rangle\rangle$. The strict passivity is equivalent to $(Z+Z^*)$ being positive definite. In this case $(Z+Z^*)$ is invertible and maximum power transfer port condition is unique.

## 12. Dynamical systems

\*(This section is largely self contained. Motivation is provided by the section on dynamical systems in [19].)
We consider the dynamical system $\mathcal{V}_{W\dot{W}UY}$ to be defined by an equation of the kind

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

where $W, \dot{W}$, are disjoint copies of each other. If we impose conditions on the variables $u, y$, by insisting that $(u, y) \in \mathcal{V}_{UY}$, we get a generalized autonomous system or **genaut** $\mathcal{V}_{W\dot{W}} := \mathcal{V}_{W\dot{W}UY} \leftrightarrow \mathcal{V}_{UY}$. We say the dynamical system $\mathcal{V}_{\dot{W}WM}$ is in the state-input-output form if it is defined through

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

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

State feedback and output injection would be represented by spaces $\mathcal{V}_{WU}, \mathcal{V}_{\dot{W}Y}$, respectively (corresponding to the solution space of feedback and injection constraints).

Applying state feedback $\mathcal{V}_{WU}$ to a dynamical system $\mathcal{V}_{W\dot{W}UY}$ will result in the genaut $\mathcal{V}_{W\dot{W}}(\text{feedback}) := (\mathcal{V}_{W\dot{W}UY} \cap \mathcal{V}_{WU}) \circ W \dot{W}$. Applying output injection $\mathcal{V}_{\dot{W}Y}$ to the dynamical system $\mathcal{V}_{W\dot{W}UY}$ will result in the genaut $\mathcal{V}_{W\dot{W}}(\text{injection}) := (\mathcal{V}_{W\dot{W}UY} + \mathcal{V}_{WU}) \times W \dot{W}$.

This section is concerned with the translation of the notation for standard notions and algorithms of control systems from state-input-output form $\dot{w} = Aw + Bu, y = Cw$, to that of the present implicit representation. There are two advantages to working with the implicit representation.

* Systems are usually available in their implicit form so that we avoid the labour of first putting them in the state-input-output form.

* In every case the implicit representation is simple and the algorithms (see Section 6) can exploit sparsity of large systems whereas the state-input-output form usually destroys it.

The problems in this section illustrate these ideas.

We illustrate the use of the notation below.

* Instead of considering the map defined by $f_S = Kf_P$, we would look at the solution space $\mathcal{V}_{SP}$ of the equation $If_S - Kf_P = 0$; instead of saying $K$ is symmetric, we would say the space $\mathcal{V}_{SP}$ is complementary orthogonal to the solution space $\mathcal{V}'_{SP}$ of the equation $Kf_S + If_P = 0$ (see for instance [11]).

* When we need to speak of feedback $u = Kx$ on the system $\mathcal{V}_{X\dot{X}U} := \{(\dot{x}, x, u) : \dot{x} = Ax + Bu\}$, we would instead speak of the intersection $\mathcal{V}_{XU} \cap \mathcal{V}_{X\dot{X}U}$ of the spaces $\mathcal{V}_{XU} := \{(x, u) : u = Kx\}$ and $\mathcal{V}_{X\dot{X}U}$ and its restriction $(\mathcal{V}_{XU} \cap \mathcal{V}_{X\dot{X}U}) \circ X \cup \dot{X}$ to the set $X \uplus \dot{X}$;

when we need to speak of injection $\dot{x} = Ly$ into the system $\mathcal{V}_{X\dot{X}Y} := \{(\dot{x}, x, y) : \dot{x} = Ax, y = Cx\}$, we would instead speak of the sum $\mathcal{V}_{\dot{X}Y} + \mathcal{V}_{X\dot{X}Y}$ of the spaces $\mathcal{V}_{\dot{X}Y} := \{(\dot{x}, y) : \dot{x} = Ly\}$ and $\mathcal{V}_{X\dot{X}Y}$ and its contraction $(\mathcal{V}_{\dot{X}Y} + \mathcal{V}_{X\dot{X}Y}) \times X \cup \dot{X}$ to the set $X \uplus \dot{X}$ (Subsection 12.1).

* When we need to speak of a controlled invariant space $\mathcal{V}_X$ (i.e., a space that satisfies $A(\mathcal{V}_X) \subseteq \mathcal{V}_X + Im(B)$) of the system $\mathcal{V}_{X\dot{X}U} := \{(\dot{x}, x, u) : \dot{x} = Ax + Bu\}$, we would instead say that $(\mathcal{V}_{X\dot{X}U} \circ X \cup \dot{X}) \leftrightarrow (\mathcal{V}_X)_{\dot{X}} \supseteq \mathcal{V}_X$ (see for instance [12])

$(X, \dot{X}$ being disjoint copies of each other with $\dot{e} \in \dot{X}, e \in X$, corresponding to each other, and $(\mathcal{V}_X)_{\dot{X}} := \{f_{\dot{X}}, f_X \in \mathcal{V}_X\}), f_{\dot{X}}(\dot{e}) = f_X(e), e \in X)$;

when we need to speak of a conditioned invariant space $\mathcal{V}_X$ (i.e., a space that satisfies

$\mathcal{V}_X \supseteq A(\mathcal{V}_X \cap \text{Ker}(C))$ of the system $\mathcal{V}_{X\dot{X}Y} := \{(\dot{x}, x, y) : \dot{x} = Ax, y = Cx\}$, we would instead say that $(\mathcal{V}_{X\dot{X}Y} \times X \cup \dot{X}) \leftrightarrow \mathcal{V}_X \subseteq (\mathcal{V}_X)_{\dot{X}}$ (Subsection 12.2).
### 12.1. State feedback and output injection

**Definition 37.** We say we apply $(W, U)$- **feedback** $\mathcal{V}_{WU}$ to the dynamical system $\mathcal{V}_{\dot{W}\dot{W}UY}$ when we perform the operation $(\mathcal{V}_{\dot{W}\dot{W}UY} \cap \mathcal{V}_{WU}) \circ W\dot{W}$. We say we apply $(\dot{W}, Y)$- **injection** to the dynamical system $\mathcal{V}_{\dot{W}\dot{W}UY}$ when we perform the operation $(\mathcal{V}_{\dot{W}\dot{W}UY} + \mathcal{V}_{\dot{W}Y}) \times W\dot{W}$.

**Problem 42.** For a system defined by

$$ \dot{w} = Aw + Bu \quad (47) $$

$$ y = Cw + Du, \quad (48) $$

show that if we apply $(W, U)$- **feedback** $\mathcal{V}_{WU}$ defined by $u = Fw$, the system $\dot{w} = (A + BF)w$, would result and if we apply $(\dot{W}, Y)$- **injection** defined by $\dot{w} = Gy$, the system $\dot{w} = (A - GC)w$, would result.

**Answer**

For the system described by Equation 47 the space of solutions $\mathcal{V}_{\dot{W}\dot{W}UY}$ is (taking $\lambda_1, \lambda_2$ to be free vectors of appropriate dimension)

$$ \begin{aligned} w &= \lambda_1 \\ \dot{w} &= A\lambda_1 + B\lambda_2 \\ u &= \lambda_2 \\ y &= C\lambda_1 + D\lambda_2. \end{aligned} $$

The $(W, U)$- feedback equations are $u = Fw$, with the space of solutions $\mathcal{V}_{WU}$ given by

$$ \begin{aligned} u &= F\lambda_1 \\ w &= \lambda_1. \end{aligned} $$

The space $(\mathcal{V}_{\dot{W}\dot{W}UY} \cap \mathcal{V}_{WU}) \circ W\dot{W}$ is

$$ \begin{aligned} w &= \lambda_1 \\ \dot{w} &= (A + BF)\lambda_1 \end{aligned} $$

which simplifies to $\dot{w} = (A + BF)w$.

The $(\dot{W}, Y)$- injection equations are $\dot{w} = Gy$, with the space of solutions $\mathcal{V}_{\dot{W}Y}$ given by

$$ \begin{aligned} y &= \sigma \\ \dot{w} &= G\sigma. \end{aligned} $$

The space $(\mathcal{V}_{\dot{W}\dot{W}UY} + \mathcal{V}_{\dot{W}Y}) \times W\dot{W}$ is obtained as

$$ \begin{aligned} w &= \lambda_1 \\ \dot{w} &= A\lambda_1 + Bu + G\sigma \\ u &= \mathbf{0} \\ y &= \mathbf{0} = C\lambda_1 + D\mathbf{0} + \sigma, \end{aligned} $$

which simplifies to $\dot{w} = (A - GC)w$.