By induction on the size of $\mathcal{H},$ one can prove the following
generalization of Theorem 11:

######  Theorem 31.

Let $\mathcal{H}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{i}},i=1,\cdots,m\\}$ be an
associative family of vector spaces and let
$\mathcal{H}^{\perp}:\equiv\\{\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}},i=1,\cdots,m\\}.$
Then
$(\leftrightarrow(\mathcal{H}))^{\perp}=(\rightleftharpoons(\mathcal{H}^{\perp})).$

We know that, by definition, $({\cal K}_{Y_{1}}\rightleftharpoons{\cal
K}_{Y_{2}})=({\cal K}_{Y_{1}}\leftrightarrow{\cal K}_{(-Y_{1}\cap
Y_{2})(Y_{2}-Y_{1})}).$ It is convenient to extend this identity to
associative families. We need the following definition for this purpose.

######  Definition 32.

Let $\mathcal{H}=\\{{\cal K}_{Y_{i}},i=1,\cdots,m\\},$ be an associative
family. We construct an associative family $\hat{\mathcal{H}}_{1,\cdots,m}$ as
follows. Let $Y_{i1}:\equiv\\{e,e\in Y_{i}\cap Y_{j},j>i\\}$ and let
$Y_{i2}:\equiv Y_{i}-Y_{i1}.$ Define $\hat{{\cal K}}_{Y_{i}}:\equiv({\cal
K}_{Y_{i}})_{(-Y_{i1})Y_{i2}}.$ Let
$\hat{\mathcal{H}}_{1,\cdots,m}:\equiv\\{\hat{{\cal
K}}_{Y_{i}},i=1,\cdots,m\\}.$ We say that
$\\{\mathcal{H},\hat{\mathcal{H}}_{1,\cdots,m}\\}$ is a skewed pair of
associative families. We omit the subscript when the order is clear from the
context and denote $\hat{\mathcal{H}}_{1,\cdots,m}$ simply by
$\hat{\mathcal{H}}.$

For the Example 29, we note that
$Y_{11}=\\{e_{3},e_{5},e_{7}\\},Y_{21}=\emptyset,Y_{31}=\emptyset,Y_{41}=\\{e_{2},e_{4},e_{8}\\},Y_{51}=\emptyset,Y_{61}=\emptyset.$

We now have the following useful lemma about the operations
$\leftrightarrow(\cdot)$ and $\rightleftharpoons(\cdot).$

######  Lemma 33.

Let $\mathcal{H}=\\{{\cal
K}_{Y_{i}},i=1,\cdots,m\\},\hat{\mathcal{H}}:\equiv\\{\hat{{\cal
K}}_{Y_{i}},i=1,\cdots,m\\}$ and let $\\{\mathcal{H},\hat{\mathcal{H}}\\}$ be
a skewed pair of associative families. Let $Z$ be the set of all elements of
$\bigcup_{i}Y_{i}$ which belong to only one of the $Y_{i}.$ Then

  1. 1.

$\leftrightarrow(\mathcal{H})\ =\ (\bigcap_{i}{\cal K}_{Y_{i}})\circ
Z=(\Sigma_{i}\hat{{\cal K}}_{Y_{i}})\times Z\ =\
(\rightleftharpoons(\hat{\mathcal{H}})),$

  2. 2.

$\rightleftharpoons(\mathcal{H})\ =\ (\Sigma_{i}{\cal K}_{Y_{i}})\times Z=\
(\bigcap_{i}\hat{{\cal K}}_{Y_{i}})\circ Z\ =\
(\leftrightarrow(\hat{\mathcal{H}})),$

where the intersection and summation operations are over all nonvoid
collections in $\mathcal{H},\hat{\mathcal{H}}.$

######  Definition 34.

Let ${\mathcal{H}}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}\\}$ be an
associative family of affine spaces with vector space translates
$\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}}\\}.$ We
say ${\mathcal{H}}$ is rigid iff the following rank conditions are satisfied.

  * 1.

(primal)
$r(\Sigma_{i}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i}r(\mbox{$\mathcal{V}$}_{Y_{i}});$

  * 2.

(dual)
$r(\Sigma_{i}\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}})=\Sigma_{i}r(\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}}).$

We note that the definition of rigid families agrees with that of a pair of
affine spaces (by part 3 of Theorem 17). We further have the following simple
lemma.

######  Lemma 35.

Let ${\mathcal{H}}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}\\}$ be an
associative family of affine spaces with vector space translates
$\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}}\\}.$ Let
${\cal G}_{\mathcal{H}}$ be connected. If $\mathcal{H}$ is rigid then every
subfamily of ${\mathcal{H}}$ is rigid.

###### Proof.

Let ${\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}$ have vector space translates
$\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}},$
respectively. Without loss of generality, it is adequate to show that
$\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{m}}\\},m<n$ is rigid. Now
$r(\mbox{$\mathcal{V}$}_{Y_{1}}+\cdots+\mbox{$\mathcal{V}$}_{Y_{m}})\leq
r(\mbox{$\mathcal{V}$}_{Y_{1}})+\cdots+r(\mbox{$\mathcal{V}$}_{Y_{m}})$ and
$r(\Sigma_{i=1}^{n}\mbox{$\mathcal{V}$}_{Y_{i}})\leq
r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})+r(\Sigma_{i=m+1}^{n}\mbox{$\mathcal{V}$}_{Y_{i}}).$
Therefore the primal rank condition of rigidity is true for $\\{{\cal
A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}\\}$ only if it is true for $\\{{\cal
A}_{Y_{1}},\cdots,{\cal A}_{Y_{m}}\\}.$ The proof for the dual rank condition
is essentially the same. ∎

By induction on the size of $\mathcal{H},$ we can prove the following
generalization of part 1 of Theorem 17.

######  Lemma 36.

Let ${\mathcal{H}}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}\\}$ be an
associative family of affine spaces with vector space translates
$\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}}\\}.$
Further let $e\in Y_{1}-\bigcup_{i=2}^{n}Y_{i}.$ If $\mathcal{H}$ is rigid
then

  1. 1.

$\leftrightarrow({\mathcal{H}})$ is nonvoid and has the vector space translate
$\leftrightarrow(\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}}\\}),$
and

  2. 2.

$\rightleftharpoons({\mathcal{H}})$ is nonvoid and has the vector space
translate
$\rightleftharpoons(\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{n}}\\}).$

The following lemma addresses the rigidity of a common class of associative
families.

######  Lemma 37.

Let $\mathcal{H}_{1}:\equiv\\{{\cal A}_{X_{1}},\cdots,{\cal A}_{X_{n}}\\},$
and let $\mathcal{H}_{2}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal
A}_{Y_{m}}\\},$ with the $X_{i},$ being pairwise disjoint and the $Y_{j}$
also. Let $\mbox{$\mathcal{V}$}_{X_{i}},\mbox{$\mathcal{V}$}_{Y_{j}},$ be the
vector space associates of ${\cal A}_{X_{i}},{\cal A}_{Y_{j}},$ respectively.
Then the associative family $\mathcal{H}_{1}\uplus\mathcal{H}_{2}$ is rigid
iff the pair
$\\{\oplus\mbox{$\mathcal{V}$}_{X_{i}},\oplus\mbox{$\mathcal{V}$}_{Y_{j}}\\},$
is rigid.

###### Proof.

We have
$r(\mbox{$\mathcal{V}$}_{X_{1}}\oplus\cdots\oplus\mbox{$\mathcal{V}$}_{X_{n}})=r(\mbox{$\mathcal{V}$}_{X_{1}})+\cdots+r(\mbox{$\mathcal{V}$}_{X_{n}}),\
r(\mbox{$\mathcal{V}$}_{Y_{1}}\oplus\cdots\oplus\mbox{$\mathcal{V}$}_{Y_{m}})=r(\mbox{$\mathcal{V}$}_{Y_{1}})+\cdots+r(\mbox{$\mathcal{V}$}_{Y_{n}}),$
$r(\mbox{$\mathcal{V}$}^{\perp}_{X_{1}}\oplus\cdots\oplus\mbox{$\mathcal{V}$}^{\perp}_{X_{n}})=r(\mbox{$\mathcal{V}$}^{\perp}_{X_{1}})+\cdots+r(\mbox{$\mathcal{V}$}^{\perp}_{X_{n}}),\
r(\mbox{$\mathcal{V}$}^{\perp}_{Y_{1}}\oplus\cdots\oplus\mbox{$\mathcal{V}$}^{\perp}_{Y_{m}})=r(\mbox{$\mathcal{V}$}^{\perp}_{Y_{1}})+\cdots+r(\mbox{$\mathcal{V}$}^{\perp}_{Y_{n}}).$
The result now follows from part 3 of Theorem 17. ∎

We now have a result which expresses rigidity of associative families
recursively.

######  Theorem 38.

Let ${\mathcal{H}}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{n}}\\}$ be an
associative family of affine spaces with ${\cal G}_{\mathcal{H}}$ connected
and with non empty edge set. Let ${\mathcal{H}}$ be partitioned as
${\mathcal{H}_{1}}\uplus{\mathcal{H}_{2}}.$ Then

  1. 1.

${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},{\mathcal{H}_{2}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow(\mathcal{H}_{2})\\}$ are
rigid.

  2. 2.

${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},{\mathcal{H}_{2}}$ and
$\\{\rightleftharpoons(\mathcal{H}_{1}),\rightleftharpoons(\mathcal{H}_{2})\\}$
are rigid.

The proof of Theorem 38 is based on the following lemmas.

######  Lemma 39.

Let
$\mathcal{H}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}}\\}$
be a collection of vector spaces. We have the following.

  1. 1.

$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff every set of nonzero vectors
$\\{f_{Y_{1}},\cdots,f_{Y_{m}}\\},f_{Y_{i}}\in\mbox{$\mathcal{V}$}_{Y_{i}}$ is
linearly independent.

  2. 2.

$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff for each $t<m,$ we have
$r(\Sigma_{i=t}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=r(\mbox{$\mathcal{V}$}_{Y_{t}})+r(\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}}).$

  3. 3.

If
$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}}),$
and $T\subseteq\bigcup_{i}Y_{i},$ then
$r((\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times
T)=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}}\times{Y_{i}}\cap T)$
(where $r(\mbox{$\mathcal{V}$}_{Y_{i}}\times{Y_{i}}\cap T)$ is taken to be
zero if ${Y_{i}}\cap T=\emptyset$).

  4. 4.

Let $\mathcal{H}$ be an associative family. For each $Y_{i}$ let $Y_{i1}$
denote the set of all $e$ such that $e\in Y_{i}\cap Y_{j}$ for some $j>i.$ Let
${Y_{i2}}:\equiv Y_{i}-{Y_{i1}},\
\hat{\mbox{$\mathcal{V}$}}_{Y_{i}}:\equiv({\mbox{$\mathcal{V}$}}_{Y_{i}})_{(-Y_{i1})Y_{i2}},i=1,\cdots,m.$
Then
$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff for each $Y_{t}$ we have $r[(\mbox{$\mathcal{V}$}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times
Y_{t1})]=0,$
equivalently, iff for each $Y_{t}$ we have
$r[(\hat{\mbox{$\mathcal{V}$}}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})\times
Y_{t1})]=0,$
equivalently, iff
$r(\Sigma_{i=1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})=\Sigma_{i=1}^{m}r(\hat{\mbox{$\mathcal{V}$}}_{Y_{i}}).$

###### Proof.

Part 1 is routine. Part 2 can be proved simply by induction. Part 3 follows
from part 1.
4\. By Theorem 5,
$r(\mbox{$\mathcal{V}$}_{A}+\mbox{$\mathcal{V}$}_{B})=r(\mbox{$\mathcal{V}$}_{A})+r(\mbox{$\mathcal{V}$}_{B})-r([\mbox{$\mathcal{V}$}_{A}\times(A\cap
B)]\cap[\mbox{$\mathcal{V}$}_{B}\times(A\cap B)]).$
Therefore
$r(\mbox{$\mathcal{V}$}_{A}+\mbox{$\mathcal{V}$}_{B})=r(\mbox{$\mathcal{V}$}_{A})+r(\mbox{$\mathcal{V}$}_{B})$
iff $r([\mbox{$\mathcal{V}$}_{A}\times(A\cap
B)]\cap[\mbox{$\mathcal{V}$}_{B}\times(A\cap B)])=0.$
We note that $Y_{t1}=Y_{t}\cap(Y_{t+1}\cup\cdots\cup Y_{m}).$ Therefore,
$r(\Sigma_{i=t}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=r(\mbox{$\mathcal{V}$}_{Y_{t}})+r(\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})$
iff $r[(\mbox{$\mathcal{V}$}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times
Y_{t1})]=0.$
Using part 2, we therefore have
$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff $r[(\mbox{$\mathcal{V}$}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times
Y_{t1})]=0,$ for each $Y_{t}.$
Next $\hat{\mbox{$\mathcal{V}$}}_{Y_{t}}\times
Y_{t1}=({\mbox{$\mathcal{V}$}}_{Y_{i}})_{(-Y_{i1})Y_{i2}}\times
Y_{t1}={\mbox{$\mathcal{V}$}}_{Y_{t}}\times Y_{t1}$ and, since in
$\hat{\mbox{$\mathcal{V}$}}_{Y_{i}},{\mbox{$\mathcal{V}$}}_{Y_{i}},i>t,$ the
columns $Y_{t1}$ have the same sign, we have
$(\Sigma_{i=t+1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})\times
Y_{t1}=(\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times Y_{t1}.$
Therefore $(\mbox{$\mathcal{V}$}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})\times
Y_{t1})=(\hat{\mbox{$\mathcal{V}$}}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})\times
Y_{t1}).$ Thus
$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff $r[(\hat{\mbox{$\mathcal{V}$}}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})\times
Y_{t1})]=0,$ for each $Y_{t}.$ We have shown above that
$r(\Sigma_{i=1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})=\Sigma_{i=1}^{m}r(\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})$
iff $r[(\hat{\mbox{$\mathcal{V}$}}_{Y_{t}}\times
Y_{t1})\cap((\Sigma_{i=t+1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})\times
Y_{t1})]=0.$ Therefore,
$r(\Sigma_{i=1}^{m}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i=1}^{m}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff
$r(\Sigma_{i=1}^{m}\hat{\mbox{$\mathcal{V}$}}_{Y_{i}})=\Sigma_{i=1}^{m}r(\hat{\mbox{$\mathcal{V}$}}_{Y_{i}}).$
∎

######  Lemma 40.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{i}},i=1,\cdots,m\\}$ and
let
${\mathcal{H}}_{1}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{i}},i=1,\cdots,t\\},t<m,$
${\mathcal{H}}_{2}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{i}},i=t+1,\cdots,m\\}$ be
subfamilies of $\hat{\mathcal{H}}.$ Let $Y^{1}=\bigcup^{t}_{i=1}Y_{i}$ and let
$Y^{2}=\bigcup^{m}_{i=t+1}Y_{i}.$ Then ${\mathcal{H}}$ satisfies the rank
conditions of Definition 34 iff ${\mathcal{H}}_{1},{\mathcal{H}}_{2}$ satisfy
them and further
$r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))=0$ and
$r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))=0.$

###### Proof.

When $Y_{1}\cap Y_{2}=\emptyset,$ it is clear that if the rank condition is
satisfied for ${\mathcal{H}_{1}},{\mathcal{H}_{2}}$ the lemma is trivially
true. Let $Y_{1}\cap Y_{2}$ be nonvoid. By Theorem 5,
$r(\mbox{$\mathcal{V}$}_{A}+\mbox{$\mathcal{V}$}_{B})=r(\mbox{$\mathcal{V}$}_{A})+r(\mbox{$\mathcal{V}$}_{B})-r([\mbox{$\mathcal{V}$}_{A}\times(A\cap
B)]\cap[\mbox{$\mathcal{V}$}_{B})\times(A\cap B)].$ Therefore,
$r(\Sigma^{m}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}})=r(\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{X_{i}})+r(\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{X_{i}})-r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})).$
It follows that
$r(\Sigma^{m}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma^{m}_{i=1}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
iff
$r(\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma^{t}_{i=1}r(\mbox{$\mathcal{V}$}_{Y_{i}}),t<m,$
$r(\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma^{m}_{i=t+1}r(\mbox{$\mathcal{V}$}_{Y_{i}})$
and $r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))=0.$
Working with $\mbox{$\mathcal{V}$}^{\perp}_{Y_{i}}$ and repeating the
argument, we get the second half of the statement of the lemma. ∎

###### Proof.

(Proof of Theorem 38)
Let ${\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{m}}$ have vector space translates
$\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}},$
respectively. We note that rigidity of $\mathcal{H}:\equiv\\{{\cal
A}_{Y_{1}},\cdots,{\cal A}_{Y_{m}}\\}$ is defined in terms of rigidity of
$\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}}\\}.$
Further by Lemma 36, we know that when $\mathcal{H}_{i}$ is rigid and
$\leftrightarrow(\mathcal{H}_{i}),\rightleftharpoons(\mathcal{H}_{i})$ are
nonvoid, then these latter have vector space translates
$\leftrightarrow(\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}}\\}),\rightleftharpoons(\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}}\\})$
respectively. Since ${\cal G}_{\mathcal{H}}$ is connected, we must have
$\leftrightarrow(\mathcal{H}_{i}),\rightleftharpoons(\mathcal{H}_{i}),i=1,2,$
not equal to ${\cal K}_{\emptyset}.$ We therefore prove the theorem taking
$\mathcal{H}:\equiv\\{\mbox{$\mathcal{V}$}_{Y_{1}},\cdots,\mbox{$\mathcal{V}$}_{Y_{m}}\\}.$

By Lemma 40, the primal rank condition of Definition 34
($r(\Sigma_{i}\mbox{$\mathcal{V}$}_{Y_{i}})=\Sigma_{i}r(\mbox{$\mathcal{V}$}_{Y_{i}})$)
holds for $\mathcal{H}$ iff it holds for
${\mathcal{H}_{1}},{\mathcal{H}_{2}},$ and
$r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))=0,$ where $Y^{1}=\bigcup^{t}_{i=1}Y_{i}$ and
$Y^{2}=\bigcup^{m}_{i=t+1}Y_{i}.$ We have
$r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))$
$=r([\Sigma^{t}_{i=1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times Y^{1}\times(Y^{1}\cap
Y^{2})\bigcap[\Sigma^{m}_{i=t+1}\mbox{$\mathcal{V}$}_{Y_{i}}]\times
Y^{2}\times(Y^{1}\cap Y^{2})$
$=r([\rightleftharpoons(\mathcal{H}_{1}))\times(Y^{1}\cap
Y^{2})]\cap[(\rightleftharpoons(\mathcal{H}_{2}))\times(Y^{1}\cap Y^{2})].$
Thus the primal rank condition holds for $\mathcal{H}$ iff it holds for
$\mathcal{H}_{1},\mathcal{H}_{2}$ and the zero intersection property holds for
$\\{(\rightleftharpoons(\mathcal{H}_{1})),(\rightleftharpoons(\mathcal{H}_{2}))\\}.$

As in Definition 32, we take
$\hat{\mathcal{H}}:\equiv\\{\hat{\mbox{$\mathcal{V}$}}_{Y_{1}},\cdots,\hat{\mbox{$\mathcal{V}$}}_{Y_{m}}\\}.$
Let
$\hat{\mathcal{H}}:\equiv\hat{\mathcal{H}}_{1,\cdots,m},\hat{\mathcal{H}}_{1}:\equiv(\hat{\mathcal{H}}_{1})_{1,\cdots,t},$
$\hat{\mathcal{H}}_{2}:\equiv(\hat{\mathcal{H}}_{2})_{t+1,\cdots,m}.$ We note
that $\hat{\hat{\mathcal{H}}}=\mathcal{H}$ and we have
$\leftrightarrow(\mathcal{H})=(\rightleftharpoons(\hat{\mathcal{H}})),$ for
any associative family $\mathcal{H}.$ By part 4 of Lemma 39, we know that the
primal rank condition holds for $\mathcal{H}$ iff it holds for
$\hat{\mathcal{H}}.$ By the above argument, the primal rank condition holds
for $\hat{\mathcal{H}}$ iff it holds for
$\hat{\mathcal{H}}_{1},\hat{\mathcal{H}}_{2}$, i.e., for
$\mathcal{H}_{1},\mathcal{H}_{2},$ and the zero intersection property holds
for
$\\{(\rightleftharpoons(\hat{\mathcal{H}}_{1})),(\rightleftharpoons(\hat{\mathcal{H}}_{1}))\\}=\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}.$
It follows that the primal rank condition holds for $\mathcal{H}$ iff it holds
for $\mathcal{H}_{1},\mathcal{H}_{2}$ and the zero intersection property holds
for
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}.$

The dual rank condition for $\mathcal{H}$ is the same as the primal rank
condition for $\mathcal{H}^{\perp}.$ When $\mathcal{H}$ is associative, so is
$\mathcal{H}^{\perp}.$ Working with $\mathcal{H}^{\perp}$ we can show that the
primal rank condition holds for $\mathcal{H}^{\perp}$ iff it holds for
$\mathcal{H}^{\perp}_{1},\mathcal{H}^{\perp}_{2}$ and the zero intersection
property holds for
$\\{(\rightleftharpoons(\mathcal{H}^{\perp}_{1})),(\rightleftharpoons(\mathcal{H}^{\perp}_{2}))\\}.$
By Theorem 31,
$\\{(\rightleftharpoons(\mathcal{H}^{\perp}_{1})),(\rightleftharpoons(\mathcal{H}^{\perp}_{2}))\\}=\\{(\leftrightarrow(\mathcal{H}_{1}))^{\perp})),(\leftrightarrow(\mathcal{H}_{2}))^{\perp}))\\}.$
Now by by part 4 of Theorem 17, the zero intersection property holds for
$\\{(\leftrightarrow(\mathcal{H}_{1}))^{\perp})),(\leftrightarrow(\mathcal{H}_{2}))^{\perp}))\\}$
iff the full sum property holds for
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}.$
We thus see that the primal and dual rank conditions of rigidity hold for
$\mathcal{H}$ iff they hold for $\mathcal{H}_{1},\mathcal{H}_{2}$ and
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}$
is rigid. Thus $\mathcal{H}$ is rigid iff
$\mathcal{H}_{1},\mathcal{H}_{2},\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}$
are rigid.

2\. As before, we only prove the result taking the families to be made up of
vector spaces.

As in Definition 32, we define
$\hat{\mathcal{H}},\hat{\mathcal{H}}_{1},\hat{\mathcal{H}}_{2}.$ By part 4 of
Lemma 39, we know that the primal and dual rank condition holds for
$\mathcal{H}$ iff it holds for $\hat{\mathcal{H}}.$ From the proof above,
$\hat{\mathcal{H}}$ is rigid iff $\hat{\mathcal{H}_{1}},\hat{\mathcal{H}_{2}}$
and
$\\{\leftrightarrow(\hat{\mathcal{H}_{1}}),\leftrightarrow(\hat{\mathcal{H}_{2}})\\}$
are rigid. By Lemma 33, $\leftrightarrow(\hat{\mathcal{H}})\ =\
\rightleftharpoons(\mathcal{H}),\leftrightarrow(\hat{\mathcal{H}}_{i})\ =\
\rightleftharpoons(\mathcal{H}_{i}).$ The result now follows.

∎

The following is a more convenient version of Theorem 38.

######  Theorem 41.

Let ${\mathcal{H}}:\equiv\\{{\cal A}_{Y_{1}},\cdots,{\cal A}_{Y_{m}}\\}$ be an
associative family of affine spaces, with ${\cal G}_{\mathcal{H}}$ connected
and with non empty edge set. Let ${\mathcal{H}}$ be partitioned as
${\mathcal{H}_{1}}\uplus\cdots\uplus{\mathcal{H}_{n}}.$ Then

  1. 1.

${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.

  2. 2.

${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\rightleftharpoons(\mathcal{H}_{1}),\cdots,\rightleftharpoons(\mathcal{H}_{n})\\}$
are rigid.

###### Proof.

1\. The proof is by induction over $n.$ We have seen in Theorem 38, that the
result is true when $n=2.$ We then have ${\mathcal{H}}$ is rigid iff
${\mathcal{H}_{1}},({\mathcal{H}_{2}}\uplus\cdots\uplus{\mathcal{H}_{n}}),\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow({\mathcal{H}_{2}}\uplus\cdots\uplus\mathcal{H}_{n})\\}$
are rigid.
By induction, ${\mathcal{H}_{2}}\uplus\cdots\uplus{\mathcal{H}_{n}}$ is rigid
iff ${\mathcal{H}_{2}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{2}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.
We therefore need only show that, when
$\mathcal{H}_{1},\cdots,\mathcal{H}_{n}$ are rigid, rigidity of
$\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow({\mathcal{H}_{2}}\uplus\cdots\uplus\mathcal{H}_{n})\\}$
and
$\\{\leftrightarrow(\mathcal{H}_{2}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
implies rigidity of
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}.$

Let us denote
$\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n}),$
respectively by ${\cal A}_{Z_{1}},\cdots,{\cal A}_{Z_{n}}.$ Since
$\mathcal{H}$ is an associative family, by the definition of
$\leftrightarrow(\mathcal{H}_{i}),$ it is clear that no element belongs to
more than two of the $Z_{i}.$ Further, since ${\cal G}_{\mathcal{H}}$ is
connected, the $Z_{i}$ are non void. Since
$\mathcal{H}_{1},\cdots,\mathcal{H}_{n},$ are rigid, by Lemma 36, the ${\cal
A}_{Z_{i}}$ are nonvoid. Let ${\cal A}_{Z_{1}},\cdots,{\cal A}_{Z_{n}},$ have
vector space translates
$\mbox{$\mathcal{V}$}_{Z_{1}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}},$
respectively. We thus need to show that rigidity of
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},(\mbox{$\mathcal{V}$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\mathcal{V}$}_{Z_{n}})\\}$
and $\\{\mbox{$\mathcal{V}$}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$
implies the rigidity of
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}.$

Suppose
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},(\mbox{$\mathcal{V}$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\mathcal{V}$}_{Z_{n}})\\}$
and $\\{\mbox{$\mathcal{V}$}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$
are rigid. Let $P$ be the set of all elements which belong precisely to one of
$Z_{2},\cdots,Z_{m}$ and let $T:\equiv Z_{1}\cap\bigcup_{i=2}^{m}Z_{i}.$ Since
no element belongs to more than two of $Z_{1},\cdots,Z_{n},$ it is clear that
$T\subseteq P.$ From the zero intersection property of
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},(\mbox{$\mathcal{V}$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\mathcal{V}$}_{Z_{n}})\\},$
we have that $r((\mbox{$\mathcal{V}$}_{Z_{1}}\times
T)\cap(\mbox{$\mathcal{V}$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\mathcal{V}$}_{Z_{n}})\times
T)=r((\mbox{$\mathcal{V}$}_{Z_{1}}\times
T)\cap[(\mbox{$\mathcal{V}$}_{Z_{2}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{n}})\times
P\times T])$
$=r((\mbox{$\mathcal{V}$}_{Z_{1}}\times
T)\cap[(\mbox{$\mathcal{V}$}_{Z_{2}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{n}})\times
T])=0.$ By Theorem 5, it follows that
$r(\mbox{$\mathcal{V}$}_{Z_{1}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{m}})=r(\mbox{$\mathcal{V}$}_{Z_{1}})+r(\mbox{$\mathcal{V}$}_{Z_{2}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{m}}).$
Since $\\{\mbox{$\mathcal{V}$}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$
is rigid, we have
$r(\mbox{$\mathcal{V}$}_{Z_{2}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{m}})=r(\mbox{$\mathcal{V}$}_{Z_{1}})+r(\mbox{$\mathcal{V}$}_{Z_{2}})+\cdots+r(\mbox{$\mathcal{V}$}_{Z_{n}}).$
Therefore
$r(\mbox{$\mathcal{V}$}_{Z_{1}}+\cdots+\mbox{$\mathcal{V}$}_{Z_{m}})=r(\mbox{$\mathcal{V}$}_{Z_{1}})+\cdots+r(\mbox{$\mathcal{V}$}_{Z_{n}}).$

The proof of the dual rank condition for
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$ is by
replacing $\mbox{$\mathcal{V}$}_{Z_{i}}$ by
$\mbox{$\mathcal{V}$}_{Z_{i}}^{\perp}$ everywhere in the above proof and by
using the fact that rigidity of
$\\{\mbox{$\mathcal{V}$}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$ is
equivalent to rigidity of
$\\{\mbox{$\mathcal{V}$}^{\perp}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}^{\perp}_{Z_{n}}\\}.$
We thus see that rigidity of
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},(\mbox{$\mathcal{V}$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\mathcal{V}$}_{Z_{n}})\\}$
and $\\{\mbox{$\mathcal{V}$}_{Z_{2}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}$
implies the rigidity of
$\\{\mbox{$\mathcal{V}$}_{Z_{1}},\cdots,\mbox{$\mathcal{V}$}_{Z_{n}}\\}.$
This proves that ${\mathcal{H}}$ is rigid iff
${\mathcal{H}_{1}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.

2\. As before, we need only prove the result for the case where $\mathcal{H}$
is a family of vector spaces.

As in Definition 32, we define
$\hat{\mathcal{H}},\hat{\mathcal{H}}_{1},\cdots\hat{\mathcal{H}}_{n}.$ By part
4 of Lemma 39, we know that the primal and dual rank condition holds for
$\mathcal{H}$ iff it holds for $\hat{\mathcal{H}}.$ From the proof above,
$\hat{\mathcal{H}}$ is rigid iff
$\hat{\mathcal{H}_{1}},\cdots,\hat{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\hat{\mathcal{H}_{1}}),\cdots,\leftrightarrow(\hat{\mathcal{H}_{n}})\\}$
are rigid. By Lemma 33, $\leftrightarrow(\hat{\mathcal{H}})\ =\
\rightleftharpoons(\mathcal{H}),\leftrightarrow(\hat{\mathcal{H}}_{i})\ =\
\rightleftharpoons(\mathcal{H}_{i}).$ The result now follows. ∎

##  6 Matroidal rigidity

###  6.1 Matroid preliminaries

This section follows [33], particularly the definition of the
‘$\leftrightarrow$’ operation for matroids.

Matroids are defined using various cryptomorphic sets of axioms. We will use
the base axioms to define a matroid $\mbox{$\cal M$}_{S}$ on a finite set $S$
as an ordered pair $(S,{\cal{B}})$, where ${\cal{B}}$ is a collection of
subsets of $S$, called ‘bases’, satisfying the following equivalent axioms.

  * 1.

If $b_{1},b_{2}\in{\cal{B}}$ and if $e_{2}\in b_{2}-b_{1}$, then there exists
$e_{1}\in b_{1}-b_{2}$ such that $(b_{1}-\\{e_{1}\\})\cup\\{e_{2}\\}$ is a
member of ${\cal{B}}$.

  * 2.

If $b_{1},b_{2}\in{\cal{B}}$ and if $e_{1}\in b_{1}-b_{2}$, then there exists
$e_{2}\in b_{2}-b_{1}$ such that $(b_{1}-\\{e_{1}\\})\cup\\{e_{2}\\}$ is a
member of ${\cal{B}}$.

It follows from the base axioms that all bases of a matroid have the same
size. Subsets of bases are called independent sets. Rank function
$r:2^{S}\rightarrow\mathbb{Z^{+}}$, corresponding to a matroid, is defined by
size of a largest independent set contained in the given subset.

The independence oracle for matroid $\mbox{$\cal M$}_{S}$ returns for the
query ‘is $X\subseteq S$ independent in the matroid $\mbox{$\cal M$}_{S}?$
with a ‘Yes’ or a ‘No’, with the former when $X$ is independent and the latter
when it is not. Usually, the complexity of algorithms related to matroids is
evaluated in terms of the number of queries to the oracle needed in the worst
case to complete the algorithm.

A matroid on $S$, with only null set as a base is called zero matroid, denoted
${\mathbf{0}}_{S}$. A matroid on $S$ with only full set $S$ as a base is
called a full or complete matroid, denoted $\mbox{$\cal F$}_{S}$. (Note that
we use ${\mathbf{0}}_{S}$ to denote the zero vector space as well as the zero
matroid and $\mbox{$\cal F$}_{S}$ to denote the full vector space as well as
the full matroid. This abuse of notation will not cause confusion since the
context would make it clear which entity is involved.) When sets $S$ and $P$
are disjoint, we denote a matroid on the set $S\cup P$ by $\mbox{$\cal
M$}_{SP}$ (and whenever we write $\mbox{$\cal M$}_{SP}$, it is assumed that
$S$ and $P$ are disjoint). Given a matroid $\mbox{$\cal M$}_{S}$ on $S$ and
$\mbox{$\cal M$}_{P}$ on $P$, with $S$ and $P$ disjoint, direct sum of
$\mbox{$\cal M$}_{S}$ and $\mbox{$\cal M$}_{P}$ is a matroid $\mbox{$\cal
M$}_{S}\oplus\mbox{$\cal M$}_{P}$ on $S\cup P$, whose bases are unions of a
base of $\mbox{$\cal M$}_{S}$ with a base of $\mbox{$\cal M$}_{P}$.

For any subset $b_{S}$ of $S$, its complement w.r.t. $S$ is denoted by
$\bar{b}_{S}=S-b_{S}$. Given a matroid $\mbox{$\cal M$}=(S,{\cal{B}})$, its
dual matroid, denoted $\mbox{$\cal M$}^{*}$, is defined to be
$(S,{\cal{B}}^{*})$, where ${\cal{B}}^{*}$ is the collection of complements of
the subsets present in ${\cal{B}}$. We can see that dual of the dual is same
as original matroid ($\mbox{$\cal M$}^{**}=\mbox{$\cal M$}$).

We summarize these ideas in the following theorem.

######  Theorem 42.

Let $\mbox{$\cal M$}_{X}$ be a matroid on $X.$ Then

  1. 1.

$r(\mbox{$\cal M$}_{X})+r(\mbox{$\cal M$}^{*}_{X})=|X|$ and $(\mbox{$\cal
M$}_{X})^{**}=\mbox{$\cal M$}_{X};$

  2. 2.

$T$ is a base of $\mbox{$\cal M$}_{X}$ iff $T$ is a cobase of $\mbox{$\cal
M$}^{*}_{X}.$

A circuit of a matroid $\cal M$ is a minimal dependent (not independent) set
in $\cal M$. Circuits of $\mbox{$\cal M$}^{*}$ are called bonds of $\cal M$.
For a matroid $\cal M$ on $S$, given a subset $T\subseteq S$, we define
restriction of $\cal M$ to $T$, denoted $\mbox{$\cal M$}\circ T$, as a
matroid, whose independent sets are all subsets of $T$ which are independent
in $\cal M$ (equivalently, bases in $\mbox{$\cal M$}\circ T$ are maximal
intersections of bases of $\cal M$ with $T$). Contraction of $\cal M$ to $T$,
denoted $\mbox{$\cal M$}\times T$, is defined by the matroid whose independent
sets are precisely those $X\subseteq T$ which satisfy the property that $X\cup
b_{S-T}$ is independent in $\cal M$ whenever $b_{S-T}$ is a base of
$\mbox{$\cal M$}\circ(S-T)$ (equivalently, bases of $\mbox{$\cal M$}\times T$
are minimal intersections of bases of $\cal M$ with $T$). A minor of $\cal M$
is a matroid of the form $(\mbox{$\cal M$}\times T_{1})\circ T_{2}$ or
$(\mbox{$\cal M$}\circ T_{1})\times T_{2}$, where $T_{2}\subseteq
T_{1}\subseteq S.$ We usually omit the bracket when we speak of minors of
matroids (eg $\mbox{$\cal M$}\times T_{1}\circ T_{2}$ in place of
$(\mbox{$\cal M$}\times T_{1})\circ T_{2}$ ).

We have the following set of basic results regarding minors and duals.

######  Theorem 43.

Let $S\cap P=\emptyset,T_{2}\subseteq T_{1}\subseteq S,$ $\mbox{$\cal M$}_{S}$
be a matroid on $S,$ ${\cal M}_{SP}$ be a matroid on $S\uplus P.$ We then have
the following.

  1. 1.

$(\mbox{$\cal M$}_{S}\times T_{1})\circ T_{2}=(\mbox{$\cal
M$}_{S}\circ(S-(T_{1}-T_{2})))\times T_{2}.$

  2. 2.

$r({\cal M}_{SP})=r({\cal M}_{SP}\circ S)+r({\cal M}_{SP}\times P).$

  3. 3.

$\mbox{$\cal M$}_{SP}^{*}\circ P=(\mbox{$\cal M$}_{SP}\times P)^{*}.$

  4. 4.

$\mbox{$\cal M$}_{SP}^{*}\times S=(\mbox{$\cal M$}_{SP}\circ S)^{*}.$

  5. 5.

$P_{1}\subseteq P$ is a base of ${\cal M}_{SP}\times P$ iff there exists
$S_{1}\subseteq S$ such that $S_{1}$ is a base of ${\cal M}_{SP}\circ S$ and
$S_{1}\cup P_{1}$ is a base of ${\cal M}_{SP}.$

  6. 6.

If $P_{1}\subseteq P$ is a base of ${\cal M}_{SP}\times P,$ then there exists
a base $P_{2}$ of ${\cal M}_{SP}\circ P,$ that contains it.

  7. 7.

Let $A,B\subseteq S\uplus P,A\cap B=\emptyset,$ and let there exist a base
$D_{1}$ of ${\cal M}_{SP}$ that contains $A$ and a cobase $E_{2}$ of ${\cal
M}_{SP}$ that contains $B.$ Then there exists a base $D$ of ${\cal M}_{SP}$
that contains $A$ but does not intersect $B.$

We associate matroids with vector spaces and graphs as follows. If
$\mbox{$\mathcal{V}$}_{S}$ is a vector space $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{S})$ is defined to be the matroid whose bases are
the column bases of $\mbox{$\mathcal{V}$}_{S}.$ It is clear that $(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}))^{*}=\mbox{$\cal M$}(\mbox{$\mathcal{V}$}^{\perp})$
since, $(I|K)$ is a representative matrix for $\mbox{$\mathcal{V}$},$ iff
$(-K^{T}|I)$ is a representative matrix for $\mbox{$\mathcal{V}$}^{\perp}.$ If
${\cal G}_{S}$ is a graph, $\mbox{$\cal M$}({\cal G}_{S})$ is defined to be
the matroid whose bases are the column bases of
$\mbox{$\mathcal{V}$}^{v}({\cal G}_{S}).$ We then have the following results.

######  Theorem 44.

$\mbox{$\cal M$}(\mathcal{G}):\equiv\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{v}(\mathcal{G}))=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{i}(\mathcal{G})))^{*}.$

######  Lemma 45.

Let $\mbox{$\mathcal{V}$}_{S}$ be a vector space. Let $W\subseteq T\subseteq
S.$

  1. 1.

$\mbox{$\cal M$}(\mathcal{V}\circ T)=(\mbox{$\cal M$}(\mathcal{V}))\circ T,\ \
\ \mbox{$\cal M$}(\mathcal{V}\times T)=(\mbox{$\cal M$}(\mathcal{V}))\times
T,\ \ \mbox{$\cal M$}(\mathcal{V}\circ T\times W)=(\mbox{$\cal
M$}(\mathcal{V}))\circ T\times W.$

  2. 2.

$(\mbox{$\cal M$}(\mathcal{V}\circ T))^{*}=(\mbox{$\cal
M$}(\mathcal{V})))^{*}\times T,\ \ \ (\mbox{$\cal M$}(\mathcal{V}\times
T))^{*}=(\mbox{$\cal M$}(\mathcal{V})))^{*}\circ T,\ \ (\mbox{$\cal
M$}(\mathcal{V}\circ T\times W))^{*}=(\mbox{$\cal M$}(\mathcal{V})))^{*}\times
T\circ W.$

  3. 3.

A subset is a base of $\mbox{$\cal M$}(\mbox{$\mathcal{V}$})$ iff it is a
column base of $\mbox{$\mathcal{V}$}.$

  4. 4.

A subset is a base of $(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}))^{*}$ iff it is
a column cobase of $\mbox{$\mathcal{V}$}.$

######  Lemma 46.

Let ${\cal G}$ be a graph on edge set $S.$ Let $W\subseteq T\subseteq S.$

  1. 1.

$\mbox{$\cal M$}(\mathcal{G}\circ T)=(\mbox{$\cal M$}(\mathcal{G}))\circ T,\ \
\ \mbox{$\cal M$}(\mathcal{G}\times T)=(\mbox{$\cal M$}(\mathcal{G}))\times
T,\ \ \mbox{$\cal M$}(\mathcal{G}\circ T\times W)=(\mbox{$\cal
M$}(\mathcal{G}))\circ T\times W.$

  2. 2.

$(\mbox{$\cal M$}(\mathcal{G}\circ T))^{*}=(\mbox{$\cal
M$}(\mathcal{G})))^{*}\times T,\ \ \ (\mbox{$\cal M$}(\mathcal{G}\times
T))^{*}=(\mbox{$\cal M$}(\mathcal{G})))^{*}\circ T,\ \ (\mbox{$\cal
M$}(\mathcal{G}\circ T\times W))^{*}=(\mbox{$\cal M$}(\mathcal{G})))^{*}\times
T\circ W.$

  3. 3.

A subset is a base of $\mbox{$\cal M$}({\cal G})$ iff it is a tree of ${\cal
G}.$

  4. 4.

A subset is a base of $(\mbox{$\cal M$}({\cal G}))^{*}$ iff it is a cotree of
${\cal G}.$

Let $\mbox{$\cal M$}_{1}$ and $\mbox{$\cal M$}_{2}$ be matroids on $S$. The
union of these matroids, denoted $\mbox{$\cal M$}_{1}\vee\mbox{$\cal M$}_{2}$,
is defined to be $(S,{\cal{B_{\vee}}})$, where ${\cal{B}}_{\vee}$ is the
collection of maximal sets of the form $b_{1}\cup b_{2}$, where $b_{1}$ is a
base of $\mbox{$\cal M$}_{1}$ and $b_{2}$ is a base of $\mbox{$\cal M$}_{2}$.
It can be shown that $\mbox{$\cal M$}_{1}\vee\mbox{$\cal M$}_{2}$ is again a
matroid. The intersection of matroids $\mbox{$\cal M$}_{1}$ and $\mbox{$\cal
M$}_{2}$, denoted $\mbox{$\cal M$}_{1}\wedge\mbox{$\cal M$}_{2}$, is defined
to be the matroid $(S,{\cal{B_{\wedge}}})$ whose bases are minimal sets of the
form $b_{1}\cap b_{2}$, where $b_{1}$ is a base of $\mbox{$\cal M$}_{1}$ and
$b_{2}$ is a base of $\mbox{$\cal M$}_{2}$. Matroid union is related to this
intersection through dualization, $(\mbox{$\cal M$}_{1}\vee\mbox{$\cal
M$}_{2})^{*}=\mbox{$\cal M$}_{1}^{*}\wedge\mbox{$\cal M$}_{2}^{*}$. Let
$S,P,Q$ be pairwise disjoint sets. Let $\mbox{$\cal M$}_{SP}$ and $\mbox{$\cal
M$}_{PQ}$ be matroids on $S\uplus P$ and $P\uplus Q$ respectively. Then, their
union and intersection operations are defined by

$\mbox{$\cal M$}_{SP}\vee\mbox{$\cal M$}_{PQ}:\equiv(\mbox{$\cal
M$}_{SP}\oplus{\mathbf{0}}_{Q})\vee(\mbox{$\cal
M$}_{PQ}\oplus{\mathbf{0}}_{S})$ $\mbox{$\cal M$}_{SP}\wedge\mbox{$\cal
M$}_{PQ}:\equiv(\mbox{$\cal M$}_{SP}\oplus\mbox{$\cal
F$}_{Q})\wedge(\mbox{$\cal M$}_{PQ}\oplus\mbox{$\cal F$}_{S}).$

Bases $b_{SP},b_{PQ}$ of $\mbox{$\cal M$}_{SP},\mbox{$\cal M$}_{PQ},$
respectively, such that $b_{SP}\cup b_{PQ}$ is a base of $\mbox{$\cal
M$}_{SP}\vee\mbox{$\cal M$}_{PQ}$, are said to be maximally distant.

Let $\mbox{$\cal M$}_{SP},\mbox{$\cal M$}_{PQ}$ be matroids defined on sets
$S\uplus P,P\uplus Q$ respectively, where $S,P,Q$ are pairwise disjoint sets.
Then the linking of $\mbox{$\cal M$}_{SP},\mbox{$\cal M$}_{PQ}$, denoted
$\mbox{$\cal M$}_{SP}\leftrightarrow\mbox{$\cal M$}_{PQ}$ is defined on the
set $S\uplus Q$ to be
$(\mbox{$\cal M$}_{SP}\vee\mbox{$\cal M$}_{PQ})\times(S\cup Q).$

We need the following basic identities about ranks of matroids, matroid
unions, minors and duals for the development in subsequent sections.

######  Theorem 47.

Let $\mbox{$\cal M$}^{1}_{A},\mbox{$\cal M$}^{2}_{B},\mbox{$\cal
M$}_{S},\mbox{$\cal M$}^{\prime}_{S}$ be matroids. Then

  1. 1.

$r(\mbox{$\cal M$}_{S})+r(\mbox{$\cal M$}^{\prime}_{S})=r(\mbox{$\cal
M$}_{S}\vee\mbox{$\cal M$}^{\prime}_{S})+r(\mbox{$\cal
M$}_{S}\wedge\mbox{$\cal M$}^{\prime}_{S});$

  2. 2.

$r(\mbox{$\cal M$}^{1}_{A})+r(\mbox{$\cal M$}^{2}_{B})=r(\mbox{$\cal
M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{B})+r[(\mbox{$\cal M$}^{1}_{A}\times(A\cap
B))\wedge(\mbox{$\cal M$}^{2}_{B}\times(A\cap B))];$

  3. 3.

$(\mbox{$\cal M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{B})^{*}=(\mbox{$\cal
M$}^{1}_{A})^{*}\wedge(\mbox{$\cal M$}^{2}_{B})^{*};$

  4. 4.

$(\mbox{$\cal M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B})^{*}=(\mbox{$\cal
M$}^{1}_{A})^{*}\vee(\mbox{$\cal M$}^{2}_{B})^{*};$

  5. 5.

(a) $(\mbox{$\cal M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{B})\circ X=\mbox{$\cal
M$}^{1}_{A}\circ X\vee\mbox{$\cal M$}^{2}_{B}\circ X,X\subseteq A\cap B;$
(b) $(\mbox{$\cal M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B})\times
X=\mbox{$\cal M$}^{1}_{A}\times X\wedge\mbox{$\cal M$}^{2}_{B}\times
X,X\subseteq A\cap B.$

###### Proof.

1\. A base of $\mbox{$\cal M$}_{S}\vee\mbox{$\cal M$}^{\prime}_{S}$ is a union
of two maximally distant bases of $\mbox{$\cal M$}_{S},\mbox{$\cal
M$}^{\prime}_{S}.$ By definition, a base of $\mbox{$\cal
M$}_{S}\wedge\mbox{$\cal M$}^{\prime}_{S},$ is the intersection of two
maximally distant bases of $\mbox{$\cal M$}_{S},\mbox{$\cal M$}^{\prime}_{S}.$
The result follows from the identity $|X|+|Y|=|X\cup Y|+|X\cap Y|,$ where
$X,Y,$ are sets.

2\. We have $\mbox{$\cal M$}^{1}_{A}\vee\mbox{$\cal
M$}^{2}_{B}:\equiv(\mbox{$\cal
M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A})\vee(\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B}).$ From the previous part, we have
$r(\mbox{$\cal M$}^{1}_{A})+r(\mbox{$\cal M$}^{2}_{B})=r(\mbox{$\cal
M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A})+r(\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B})$
$=r((\mbox{$\cal M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A})\vee(\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B}))+r((\mbox{$\cal
M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A})\wedge(\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B})).$
Now it can be seen that a minimal intersection of a pair of bases of
$\mbox{$\cal M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A},\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B}$ is the same as a minimal intersection of
a pair of bases of $\mbox{$\cal M$}^{1}_{A}\times(A\cap B),\mbox{$\cal
M$}^{2}_{B}\times(A\cap B)$ so that
$r((\mbox{$\cal M$}^{1}_{A}\oplus{\mathbf{0}}_{B-A})\wedge(\mbox{$\cal
M$}^{2}_{B}\oplus{\mathbf{0}}_{A-B}))=r[(\mbox{$\cal M$}^{1}_{A}\times(A\cap
B))\wedge(\mbox{$\cal M$}^{2}_{B}\times(A\cap B))]$ and the result follows.

Parts 3 and 4 follow from the definition of $\mbox{$\cal
M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{B},\mbox{$\cal
M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B},(\mbox{$\cal
M$}^{1}_{A})^{*}\vee(\mbox{$\cal M$}^{2}_{B})^{*},(\mbox{$\cal
M$}^{1}_{A})^{*}\wedge(\mbox{$\cal M$}^{2}_{B})^{*}.$

5(a) follows from the definition of the matroid union operation.

5(b) We have $(\mbox{$\cal M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B})\times
X=((\mbox{$\cal M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B})\times
X)^{**}=((\mbox{$\cal M$}^{1}_{A}\wedge\mbox{$\cal M$}^{2}_{B})^{*}\circ
X)^{*}=((\mbox{$\cal M$}^{1}_{A})^{*}\vee(\mbox{$\cal M$}^{2}_{B})^{*})\circ
X)^{*}=((\mbox{$\cal M$}^{1}_{A})^{*}\circ X\vee(\mbox{$\cal
M$}^{2}_{B})^{*}\circ X)^{*}=((\mbox{$\cal M$}^{1}_{A})^{*}\circ
X)^{*}\wedge((\mbox{$\cal M$}^{2}_{B})^{*}\circ X)^{*}=\mbox{$\cal
M$}^{1}_{A}\times X\wedge\mbox{$\cal M$}^{2}_{B}\times X.$

∎

######  Theorem 48.

Let ${\cal M}_{SP},{\cal M}_{PQ},$ be matroids on $S\uplus P,P\uplus Q,$
respectively, with $S,P,Q,$ being pairwise disjoint. Then
$r({\cal M}_{SP}\leftrightarrow{\cal M}_{PQ})=r({\cal M}_{SP}\times S)+r({\cal
M}_{PQ}\times Q)+r({\cal M}_{SP}\circ P\wedge{\cal M}_{PQ}\circ P)-r({\cal
M}_{SP}\times P\wedge{\cal M}_{PQ}\times P).$

###### Proof.

Here we have used part 2 of Theorem 47 and part 2 of Theorem 43.$r({\cal
M}_{SP}\leftrightarrow{\cal M}_{PQ}):\equiv r(({\cal M}_{SP}\vee{\cal
M}_{PQ})\times SQ)$
$=r({\cal M}_{SP}\vee{\cal M}_{PQ})-r(({\cal M}_{SP}\vee{\cal M}_{PQ})\circ
P)$
$=r({\cal M}_{SP})+r({\cal M}_{PQ})-r({\cal M}_{SP}\times P\wedge{\cal
M}_{PQ}\times P)-r({\cal M}_{SP}\circ P\vee{\cal M}_{PQ}\circ P)$
$=r({\cal M}_{SP})+r({\cal M}_{PQ})-r({\cal M}_{SP}\times P\wedge{\cal
M}_{PQ}\times P)-r({\cal M}_{SP}\circ P)-r({\cal M}_{PQ}\circ P)+r(({\cal
M}_{SP}\circ P)\wedge({\cal M}_{PQ}\circ P))$
$=[r({\cal M}_{SP})-r({\cal M}_{SP}\circ P)]+[r({\cal M}_{PQ})-r({\cal
M}_{PQ}\circ P)]-r({\cal M}_{SP}\times P\wedge{\cal M}_{PQ}\times P)+r(({\cal
M}_{SP}\circ P)\wedge({\cal M}_{PQ}\circ P))$
$=r({\cal M}_{SP}\times S)+r({\cal M}_{PQ}\times Q)+r({\cal M}_{SP}\circ
P\wedge{\cal M}_{PQ}\circ P)-r({\cal M}_{SP}\times P\wedge{\cal M}_{PQ}\times
P).$

∎

The following pair of results are from [33].

######  Theorem 49.

$\mbox{$\cal M$}_{SP}\leftrightarrow\mbox{$\cal M$}_{PQ}=(\mbox{$\cal
M$}_{SP}\vee\mbox{$\cal M$}_{PQ})\times(S\cup Q)=(\mbox{$\cal
M$}_{SP}\wedge\mbox{$\cal M$}_{PQ})\circ(S\cup Q)$

######  Theorem 50.

(Implicit Duality Theorem (IDT))

$(\mbox{$\cal M$}_{SP}\leftrightarrow\mbox{$\cal M$}_{PQ})^{*}=\mbox{$\cal
M$}_{SP}^{*}\leftrightarrow\mbox{$\cal M$}_{PQ}^{*}$

###### Proof.

$\displaystyle(\mbox{$\cal M$}_{SP}\leftrightarrow\mbox{$\cal M$}_{PQ})^{*}$
$\displaystyle=$ $\displaystyle[(\mbox{$\cal M$}_{SP}\vee\mbox{$\cal
M$}_{PQ})\times(S\cup Q)]^{*}$ $\displaystyle=$ $\displaystyle(\mbox{$\cal
M$}_{SP}\vee\mbox{$\cal M$}_{PQ})^{*}\circ(S\cup Q)\mbox{ (using Theorem
\ref{thm:dotcrossidentitym}).}$ $\displaystyle=$ $\displaystyle(\mbox{$\cal
M$}_{SP}^{*}\wedge\mbox{$\cal M$}_{PQ}^{*})\circ(S\cup Q)$ $\displaystyle=$
$\displaystyle(\mbox{$\cal M$}_{SP}^{*}\vee\mbox{$\cal
M$}_{PQ}^{*})\times(S\cup Q)\mbox{ (using Theorem \ref{thm:matchedpropm}).}$
$\displaystyle=$ $\displaystyle\mbox{$\cal
M$}_{SP}^{*}\leftrightarrow\mbox{$\cal M$}_{PQ}^{*}.$

∎

We have deliberately written the above results in a form that mimics that of
corresponding results for vector spaces.

The substitution rules are

$\displaystyle{Vector\ space\ entity}$ $\displaystyle{Matroid\ entity}$
$\displaystyle{Vector\ space\ entity}$ $\displaystyle{Matroid\ entity}$ column
base base column cobase cobase $\displaystyle\ \ \ \ \
\mbox{$\mathcal{V}$}_{X}$ $\displaystyle\ \ \ \ \mbox{$\cal M$}_{X}$
$\displaystyle\ \ \ \ \mbox{$\mathcal{V}$}_{X}^{\perp}$ $\displaystyle\ \ \ \
\mbox{$\cal M$}_{X}^{*}$ $\displaystyle\ \ \ \ \mbox{$\cal F$}_{A}$
$\displaystyle\ \ \ \ \mbox{$\cal F$}_{A}$ $\displaystyle\ \ \ \
{\mathbf{0}}_{A}$ $\displaystyle\ \ \ \ {\mathbf{0}}_{A}$ $\displaystyle\ \ \
\ \mbox{$\mathcal{V}$}_{X}\oplus\mbox{$\mathcal{V}$}_{Y}$ $\displaystyle\ \ \
\ \mbox{$\cal M$}_{X}\oplus\mbox{$\cal M$}_{Y}$ $\displaystyle\ \ \ \
\mbox{$\mathcal{V}$}_{X}+\mbox{$\mathcal{V}$}_{Y}$ $\displaystyle\ \ \ \
\mbox{$\cal M$}_{X}\vee\mbox{$\cal M$}_{Y}$ $\displaystyle\ \ \ \
\mbox{$\mathcal{V}$}_{X}\cap\mbox{$\mathcal{V}$}_{Y}$ $\displaystyle\ \ \ \
\mbox{$\cal M$}_{X}\wedge\mbox{$\cal M$}_{Y}$ $\displaystyle\ \ \ \
\mbox{$\mathcal{V}$}_{X}\leftrightarrow\mbox{$\mathcal{V}$}_{Y}$
$\displaystyle\ \ \ \ \mbox{$\cal M$}_{X}\leftrightarrow\mbox{$\cal M$}_{Y}$
$\displaystyle\ \ \ \ \mbox{$\mathcal{V}$}_{AB}\circ B$ $\displaystyle\ \ \ \
\mbox{$\cal M$}_{AB}\circ B$ $\displaystyle\ \ \ \
\mbox{$\mathcal{V}$}_{AB}\times B$ $\displaystyle\ \ \ \ \mbox{$\cal
M$}_{AB}\times B$

The corresponding pairs are Theorems 42,1, Theorems 43,2, Theorems 44,3,
Lemmas 46,4,
Theorems 47,5, Theorems 48,6, Theorems 49,7 and Theorems 50,11.

###  6.2 Rigidity of matroid pairs

We show in this subsection, that there is a notion analogous to rigidity of
vector space pairs in the matroid context and the properties of rigid pairs of
matroids mimic those of rigid pairs of vector spaces. This fact is used
finally in Theorem 56, to examine under what conditions rigidity of a vector
space pair can be inferred from that of the associated matroid pair.

######  Definition 51.

Let $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}$ be matroids on sets $A\uplus
B,B\uplus C,$ respectively, A,B,C being pairwise disjoint. We say the pair
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ has the full sum property
iff $\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B=\mbox{$\cal
F$}_{B}.$
We say the pair $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ has the zero
intersection property iff $\mbox{$\cal M$}_{AB}\times B\wedge\mbox{$\cal
M$}_{BC}\times B={\mathbf{0}}_{B}.$
We say $\mbox{$\cal M$}_{AB}$ is rigid with respect to $\mbox{$\cal M$}_{BC},$
or that the pair $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid,
iff it has the full sum property and the zero intersection property.
When $B=\emptyset,$ we take $\\{\mbox{$\cal M$}_{A},\mbox{$\cal M$}_{C}\\}$ to
be rigid .

When matroids are direct sums of other matroids, it is clear from the
definition that rigidity involving the former can be inferred from rigidity
involving the latter.

######  Lemma 52.

The pair $\\{\mbox{$\cal M$}_{AB}\oplus\mbox{$\cal M$}_{CD},\mbox{$\cal
M$}^{1}_{B}\oplus\mbox{$\cal M$}^{2}_{C}\\}$ is rigid iff the pairs
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}^{1}_{B}\\},$ $\\{\mbox{$\cal
M$}_{CD},\mbox{$\cal M$}^{2}_{C}\\}$ are rigid.

The next result states the basic facts about rigid pairs of matroids.

######  Theorem 53.

Let $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ be a rigid pair of
matroids. We then have the following

  1. 1.

The full sum property of $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is
equivalent to $(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\circ
B=\mbox{$\cal F$}_{B},$ equivalently, to there being bases $b_{AB},b_{BC}$ of
$\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC},$ respectively such that
$b_{AB}\cup b_{BC}\supseteq B.$

  2. 2.

The zero intersection property of $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal
M$}_{BC}\\}$ is equivalent to $(\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal
M$}_{BC})\times B={\mathbf{0}}_{B},$ equivalently, to there being bases
$b_{AB},b_{BC}$ of $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC},$ respectively
such that $b_{AB}\cap b_{BC}=\emptyset.$

  3. 3.

The pair $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid
iff $r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC})$ and $r(\mbox{$\cal
M$}_{AB}^{*}\vee\mbox{$\cal M$}_{BC}^{*})=r(\mbox{$\cal
M$}_{AB}^{*})+r(\mbox{$\cal M$}_{BC}^{*}).$

  4. 4.

The pair $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ has the zero
intersection (full sum) property iff $\\{\mbox{$\cal M$}^{*}_{AB},\mbox{$\cal
M$}^{*}_{BC}\\}$ has the full sum (zero intersection) property. Therefore
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid iff $\\{\mbox{$\cal
M$}^{*}_{AB},\mbox{$\cal M$}^{*}_{BC}\\}$ is rigid.

  5. 5.

$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid iff there exist
disjoint bases $b_{AB},b_{BC}$ of $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}$
respectively such that $b_{AB}\cup b_{BC}\supseteq B.$

###### Proof.

1\. Note that $\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC}:\equiv(\mbox{$\cal
M$}_{AB}\oplus{\mathbf{0}}_{C})\vee(\mbox{$\cal
M$}_{BC}\oplus{\mathbf{0}}_{A}).$
It is clear that $(\mbox{$\cal M$}_{AB}\circ B)\vee(\mbox{$\cal M$}_{BC}\circ
B)=(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\circ B,$ so that
$(\mbox{$\cal M$}_{AB}\circ B)\vee(\mbox{$\cal M$}_{BC}\circ B)=\mbox{$\cal
F$}_{B}$ is equivalent to $(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\circ
B=\mbox{$\cal F$}_{B}.$
The latter statement is the same as there being bases $b_{AB},b_{BC}$ of
$\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC},$ respectively such that
$b_{AB}\cup b_{BC}\supseteq B.$

2\. Note that $\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal
M$}_{BC}:\equiv(\mbox{$\cal M$}_{AB}\oplus\mbox{$\cal
F$}_{C})\wedge(\mbox{$\cal M$}_{BC}\oplus\mbox{$\cal F$}_{A}).$
We have $(\mbox{$\cal M$}_{AB}\times B)\wedge(\mbox{$\cal M$}_{BC}\times
B)=(\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal M$}_{BC})\times B$ (using part 5 of
Theorem 47), so that
$(\mbox{$\cal M$}_{AB}\times B)\wedge(\mbox{$\cal M$}_{BC}\times
B)={\mathbf{0}}_{B}$ is equivalent to $(\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal
M$}_{BC})\times B={\mathbf{0}}_{B}.$
The latter statement is the same as there being bases $b_{AB},b_{BC}$ of
$\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC},$ respectively such that
$b_{AB}\cap b_{BC}=\emptyset.$

3\. Let $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ be rigid . Then
$(\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B)=\mbox{$\cal
F$}_{B}$ and $(\mbox{$\cal M$}_{AB}\times B\wedge\mbox{$\cal M$}_{BC}\times
B)={\mathbf{0}}_{B}.$
Now, using Theorem 47 and the zero intersection property,
$r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC})-r(\mbox{$\cal M$}_{AB}\times
B\wedge\mbox{$\cal M$}_{BC}\times B)=r(\mbox{$\cal M$}_{AB})+r(\mbox{$\cal
M$}_{BC}).$
Next $(\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B)=\mbox{$\cal
F$}_{B}$ iff $(\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ
B)^{*}=\mbox{$\cal F$}_{B}^{*},$ i.e., $(\mbox{$\cal M$}_{AB}^{*}\times
B\wedge\mbox{$\cal M$}_{BC}^{*}\times B)={\mathbf{0}}_{B}.$ Using the above
argument, we therefore have $r(\mbox{$\cal M$}_{AB}^{*}\vee\mbox{$\cal
M$}_{BC}^{*})=r(\mbox{$\cal M$}_{AB}^{*})+r(\mbox{$\cal M$}_{BC}^{*}).$
On the other hand, suppose $r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal
M$}_{BC})=r(\mbox{$\cal M$}_{AB})+r(\mbox{$\cal M$}_{BC})$ and $r(\mbox{$\cal
M$}_{AB}^{*}+\mbox{$\cal M$}_{BC}^{*})$
$=r(\mbox{$\cal M$}_{AB}^{*})+r(\mbox{$\cal M$}_{BC}^{*}).$
The former condition implies $r(\mbox{$\cal M$}_{AB}\times B\wedge\mbox{$\cal
M$}_{BC}\times B)=0,$ i.e., $(\mbox{$\cal M$}_{AB}\times B\wedge\mbox{$\cal
M$}_{BC}\times B)={\mathbf{0}}_{B}.$ and the latter implies $r(\mbox{$\cal
M$}_{AB}^{*}\times B\wedge\mbox{$\cal M$}_{BC}^{*}\times B)=0,$ i.e.,
$(\mbox{$\cal M$}_{AB}^{*}\times B\wedge\mbox{$\cal M$}_{BC}^{*}\times
B)={\mathbf{0}}_{B},$ i.e., $(\mbox{$\cal M$}_{AB}^{*}\times
B\wedge\mbox{$\cal M$}_{BC}^{*}\times B)^{*}=(\mbox{$\cal M$}_{AB}\circ
B\vee\mbox{$\cal M$}_{BC}\circ B)=\mbox{$\cal F$}_{B}$ (using parts 3 and 4 of
Theorems 47,43).

4\. We have, $(\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ
B)^{*}=\mbox{$\cal M$}_{AB}^{*}\times B\ \wedge\ \mbox{$\cal
M$}_{BC}^{*}\times B.$ Therefore $(\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal
M$}_{BC}\circ B)=\mbox{$\cal F$}_{B}$ iff $\mbox{$\cal M$}_{AB}^{*}\times B\
\wedge\ \mbox{$\cal M$}_{BC}^{*}\times B={\mathbf{0}}_{B}.$ Next $(\mbox{$\cal
M$}_{AB}\times B\ \wedge\ \mbox{$\cal M$}_{BC}\times B)^{*}=\mbox{$\cal
M$}_{AB}^{*}\circ B\vee\mbox{$\cal M$}_{BC}^{*}\circ B.$ Therefore
$(\mbox{$\cal M$}_{AB}\times B\ \wedge\ \mbox{$\cal M$}_{BC}\times
B)={\mathbf{0}}_{B}$ iff $\mbox{$\cal M$}_{AB}^{*}\circ B\vee\mbox{$\cal
M$}_{BC}^{*}\circ B=\mbox{$\cal F$}_{B}.$

5\. Let $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ be rigid and let
$b_{AC}$ be a base of $\mbox{$\cal M$}_{AB}\leftrightarrow\mbox{$\cal
M$}_{BC}=(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\times AC.$ Then there
exists a base $b_{ABC}$ of $\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC}$ such
that $b_{AC}=b_{ABC}\cap(A\uplus C).$ Since $\\{\mbox{$\cal
M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid, by part 3 above, we must have
$r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC}).$ Therefore there exist disjoint bases
$b_{AB},b_{BC}$ of $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC},$ respectively
such that $b_{ABC}=b_{AB}\uplus b_{BC}.$ We have,
$|b_{AC}|=|b_{AB}\uplus b_{BC}|-|(b_{AB}\uplus b_{BC})\cap B|=r(\mbox{$\cal
M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC})=r((\mbox{$\cal
M$}_{AB}\vee\mbox{$\cal M$}_{BC})\times AC)$
$=r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})-r((\mbox{$\cal
M$}_{AB}\vee\mbox{$\cal M$}_{BC})\circ B)=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC})-|B|$ (using full sum property of
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$). We conclude that
$(b_{AB}\uplus b_{BC})\cap B=B.$
Thus rigidity of $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ implies
that there exist disjoint bases of $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}$
which cover $B.$

On the other hand suppose that there exist disjoint bases of $\mbox{$\cal
M$}_{AB},\mbox{$\cal M$}_{BC}$ which cover $B.$ It is clear that we must have
$r(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC})$ and $r(\mbox{$\cal
M$}^{*}_{AB}\vee\mbox{$\cal M$}^{*}_{BC})=r(\mbox{$\cal
M$}^{*}_{AB})+r(\mbox{$\cal M$}^{*}_{BC}),$ so that the rigidity of
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ follows.

∎

The next lemma is of use for characterizing rigid networks without ports and,
in the case of rigid multiports, the dimension of the multiport of the
multiport behaviour. Proof is given in A.

######  Lemma 54.

  1. 1.

Let $\mbox{$\cal M$}^{1}_{B},\mbox{$\cal M$}^{2}_{B}$ be matroids on $B.$ If
$r(\mbox{$\cal M$}^{1}_{B})+r(\mbox{$\cal M$}^{2}_{B})=|B|,$ then the full sum
property and zero intersection property are equivalent

  2. 2.

If $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid then
$r(\mbox{$\cal M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB})+r(\mbox{$\cal M$}_{BC})-|B|.$

The following result is parallel to Theorem 24. Its proof is a line by line
translation of that of Theorem 24 and is shifted to A.

######  Theorem 55.

Let $\mbox{$\cal M$}_{WTV},\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T},$ be
matroids on $W\uplus T\uplus V,V,T,$
respectively. Then $\\{\mbox{$\cal M$}_{WTV},\mbox{$\cal
M$}_{T}\oplus\mbox{$\cal M$}_{V}\\}$ is rigid

  1. 1.

iff $\\{\mbox{$\cal M$}_{WTV},\mbox{$\cal M$}_{V}\\},$ $\\{\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}$ are rigid;

  2. 2.

iff $\\{\mbox{$\cal M$}_{WTV},\mbox{$\cal M$}_{V}\\}$ is rigid,
$\\{\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\},$
$\\{\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}$
satisfy the full sum and zero intersection properties respectively;

  3. 3.

iff $\\{\mbox{$\cal M$}_{WTV},\mbox{$\cal M$}_{V}\\},$ $\\{\mbox{$\cal
M$}_{WTV}\wedge\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\},$ $\\{\mbox{$\cal
M$}_{WTV}\vee\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}$ are rigid.

###  6.3 Testing rigidity of vector space pairs through associated matroid
pairs

Matroids associated with rigid pairs of vector spaces are always rigid. But
under certain commonly occurring situations, the converse is also true. This
fact is useful for testing the rigidity of the original pairs of vector spaces
avoiding linear algebraic computations.

######  Theorem 56.

Let $\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}$ be vector spaces on
$A\uplus B,B\uplus C,$ respectively with $A,B,C$ pairwise disjoint. We then
have the following.

  1. 1.

If $\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}\\}$ is rigid then
so is $\\{\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})\\}.$

  2. 2.

Suppose $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{BC})$
and $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB}+\mbox{$\mathcal{V}$}^{\perp}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{BC}).$
Then

    1. (a)

$\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\cap\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\wedge\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}\cap\mbox{$\mathcal{V}$}_{BC}^{\perp})=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}))^{*}\wedge(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))^{*}$

    2. (b)

$\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\leftrightarrow\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC});$

    3. (c)

$\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}\\}$ is rigid iff
$\\{\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})\\}$ is rigid.

###### Proof.

We will use the following facts.
(a) $\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{X}\circ Z)=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{X}))\circ Z,\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{X}\times Z)=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{X}))\times Z,$
$(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{X})^{\perp})=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{X}))^{*},Z\subseteq X$ (Lemma 45).
(b) $\mbox{$\cal M$}^{1}_{X}\wedge\mbox{$\cal M$}^{2}_{X}:\equiv((\mbox{$\cal
M$}^{1}_{X})^{*}\vee(\mbox{$\cal M$}^{2}_{X})^{*})^{*}.$
When $A,B,C$ are pairwise disjoint, $\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal
M$}_{BC}:\equiv(\mbox{$\cal M$}_{AB}\oplus\mbox{$\cal
F$}_{C})\wedge(\mbox{$\cal M$}_{BC}\oplus\mbox{$\cal F$}_{A})$
$=((\mbox{$\cal M$}_{AB}\oplus\mbox{$\cal F$}_{C})^{*}\vee(\mbox{$\cal
M$}_{BC}\oplus\mbox{$\cal F$}_{A})^{*})^{*}=(\mbox{$\cal
M$}_{AB}^{*}\oplus{\mathbf{0}}_{C})\vee(\mbox{$\cal
M$}_{BC}^{*}\oplus{\mathbf{0}}_{A}))^{*}=(\mbox{$\cal
M$}_{AB}^{*}\vee\mbox{$\cal M$}_{BC}^{*})^{*}$ (Theorem 50).
(c) When $A,B,C$ are pairwise disjoint, $(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal
M$}_{BC})\circ B=(\mbox{$\cal M$}_{AB}\circ B)\vee(\mbox{$\cal M$}_{BC}\circ
B),(\mbox{$\cal M$}_{AB}\wedge\mbox{$\cal M$}_{BC})\times B=(\mbox{$\cal
M$}_{AB}\times B)\wedge(\mbox{$\cal M$}_{BC}\times B)$ (Theorem 47).
(d) $r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC}))\leq r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})).$

1\. $\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}\\}$ is rigid iff
$r(\mbox{$\mathcal{V}$}_{AB})+r(\mbox{$\mathcal{V}$}_{BC})=r(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})$
and
$r(\mbox{$\mathcal{V}$}_{AB}^{\perp})+r(\mbox{$\mathcal{V}$}_{BC}^{\perp})$
$=r(\mbox{$\mathcal{V}$}_{AB}^{\perp}+\mbox{$\mathcal{V}$}_{BC}^{\perp}),$ by
part 4 of Theorem 17. Therefore, if
$\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}\\}$ is rigid then we
have,
$r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))=r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC}))\leq r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{BC}))$
and $r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp}))$
$=r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}+\mbox{$\mathcal{V}$}_{BC}^{\perp}))\leq
r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp})).$ But, by definition of the matroid
union operation, $r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))\geq r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{BC}))$
and $r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp}))$
$\geq r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp})).$ We therefore conclude that
$r(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))=r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{BC}))$
and $r((\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}))^{*})+r((\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))^{*})=r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}))+r(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp}))=r((\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}))^{*}\vee(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))^{*})$ and by part 3 of Theorem 53, it follows
that $\\{\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})\\}$ is rigid.

2(a) We are given that $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{BC}).$
We then have $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\cap\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}_{AB}^{\perp}+\mbox{$\mathcal{V}$}_{BC}^{\perp})^{\perp})=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}^{\perp}))^{*}$
$=((\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}))^{*}\vee(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))^{*})^{*}=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\wedge\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}),$ using facts (a) and (b).
Similarly, from $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB}+\mbox{$\mathcal{V}$}^{\perp}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{BC}),$ it follows that
$\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}^{\perp}\cap\mbox{$\mathcal{V}$}_{BC}^{\perp})=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}))^{*}\wedge(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))^{*}.$

2(b) We have $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})\times
B)=(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC}))\times B$
$=(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))\times B=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\leftrightarrow\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}),$ using the hypothesis of the theorem, fact
(a), and the definition of the ‘$\leftrightarrow$’ operation for matroids.

2(c) The pair $\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{BC}\\}$ is
rigid iff $\mbox{$\mathcal{V}$}_{AB}\circ B+\mbox{$\mathcal{V}$}_{BC}\circ
B=\mbox{$\cal F$}_{B}$ and $\mbox{$\mathcal{V}$}_{AB}\times
B\cap\mbox{$\mathcal{V}$}_{BC}\times B={\mathbf{0}}_{B},$
i.e., iff $(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})\circ
B=\mbox{$\cal F$}_{B}$ and
$(\mbox{$\mathcal{V}$}_{AB}\cap\mbox{$\mathcal{V}$}_{BC})\times
B={\mathbf{0}}_{B},$
i.e., iff $\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{BC})\circ B)=\mbox{$\cal
F$}_{B}$ and $\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}_{AB}\cap\mbox{$\mathcal{V}$}_{BC})\times
B)={\mathbf{0}}_{B},$
ı.e., iff $(\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))\circ B=\mbox{$\cal F$}_{B}$ and $(\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\wedge\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC}))\times B={\mathbf{0}}_{B}$
i.e., iff $\\{\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{AB}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})\\}$ is rigid, using fact (c), hypothesis of
part 2 of the theorem and part 2(a) above. ∎

###  6.4 Rigidity and matroid duality

We show in this subsection that when we have matroid duality, we automatically
have rigidity. This suggests rigidity can be regarded as a weak form of
matroid duality.

######  Lemma 57.

Let $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}$ be matroids, $A,B,C,$ being
pairwise disjoint, such that
$(\mbox{$\cal M$}_{AB}\circ B)^{*}=\mbox{$\cal M$}_{BC}\times B.$ We then have
the following.

  1. 1.

$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid;

  2. 2.

$\\{\mbox{$\cal M$}_{AB},(\mbox{$\cal M$}^{*}_{AB})_{\tilde{A}B}\\},$ is
rigid, where $\tilde{A}$ is a copy of $A$ disjoint from $A,B;$

###### Proof.

1\. Since $(\mbox{$\cal M$}_{AB}\circ B)^{*}=\mbox{$\cal M$}_{BC}\times B,$ we
must have $\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\times
B=\mbox{$\cal F$}_{B}.$ Now every independent set of $\mbox{$\cal
M$}_{BC}\times B$ is contained in an independent set of $\mbox{$\cal
M$}_{BC}\circ B.$ Therefore $\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal
M$}_{BC}\circ B=\mbox{$\cal F$}_{B},$ i.e., the full sum property holds for
$\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}.$
Next $(\mbox{$\cal M$}_{AB}\circ B)^{**}=(\mbox{$\cal M$}_{BC}\times B)^{*}.$
Therefore, $(\mbox{$\cal M$}_{AB}^{*}\times B)^{*}=\mbox{$\cal
M$}_{BC}^{*}\circ B,$ i.e., $(\mbox{$\cal M$}_{BC}^{*}\circ B)^{*}=\mbox{$\cal
M$}_{AB}^{*}\times B.$ By the argument above, this means $\mbox{$\cal
M$}_{BC}^{*}\circ B\vee\mbox{$\cal M$}_{AB}^{*}\times B=\mbox{$\cal F$}_{B},$
i.e., the full sum property holds for $\\{\mbox{$\cal M$}_{AB}^{*},\mbox{$\cal
M$}_{BC}^{*}\\}.$ By part 4 of Theorem 53, this means that the zero
intersection property holds for $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal
M$}_{BC}\\}.$

We conclude that $\\{\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}\\}$ is rigid.

2\. We note that $(\mbox{$\cal M$}_{AB}\circ B)^{*}=\mbox{$\cal
M$}_{AB}^{*}\times B=(\mbox{$\cal M$}^{*}_{AB})_{\tilde{A}B}\times B.$ The
result now follows from part 1 above. ∎

######  Remark 7.

We have that $\\{\mbox{$\cal M$}_{X},\mbox{$\cal M$}_{X}^{*}\\}$ is rigid. By
Theorem 50, $\\{\mbox{$\cal M$}_{A}\leftrightarrow\mbox{$\cal
M$}_{B},\mbox{$\cal M$}^{*}_{A}\leftrightarrow\mbox{$\cal
M$}^{*}_{B}\\},B\subseteq A,$ is also rigid. We have that $\\{\mbox{$\cal
M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{A},(\mbox{$\cal
M$}^{1}_{A})^{*}\wedge(\mbox{$\cal M$}^{2}_{A})^{*}\\}$ is rigid since
$(\mbox{$\cal M$}^{1}_{A}\vee\mbox{$\cal M$}^{2}_{A})^{*}=(\mbox{$\cal
M$}^{1}_{A})^{*}\wedge(\mbox{$\cal M$}^{2}_{A})^{*}.$
There appear to be no counterparts to these facts in terms of rigidity without
using duality.

###  6.5 Computing a column base of
$\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC}$

Finding a column base of
$\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC}$ requires
linear algebraic computations. However, when the conditions of part 2 of
Theorem 56 are satisfied, we have $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\leftrightarrow\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{BC})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC}).$ Bases
of $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC})$ and
column bases of
$\mbox{$\mathcal{V}$}_{AB}\leftrightarrow\mbox{$\mathcal{V}$}_{BC}$ are
identical. The problem of computing a base of $\mbox{$\cal
M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC}$ given an ‘independence oracle’ of
the matroids $\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC}$ is one whose solution
is nontrivial but known. First, we find a pair of maximally distant bases
$b^{1}_{B},b^{2}_{B}$ for the matroids $\mbox{$\cal M$}_{AB}\circ
B,\mbox{$\cal M$}_{BC}\circ B$ using the well known matroid union algorithm
essentially due to J. Edmonds [3]. It follows that $b^{1}_{B}\cup b^{2}_{B}$
is a basis for $(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\circ
B=\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B.$ We then extend
these bases to $b^{1}_{AB},b^{2}_{BC}$ of $\mbox{$\cal M$}_{AB},\mbox{$\cal
M$}_{BC}$ respectively. Then $b^{1}_{AB}\cup b^{2}_{BC}$ is a basis of
$\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC}$ that contains the basis
$b^{1}_{B}\cup b^{2}_{B}$ of $(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal
M$}_{BC})\circ B.$ Therefore,
$(b^{1}_{AB}-b^{1}_{B})\uplus(b^{2}_{BC}-b^{2}_{B})$ is a base of
$(\mbox{$\cal M$}_{AB}\vee\mbox{$\cal M$}_{BC})\times(A\uplus C)=\mbox{$\cal
M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC}.$ A detailed discussion of the
matroid union algorithm may be found in [31],[19]. Fortunately for us, in the
most important cases where we have to find maximally distant bases, we can do
so by computing one of them to satisfy some simple properties.

###  6.6 Rigid families of matroids

The notion of rigidity of families carries over from vector spaces to matroids
routinely. For this purpose we first give a definition of rigidity for
families relevant to our problem (‘associative families’) and then justify the
definition by describing the properties of rigid associative families through
subsequent lemmas.

######  Definition 58.

An associative family $\mathcal{H}:\equiv\\{\mbox{$\cal
M$}_{Y_{i}},i=1,\cdots,m\\}$ is a family of matroids where no element in
$Y:\equiv\bigcup_{i=1}^{m}Y_{i}$ belongs to more than two of the $Y_{i}.$ When
$Y_{i}=\emptyset,$ we will take $\mbox{$\cal M$}_{Y_{i}}=\mbox{$\cal
M$}_{\emptyset}:\equiv\emptyset.$ Let
$\mathcal{H}_{nonvoid}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=1,\cdots,t\\}$ be
the subfamily of $\mathcal{H}$ whose elements are non void matroids that
belong to $\mathcal{H}.$ For $i=1,\cdots,t,$ let $Z_{i}$ be the subset of
elements of $Y_{i}$ which belong to none of the $Y_{j},j\neq i$ and let
$Z:\equiv\bigcup_{i=1}^{t}Z_{i}.$
We define
$\boldsymbol{\leftrightarrow(\mathcal{H})}:\equiv(\bigvee_{i=1}^{t}\mbox{$\cal
M$}_{Y_{i}}))\times Z=(\mbox{$\cal M$}_{Y_{1}}\vee\cdots\vee\mbox{$\cal
M$}_{Y_{t}})\times Z.$

######  Definition 59.

For an associative family $\mathcal{H}:\equiv\\{\mbox{$\cal
M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{m}}\\},$ the graph $\boldsymbol{{\cal
G}_{\mathcal{H}}}$ is defined to have vertices $\mbox{$\cal
M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{m}},$ edges $Y_{1}\cup\cdots\cup Y_{m}$
with an edge $e$ lying between vertices $\mbox{$\cal M$}_{Y_{i}},\mbox{$\cal
M$}_{Y_{j}}$ iff $e\in Y_{i}\cap Y_{j}.$ We will refer to ${\cal
G}_{\mathcal{H}}$ as the graph of $\mathcal{H}.$

######  Remark 8.

We note the following.

  1. 1.

The operation $\leftrightarrow(\cdot)$ is well defined over associative
families and agrees with the corresponding operation over pairs of matroids.
If $\mathcal{H}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\mbox{$\cal
M$}_{Y_{2}},\mbox{$\cal M$}_{Y_{3}}\\},$ is an associative family, it can be
shown that
$\leftrightarrow(\mathcal{H})=(\mbox{$\cal
M$}_{Y_{1}}\leftrightarrow\mbox{$\cal M$}_{Y_{2}})\leftrightarrow\mbox{$\cal
M$}_{Y_{3}}=\mbox{$\cal M$}_{Y_{1}}\leftrightarrow(\mbox{$\cal
M$}_{Y_{2}}\leftrightarrow\mbox{$\cal M$}_{Y_{3}})$ [33]. By induction it
follows that, treated as a binary operation, $\leftrightarrow(\cdot)$ is
associative over an associative family $\mathcal{H}$ and, independent of the
way the brackets are constructed this operation reduces to
$\leftrightarrow(\mathcal{H}).$

  2. 2.

Suppose $\mathcal{H}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=1,\cdots,m\\}$ is an
associative family with every element of $\bigcup_{i=1}^{m}\mbox{$\cal
M$}_{Y_{i}}$ belonging to exactly two of the $Y_{i}.$ Then
$(\leftrightarrow(\mathcal{H}))=\emptyset.$ For consistency of notation, in
this case we denote $\leftrightarrow(\mathcal{H})$ by $\mbox{$\cal
M$}_{\emptyset}.$ We note that, by the definition of the operations
$\vee,\wedge,\leftrightarrow(\cdot),$ we must have $(\mbox{$\cal
M$}_{\emptyset}\vee\mbox{$\cal M$}_{X})=(\mbox{$\cal
M$}_{\emptyset}\wedge\mbox{$\cal M$}_{X})=(\mbox{$\cal
M$}_{\emptyset}\leftrightarrow\mbox{$\cal M$}_{X})=\mbox{$\cal M$}_{X}.$ The
following result is known [33].

######  Lemma 60.

Let $\mathcal{H}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal
M$}_{Y_{m}}\\}$ be an associative family of matroids. Let $Z$ be the subset of
elements of $\bigcup_{i}Y_{i}$ that belong to only one of the $Y_{i}.$ Then
$\boldsymbol{\leftrightarrow(\mathcal{H})}$
$:\equiv(\bigwedge_{i=1}^{m}\mbox{$\cal M$}_{Y_{i}}))\circ Z=(\mbox{$\cal
M$}_{Y_{1}}\wedge\cdots\wedge\mbox{$\cal M$}_{Y_{m}})\circ Z.$

  3. 3.

If the graph ${\cal G}_{\mathcal{H}}$ has edges and is connected, then it does
not have isolated vertices. This means $\mathcal{H}$ has no element which is
equal to $\mbox{$\cal M$}_{\emptyset}.$ Further, if it is connected and has at
least one selfloop, no subfamily $\mathcal{H}_{1}$ of $\mathcal{H}$ would be
such that $\leftrightarrow(\mathcal{H}_{1})=\mbox{$\cal M$}_{\emptyset}.$

  4. 4.

Let $\mathcal{H}=\mathcal{H}_{1}\uplus\mathcal{H}_{2}.$ Then
$\leftrightarrow(\mathcal{H})\ =\
(\leftrightarrow(\mathcal{H}_{1}))\leftrightarrow(\leftrightarrow(\mathcal{H}_{2})).$

  5. 5.

By induction on the size of $\mathcal{H},$ one can prove the following
generalization of Theorem 11:

######  Theorem 61.

Let $\mathcal{H}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=1,\cdots,m\\}$ be an
associative family of matroids and let
$\mathcal{H}^{*}:\equiv\\{\mbox{$\cal M$}^{*}_{Y_{i}},i=1,\cdots,m\\}.$ Then
$(\leftrightarrow(\mathcal{H}))^{*}=(\leftrightarrow(\mathcal{H}^{*})).$

######  Definition 62.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal
M$}_{Y_{n}}\\}$ be an associative family of matroids. We say ${\mathcal{H}}$
is rigid iff the following rank conditions are satisfied.

  * 1.

(primal) $r(\Sigma_{i}\mbox{$\cal M$}_{Y_{i}})=\Sigma_{i}r(\mbox{$\cal
M$}_{Y_{i}});$

  * 2.

(dual) $r(\Sigma_{i}\mbox{$\cal M$}^{*}_{Y_{i}})=\Sigma_{i}r(\mbox{$\cal
M$}^{*}_{Y_{i}}).$

We note that the definition of rigid families of matroids agrees with that of
a pair of matroids (by part 3 of Theorem 53).

We have the following simple lemma.

######  Lemma 63.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal
M$}_{Y_{n}}\\}$ be an associative family of matroids with ${\cal
G}_{\mathcal{H}}$ connected and with non empty edge set. If $\mathcal{H}$ is
rigid then every subfamily of ${\mathcal{H}}$ is rigid.

###### Proof.

Without loss of generality, it is adequate to show that $\\{\mbox{$\cal
M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{m}}\\},m<n$ is rigid. Now
$r(\mbox{$\cal M$}_{Y_{1}}\vee\cdots\vee\mbox{$\cal M$}_{Y_{m}})\leq
r(\mbox{$\cal M$}_{Y_{1}})+\cdots+r(\mbox{$\cal M$}_{Y_{m}})$ and
$r(\bigvee_{i=1}^{n}\mbox{$\cal M$}_{Y_{i}})\leq
r(\bigvee_{i=1}^{m}\mbox{$\cal M$}_{Y_{i}})+r(\bigvee_{i=m+1}^{n}\mbox{$\cal
M$}_{Y_{i}}).$ Therefore the primal rank condition of rigidity is true for
$\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{n}}\\}$ only if it is
true for $\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{m}}\\}.$ The
proof for the dual rank condition is essentially the same. ∎

The following lemma addresses the rigidity of a common class of associative
families.

######  Lemma 64.

Let $\mathcal{H}_{1}:\equiv\\{\mbox{$\cal M$}_{X_{1}},\cdots,\mbox{$\cal
M$}_{X_{n}}\\},$ and let $\mathcal{H}_{2}:\equiv\\{\mbox{$\cal
M$}_{Y_{1}},\cdots,\mbox{$\cal M$}_{Y_{m}}\\},$ with the $X_{i},$ being
pairwise disjoint and the $Y_{j}$ also. Then the associative family
$\mathcal{H}_{1}\uplus\mathcal{H}_{2}$ is rigid iff the pair
$\\{\oplus\mbox{$\cal M$}_{X_{i}},\oplus\mbox{$\cal M$}_{Y_{j}}\\},$ is rigid.

###### Proof.

We have
$r(\mbox{$\cal M$}_{X_{1}}\oplus\cdots\oplus\mbox{$\cal
M$}_{X_{n}})=r(\mbox{$\cal M$}_{X_{1}})+\cdots+r(\mbox{$\cal M$}_{X_{n}}),\
r(\mbox{$\cal M$}_{Y_{1}}\oplus\cdots\oplus\mbox{$\cal
M$}_{Y_{m}})=r(\mbox{$\cal M$}_{Y_{1}})+\cdots+r(\mbox{$\cal M$}_{Y_{n}}),$
$r(\mbox{$\cal M$}^{*}_{X_{1}}\oplus\cdots\oplus\mbox{$\cal
M$}^{*}_{X_{n}})=r(\mbox{$\cal M$}^{*}_{X_{1}})+\cdots+r(\mbox{$\cal
M$}^{*}_{X_{n}}),\ r(\mbox{$\cal M$}^{*}_{Y_{1}}\oplus\cdots\oplus\mbox{$\cal
M$}^{*}_{Y_{m}})=r(\mbox{$\cal M$}^{*}_{Y_{1}})+\cdots+r(\mbox{$\cal
M$}^{*}_{Y_{n}}).$
The result now follows from part 3 of Theorem 53. ∎

We now have a result which expresses rigidity of associative families
recursively.

######  Theorem 65.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal
M$}_{Y_{n}}\\}$ be an associative family of matroids with ${\cal
G}_{\mathcal{H}}$ connected and with non empty edge set. Let ${\mathcal{H}}$
be partitioned as ${\mathcal{H}_{1}}\uplus{\mathcal{H}_{2}}.$ Then
${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},{\mathcal{H}_{2}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow(\mathcal{H}_{2})\\}$ are
rigid.

The proof of Theorem 65 is based on the following lemma.

######  Lemma 66.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=1,\cdots,m\\}$ and let
${\mathcal{H}}_{1}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=1,\cdots,t\\},t<m,$
${\mathcal{H}}_{2}:\equiv\\{\mbox{$\cal M$}_{Y_{i}},i=t+1,\cdots,m\\}$ be
subfamilies of ${\mathcal{H}}.$ Let $Y^{1}=\bigcup^{t}_{i=1}Y_{i}$ and let
$Y^{2}=\bigcup^{m}_{i=t+1}Y_{i}.$ Then ${\mathcal{H}}$ satisfies the rank
conditions of Definition 34 iff ${\mathcal{H}}_{1},{\mathcal{H}}_{2}$ satisfy
them and further
$r([\bigvee^{t}_{i=1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigwedge[\bigvee^{m}_{i=t+1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))=0$ and
$r([\bigvee^{t}_{i=1}\mbox{$\cal M$}^{*}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\bigwedge[\bigvee^{m}_{i=t+1}\mbox{$\cal
M$}^{*}_{Y_{i}}]\times(Y^{1}\cap Y^{2}))=0.$

###### Proof.

When $Y_{1}\cap Y_{2}=\emptyset,$ it is clear that if the rank condition is
satisfied for ${\mathcal{H}_{1}},{\mathcal{H}_{2}}$ the lemma is trivially
true. Let $Y_{1}\cap Y_{2}$ be nonvoid. By Theorem 47,
$r(\mbox{$\cal M$}_{A}\vee\mbox{$\cal M$}_{B})=r(\mbox{$\cal
M$}_{A})+r(\mbox{$\cal M$}_{B})-r([\mbox{$\cal M$}_{A}\times(A\cap
B)]\wedge[\mbox{$\cal M$}_{B}\times(A\cap B)].$ Therefore,
$r(\bigvee^{m}_{i=1}\mbox{$\cal M$}_{Y_{i}})=r(\bigvee^{t}_{i=1}\mbox{$\cal
M$}_{Y_{i}})+r(\bigvee^{m}_{i=t+1}\mbox{$\cal
M$}_{Y_{i}})-r([\bigvee^{t}_{i=1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\wedge[\bigvee^{m}_{i=t+1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})).$
It follows that $r(\bigvee^{m}_{i=1}\mbox{$\cal
M$}_{Y_{i}})=\Sigma^{m}_{i=1}r(\mbox{$\cal M$}_{Y_{i}})$ iff
$r(\bigvee^{t}_{i=1}\mbox{$\cal M$}_{Y_{i}})=\Sigma^{t}_{i=1}r(\mbox{$\cal
M$}_{Y_{i}}),t<m,$
$r(\bigvee^{m}_{i=t+1}\mbox{$\cal M$}_{Y_{i}})=\Sigma^{m}_{i=t+1}r(\mbox{$\cal
M$}_{Y_{i}})$ and $r([\bigvee^{t}_{i=1}\mbox{$\cal
M$}_{Y_{i}}]\times(Y^{1}\cap Y^{2})\wedge[\bigvee^{m}_{i=t+1}\mbox{$\cal
M$}_{Y_{i}}]\times(Y^{1}\cap Y^{2}))=0.$
Working with $\mbox{$\cal M$}^{*}_{Y_{i}}$ and repeating the argument, we get
the second half of the statement of the lemma. ∎

###### Proof.

(Proof of Theorem 65)
By Lemma 66, the primal rank condition of Definition 34
($r(\bigvee_{i}\mbox{$\cal M$}_{Y_{i}})=\Sigma_{i}r(\mbox{$\cal M$}_{Y_{i}})$)
holds for $\mathcal{H}$ iff it holds for
${\mathcal{H}_{1}},{\mathcal{H}_{2}},$ and $r([\bigvee^{t}_{i=1}\mbox{$\cal
M$}_{Y_{i}}]\times(Y^{1}\cap Y^{2})\wedge[\bigvee^{m}_{i=t+1}\mbox{$\cal
M$}_{Y_{i}}]\times(Y^{1}\cap Y^{2}))=0.$
We have $r([\bigvee^{t}_{i=1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2})\wedge[\bigvee^{m}_{i=t+1}\mbox{$\cal M$}_{Y_{i}}]\times(Y^{1}\cap
Y^{2}))$
$=r([\bigvee^{t}_{i=1}\mbox{$\cal M$}_{Y_{i}}]\times Y^{1}\times(Y^{1}\cap
Y^{2})\wedge[\bigvee^{m}_{i=t+1}\mbox{$\cal M$}_{Y_{i}}]\times
Y^{2}\times(Y^{1}\cap Y^{2})$
$=(\leftrightarrow(\mathcal{H}_{1}))\times(Y^{1}\cap
Y^{2})\wedge(\leftrightarrow(\mathcal{H}_{2}))\times(Y^{1}\cap Y^{2}).$ Thus
the primal rank condition holds for $\mathcal{H}$ iff it holds for
$\mathcal{H}_{1},\mathcal{H}_{2}$ and the zero intersection property holds for
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}.$

The dual rank condition for $\mathcal{H}$ is the same as the primal rank
condition for $\mathcal{H}^{*}.$ When $\mathcal{H}$ is associative, so is
$\mathcal{H}^{*}.$ Working with $\mathcal{H}^{*}$ we can show that the primal
rank condition holds for $\mathcal{H}^{*}$ iff it holds for
$\mathcal{H}^{*}_{1},\mathcal{H}^{*}_{2}$ and the zero intersection property
holds for
$\\{(\leftrightarrow(\mathcal{H}^{*}_{1})),(\leftrightarrow(\mathcal{H}^{*}_{2}))\\}.$
By Theorem 61,
$\\{(\leftrightarrow(\mathcal{H}^{*}_{1})),(\leftrightarrow(\mathcal{H}^{*}_{2}))\\}=\\{(\leftrightarrow(\mathcal{H}_{1}))^{*})),(\leftrightarrow(\mathcal{H}_{2}))^{*}))\\}.$
Now by by part 4 of Theorem 17, the zero intersection property holds for
$\\{(\leftrightarrow(\mathcal{H}_{1}))^{*})),(\leftrightarrow(\mathcal{H}_{2}))^{*}))\\}$
iff the full sum property holds for
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}.$
We thus see that the primal and dual rank conditions of rigidity hold for
$\mathcal{H}$ iff they hold for $\mathcal{H}_{1},\mathcal{H}_{2}$ and
$\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}$
is rigid. Thus $\mathcal{H}$ is rigid iff
$\mathcal{H}_{1},\mathcal{H}_{2},\\{(\leftrightarrow(\mathcal{H}_{1})),(\leftrightarrow(\mathcal{H}_{2}))\\}$
are rigid. ∎

The following is a more convenient version of Theorem 65.

######  Theorem 67.

Let ${\mathcal{H}}:\equiv\\{\mbox{$\cal M$}_{Y_{1}},\cdots,\mbox{$\cal
M$}_{Y_{m}}\\}$ be an associative family of matroids with ${\cal
G}_{\mathcal{H}}$ connected and with non empty edge set. Let ${\mathcal{H}}$
be partitioned as ${\mathcal{H}_{1}}\uplus\cdots\uplus{\mathcal{H}_{n}}.$ Then
${\mathcal{H}}$ is rigid iff ${\mathcal{H}_{1}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.

###### Proof.

1\. The proof is by induction over $n.$ We have seen in Theorem 65, that the
result is true when $n=2.$ We then have ${\mathcal{H}}$ is rigid iff
${\mathcal{H}_{1}},({\mathcal{H}_{2}}\uplus\cdots\uplus{\mathcal{H}_{n}}),\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow({\mathcal{H}_{2}}\uplus\cdots\uplus\mathcal{H}_{n})\\}$
are rigid.
By induction, ${\mathcal{H}_{2}}\uplus\cdots\uplus{\mathcal{H}_{n}}$ is rigid
iff ${\mathcal{H}_{2}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{2}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.
We therefore need only show that, rigidity of
$\\{\leftrightarrow(\mathcal{H}_{1}),\leftrightarrow({\mathcal{H}_{2}}\uplus\cdots\uplus\mathcal{H}_{n})\\}$
and
$\\{\leftrightarrow(\mathcal{H}_{2}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
implies rigidity of
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}.$

Let us denote
$\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n}),$
respectively by $\mbox{$\cal M$}_{Z_{1}},\cdots,\mbox{$\cal M$}_{Z_{m}}.$
Since $\mathcal{H}$ is an associative family, by the definition of
$\leftrightarrow(\mathcal{H}_{i}),$ it is clear that no element belongs to
more than two of the $Z_{i}.$ We thus need to show that rigidity of
$\\{\mbox{$\cal M$}_{Z_{1}},(\mbox{$\cal
M$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\cal M$}_{Z_{m}})\\}$
and $\\{\mbox{$\cal M$}_{Z_{2}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ implies the
rigidity of $\\{\mbox{$\cal M$}_{Z_{1}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}.$

Suppose $\\{\mbox{$\cal M$}_{Z_{1}},(\mbox{$\cal
M$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\cal M$}_{Z_{m}})\\}$
and $\\{\mbox{$\cal M$}_{Z_{2}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ are rigid.
Let $P$ be the set of all elements which belong precisely to one of
$Z_{2},\cdots,Z_{m}$ and let $T:\equiv Z_{1}\cap\bigcup_{i=2}^{m}Z_{i}.$ Since
no element belongs to more than two of $Z_{1},\cdots,Z_{m},$ it is clear that
$T\subseteq P.$ From the zero intersection property of $\\{\mbox{$\cal
M$}_{Z_{1}},(\mbox{$\cal
M$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\cal M$}_{Z_{m}})\\},$
we have that $r((\mbox{$\cal M$}_{Z_{1}}\times T)\wedge(\mbox{$\cal
M$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\cal M$}_{Z_{m}})\times
T)=r((\mbox{$\cal M$}_{Z_{1}}\times T)\wedge[(\mbox{$\cal
M$}_{Z_{2}}\vee\cdots\vee\mbox{$\cal M$}_{Z_{m}})\times P\times T])$
$=r((\mbox{$\cal M$}_{Z_{1}}\times T)\wedge[(\mbox{$\cal
M$}_{Z_{2}}\vee\cdots\vee\mbox{$\cal M$}_{Z_{m}})\times T])=0.$ By Theorem 5,
it follows that $r(\mbox{$\cal M$}_{Z_{1}}\vee\cdots\vee\mbox{$\cal
M$}_{Z_{m}})=r(\mbox{$\cal M$}_{Z_{1}})+r(\mbox{$\cal
M$}_{Z_{2}}\vee\cdots\vee\mbox{$\cal M$}_{Z_{m}}).$ Since $\\{\mbox{$\cal
M$}_{Z_{2}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ is rigid, we have
$r(\mbox{$\cal M$}_{Z_{2}}\vee\cdots\vee\mbox{$\cal M$}_{Z_{m}})=r(\mbox{$\cal
M$}_{Z_{1}})+r(\mbox{$\cal M$}_{Z_{2}})+\cdots+r(\mbox{$\cal M$}_{Z_{m}}).$
Therefore $r(\mbox{$\cal M$}_{Z_{1}}\vee\cdots\vee\mbox{$\cal
M$}_{Z_{m}})=r(\mbox{$\cal M$}_{Z_{1}})+\cdots+r(\mbox{$\cal M$}_{Z_{m}}).$

The proof of the dual rank condition for $\\{\mbox{$\cal
M$}_{Z_{1}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ is by replacing $\mbox{$\cal
M$}_{Z_{i}}$ by $\mbox{$\cal M$}_{Z_{i}}^{*}$ everywhere in the above proof
and by using the fact that rigidity of $\\{\mbox{$\cal
M$}_{Z_{2}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ is equivalent to rigidity of
$\\{\mbox{$\cal M$}^{*}_{Z_{2}},\cdots,\mbox{$\cal M$}^{*}_{Z_{m}}\\}.$
We thus see that rigidity of $\\{\mbox{$\cal M$}_{Z_{1}},(\mbox{$\cal
M$}_{Z_{2}}\leftrightarrow\cdots\leftrightarrow\mbox{$\cal M$}_{Z_{m}})\\}$
and $\\{\mbox{$\cal M$}_{Z_{2}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}$ implies the
rigidity of $\\{\mbox{$\cal M$}_{Z_{1}},\cdots,\mbox{$\cal M$}_{Z_{m}}\\}.$
This proves that ${\mathcal{H}}$ is rigid iff
${\mathcal{H}_{1}},\cdots,{\mathcal{H}_{n}}$ and
$\\{\leftrightarrow(\mathcal{H}_{1}),\cdots,\leftrightarrow(\mathcal{H}_{n})\\}$
are rigid.

∎

##  7 Connecting rigid multiports to obtain a rigid multiport

In this section we combine the results of Subsections 5.2 and 6.2 to give
simple rules for connecting rigid multiports to obtain a rigid multiport, when
the device characteristic has a special form. This form is sufficiently
general to capture commonly obtained device characteristics.

Suppose we have rigid multiports ${\cal N}_{WQ},{\cal N}_{TW}$ and we wish to
connect them at ports $W.$ How do we test for rigidity of the resulting
multiport ${\cal N}_{TQ}?$ How do we connect them so that the resulting
multiport is rigid?

The general answer is given in Theorems 21, 24 and 25.
As in Theorem 25, we could have rigid multiports ${\cal N}_{TW},{{\cal
N}}_{\tilde{W}Q}$ on graphs ${\cal G}_{RSW},{\cal G}_{\tilde{W}MQ}$
respectively and device characteristics ${\cal A}_{S^{\prime}S"},{{\cal
A}}_{M^{\prime}M"}$ respectively. The multiport ${\cal N}_{TQ}:\equiv{[{\cal
N}_{TW}\oplus{{\cal N}}_{\tilde{W}Q}]\cap{\cal A}^{W\tilde{W}}},$ obtained by
connecting ${\cal N}_{TW},{{\cal N}}_{\tilde{W}Q}$ through ${\cal
A}^{W\tilde{W}}$ is rigid, provided the pair
$\\{\mbox{$\mathcal{V}$}_{R^{\prime}W^{\prime}R"W"}\oplus\mbox{$\mathcal{V}$}_{\tilde{W}^{\prime}Q^{\prime}\tilde{W}"Q"},{\cal
A}^{W\tilde{W}}_{W^{\prime}W"\tilde{W}^{\prime}\tilde{W}"}\\},$ is rigid,
where
$\mbox{$\mathcal{V}$}_{R^{\prime}W^{\prime}R"W"}\oplus\mbox{$\mathcal{V}$}_{\tilde{W}^{\prime}Q^{\prime}\tilde{W}"Q"}$
are the vector space translates of port behaviours of ${\cal N}_{TW},{{\cal
N}}_{\tilde{W}Q}$ respectively. This test requires solution of linear
equations whose nature is very general. Fortunately, in some important special
cases, the test only involves working with simple matroids and is therefore
very efficient.

###  7.1 Sufficiency of matroidal tests for rigidity of multiports

We simplify the problem of testing for rigidity of multiports by making an
assumption that is justified in practice. We assume that the parameters
associated with the various devices, such as resistance in the case of
resistors, gain, transresistance, transconductance in the case of controlled
sources, are not known exactly but may be treated as being picked at random
from an interval of positive width $\epsilon,$ about some real value. This
width may be as small as we please, as long as it is nonzero. This is a way of
saying that parameters are not known exactly. Under this condition, we may
treat the parameters to be algebraically independent over ${\mathbb{Q}}.$ We
remind the reader that elements $x_{i}\in\Re,i=1,\cdots,k$ are algebraically
independent over $\mathbb{Q}$ iff every nontrivial multivariable polynomial in
$x_{i}$ with coefficients from $\mathbb{Q}$ takes nonzero value. Essentially,
once this assumption is made, we have to test for rigidity of a pair
$\\{\mbox{$\mathcal{V}$}_{AB},\mbox{$\mathcal{V}$}_{B}\\},$ which has the
property that $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}+\mbox{$\mathcal{V}$}_{B})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB})\vee\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{B})$
and $\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB}+\mbox{$\mathcal{V}$}^{\perp}_{B})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{\perp}_{B}).$ So, by Theorem 56, the problem reduces
to testing the rigidity of the pair $\\{\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AB}),\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{B})\\}$
which turns out to be simple because both the matroids are simple, the matroid
$\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{B}),$ being particularly so.

In order to deal with connection of multiports in a simple way, we use ideas
from topological multiport decomposition [16, 19], which we describe below.

Let ${\cal G}_{S_{1}S_{2}}$ be a graph. Then it is always possible to
construct graphs ${\cal G}_{S_{1}W},{\cal G}_{S_{2}\tilde{W}},{\cal
G}_{W\tilde{W}},$ where $W,\tilde{W}$ are additional sets of edges which are
disjoint from each other as well as disjoint from $S_{1},S_{2},$ such that
$\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{1}S_{2}})=(\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{1}W})\oplus\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{2}\tilde{W}}))\leftrightarrow\mbox{$\mathcal{V}$}^{v}({\cal
G}_{W\tilde{W}})$ and $\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{1}S_{2}})=(\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{1}W})\oplus\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{2}\tilde{W}}))\leftrightarrow\mbox{$\mathcal{V}$}^{i}({\cal
G}_{W\tilde{W}}).$
We can always choose $W,\tilde{W}$ to have size
$|W|=|\tilde{W}|=\xi(S_{1},S_{2}):\equiv r({\cal G}_{S_{1}S_{2}}\circ
S_{1})-r({\cal G}_{S_{1}S_{2}}\times S_{1})$
$=r({\cal G}_{S_{1}S_{2}}\circ S_{2})-r({\cal G}_{S_{1}S_{2}}\times S_{2}).$
If ${\cal G}_{S_{1}S_{2}}\circ S_{1},{\cal G}_{S_{1}S_{2}}\circ S_{2}$ are
connected, these graphs would have common vertices whose number would be equal
to $\xi(S_{1},S_{2})+1.$ In this case ${\cal G}_{S_{1}W},{\cal G}_{S_{2}W}$
can be built as given below.

Let $v_{1},\cdots,v_{k},$ be the common vertices between the above mentioned
subgraphs of ${\cal G}_{S_{1}S_{2}}.$ Let $e_{1},\cdots,e_{k-1},$ be edges
distinct from those in $S_{1}\uplus S_{2}$ with $e_{i}$ having end points
$v_{i},v_{k}$ for $i=1,\cdots,k-1.$ We will call $v_{k}$ as the datum node and
we will say ${\cal G}_{S_{1}W},{\cal G}_{S_{2}W}$ have node to datum type of
ports. In this case, ${\cal G}_{S_{1}S_{2}}$ is obtained from ${\cal
G}_{S_{1}S_{2}}\circ S_{1}$ and ${\cal G}_{S_{1}S_{2}}\circ S_{2}$ by
identifying the nodes $v_{1},\cdots,v_{k},$ in the two graphs and, further, it
turns out that $\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{1}S_{2}})=(\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{1}W})\leftrightarrow\mbox{$\mathcal{V}$}^{v}({\cal G}_{S_{2}{W}}))$ and
$\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{1}S_{2}})=(\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{1}W})\rightleftharpoons\mbox{$\mathcal{V}$}^{i}({\cal G}_{S_{2}{W}})).$
It may be noted that, in practice, this is the way larger networks are built
from smaller modules.

Let us suppose we have built rigid multiports ${\cal N}_{TW},{\cal N}_{WQ}$ on
graphs ${\cal G}_{S_{1}W},{\cal G}_{S_{2}W}$ respectively, where
$S_{1}\supseteq T,S_{2}\supseteq Q.$ Further let ${\cal G}_{S_{1}W}\circ
S_{1},{\cal G}_{S_{2}W}\circ S_{2}$ be connected and let ${\cal
G}_{S_{1}W},{\cal G}_{S_{2}W}$ have node to datum type of ports. Let the
device characteristics for both multiports be composed in terms of resistors,
voltage sources, current sources and controlled sources (CCVS,VCCS,CCCS,VCVS).
Note that the first two letters in the acronym refer to ‘current controlled’
or ‘voltage controlled’ and the last two, to ‘current source’ or ‘voltage
source’. The combined device characteristic is given below.

$\displaystyle\begin{pmatrix}I_{\tilde{Y}_{1}^{\prime}}&0_{\tilde{Z}_{1}^{\prime}}&0_{\tilde{Y}_{1}"}&0_{\tilde{Z}_{1}"}\\\
0_{\tilde{Y}_{1}^{\prime}}&I_{\tilde{Z}_{1}^{\prime}}&-r_{\tilde{Z}_{1}^{\prime}\tilde{Y}_{1}"}&0_{\tilde{Z}_{1}"}\end{pmatrix}\begin{pmatrix}v_{\tilde{Y}_{1}^{\prime}}\\\
v_{\tilde{Z}_{1}^{\prime}}\\\ i_{\tilde{Y}_{1}"}\\\
i_{\tilde{Z}_{1}"}\end{pmatrix}=\begin{pmatrix}0\\\
0\end{pmatrix};\begin{pmatrix}0_{\tilde{Y}_{2}^{\prime}}&0_{\tilde{Z}_{2}^{\prime}}&I_{\tilde{Y}_{2}"}&0_{\tilde{Z}_{2}"}\\\
-g_{\tilde{Z}_{2}"\tilde{Y}_{2}^{\prime}}&0_{\tilde{Z}_{2}^{\prime}}&0_{\tilde{Y}_{2}"}&I_{\tilde{Z}_{2}"}\end{pmatrix}\begin{pmatrix}v_{\tilde{Y}_{2}^{\prime}}\\\
v_{\tilde{Z}_{2}^{\prime}}\\\ i_{\tilde{Y}_{2}"}\\\
i_{\tilde{Z}_{2}"}\end{pmatrix}=\begin{pmatrix}0\\\ 0\end{pmatrix}$ (4)

$\displaystyle\begin{pmatrix}I_{\hat{Y}_{1}^{\prime}}&0_{\hat{Z}_{2}^{\prime}}&0_{\hat{Y}_{1}"}&0_{\hat{Z}_{2}"}\\\
0_{\hat{Y}_{1}^{\prime}}&0_{\hat{Z}_{2}^{\prime}}&-\alpha_{\hat{Z}_{2}"\hat{Y}_{1}"}&I_{\hat{Z}_{2}"}\end{pmatrix}\begin{pmatrix}v_{\hat{Y}_{1}^{\prime}}\\\
v_{\hat{Z}_{2}^{\prime}}\\\ i_{\hat{Y}_{1}"}\\\
i_{\hat{Z}_{2}"}\end{pmatrix}=\begin{pmatrix}0\\\
0\end{pmatrix};\begin{pmatrix}0_{\hat{Y}_{2}^{\prime}}&0_{\hat{Z}_{1}^{\prime}}&I_{\hat{Y}_{2}"}&0_{\hat{Z}_{1}"}\\\
-\beta_{\hat{Z}_{1}^{\prime}\hat{Y}_{2}^{\prime}}&I_{\hat{Z}_{1}^{\prime}}&0_{\hat{Y}_{2}"}&0_{\hat{Z}_{1}"}\end{pmatrix}\begin{pmatrix}v_{\hat{Y}_{2}^{\prime}}\\\
v_{\hat{Z}_{1}^{\prime}}\\\ i_{\hat{Y}_{2}"}\\\
i_{\hat{Z}_{1}"}\end{pmatrix}=\begin{pmatrix}0\\\ 0\end{pmatrix}$ (5)
$\displaystyle\begin{pmatrix}I&-\hat{R}\end{pmatrix}\begin{pmatrix}v_{R^{\prime}}\\\
i_{R"}\end{pmatrix}=0;\begin{pmatrix}I_{E^{\prime}}&0_{E"}\end{pmatrix}\begin{pmatrix}v_{E^{\prime}}\\\
i_{E"}\end{pmatrix}=s_{E};\begin{pmatrix}0_{J^{\prime}}&I_{J"}\end{pmatrix}\begin{pmatrix}v_{J^{\prime}}\\\
i_{J"}\end{pmatrix}=s_{J}.$ (6)

The matrices
$r_{\tilde{Z}_{1}^{\prime}\tilde{Y}_{1}"},g_{\tilde{Z}_{2}"\tilde{Y}_{2}^{\prime}},\alpha_{\hat{Z}_{2}"\hat{Y}_{1}"},\beta_{\hat{Z}_{1}^{\prime}\hat{Y}_{2}^{\prime}},\hat{R}$
are diagonal matrices and their diagonal entries are together assumed to be
algebraically independent over ${\mathbb{Q}}.$ It is clear that a device
characteristic composed entirely of the above mentioned devices is a proper
affine space. A multiport composed only of these devices is proper, by
definition, iff it is rigid.

If we connect ${\cal N}_{TW},{\cal N}_{WQ}$ at ports $W$ will we obtain a
rigid multiport ${\cal N}_{TQ}?$
To answer this question, we need to examine whether the pair
$\\{\mbox{$\mathcal{V}$}_{AX},\mbox{$\mathcal{V}$}_{X}\\}$ is rigid, where
$\mbox{$\mathcal{V}$}_{X}$ is the vector space translate of the device
characteristic composed of the devices described in Equations 4, 5, 6 and
$\mbox{$\mathcal{V}$}_{AX}:\equiv(\mbox{$\mathcal{V}$}^{v}({\cal
G}_{S_{1}S_{2}}))_{S_{1}^{\prime}S_{2}^{\prime}}\oplus(\mbox{$\mathcal{V}$}^{i}({\cal
G}_{S_{1}S_{2}}))_{S_{1}"S_{2}"}.$ Because of the algebraic independence of
the above mentioned parameters, and the structure of the device
characteristic, under certain additional topological conditions, this problem
reduces to checking whether the pair $\\{\mbox{$\cal M$}_{AX},\mbox{$\cal
M$}_{X}\\},$ is rigid, where $\mbox{$\cal M$}_{AX}:\equiv\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}_{AX}),$
$\mbox{$\cal M$}_{X}:\equiv\mbox{$\cal M$}(\mbox{$\mathcal{V}$}_{X})$ (Theorem
72 in the Appendix). This checking is done by applying the matroid union
algorithm [3, 31, 19].

In this section we give a simpler result, which gives sufficient conditions
for the multiport ${\cal N}_{P}:\equiv{\cal N}_{TQ}$ to be rigid. This result
is easy to state, and additionally the sufficient conditions given are easy to
test and practically speaking, invariably satisfied. Essentially, we only need
to check if the voltage source like branches (controlled voltage source
branches $Z_{1}$ together with the (voltage zero) controlling current branches
$Y_{1}$ and the voltage source branches $E$) do not form a loop and the
current source like branches (controlled current source branches $Z_{2}$
together with the (current zero) controlling voltage branches $Y_{2}$ and the
current source branches $J$) do not form a cutset in the graph ${\cal
G}_{S_{1}S_{2}}.$ Additionally, when these conditions are satisfied, the
result states that the multiport behaviour has a hybrid representation, i.e.,
a representation of the form

$\displaystyle\begin{pmatrix}i_{P_{1}"}\\\
v_{(P-P_{1})^{\prime}}\end{pmatrix}=\begin{pmatrix}g_{11}&h_{12}\\\
h_{21}&r_{22}\end{pmatrix}\begin{pmatrix}v_{P_{1}^{\prime}}\\\
i_{(P-P_{1})"}\end{pmatrix}+\begin{pmatrix}s_{P_{1}"}\\\
s_{(P-P_{1})^{\prime}}\end{pmatrix},$

and the corresponding column base is easy to compute directly from the graph
${\cal G}_{S_{1}S_{2}}.$ This makes the computation of the multiport behaviour
easier than when the column base is not available.

The proof is given in B.

######  Theorem 68.

Let ${\cal N}_{P}$ be a multiport on graph ${\cal G}_{SP}$ whose device
characteristic ${\cal A}_{S^{\prime}S"}$ is composed entirely of voltage
sources, current sources, CCVS,VCCS,CCCS,VCVS and resistors as in Equations 4,
5, 6. Let
$Y_{1}:\equiv\tilde{Y}_{1}\uplus\hat{Y}_{1},Y_{2}:\equiv\tilde{Y}_{2}\uplus\hat{Y}_{2},Z_{1}:\equiv\tilde{Z}_{1}\uplus\hat{Z}_{1},Z_{2}:\equiv\tilde{Z}_{2}\uplus\hat{Z}_{2}.$

Let the values of resistors and the controlled source parameters be
algebraically independent over ${\mathbb{Q}}.$ We then have the following.

  1. 1.

${\cal N}_{P}$ is a proper multiport only if

    1. (a)

the controlling current branches $Y_{1}$ together with the voltage source
branches $E$ do not contain a loop of ${\cal G}_{SP}$ and

    2. (b)

the controlling voltage branches $Y_{2}$ together with the current source
branches $J$ do not contain a cutset of ${\cal G}_{SP}.$

  2. 2.

${\cal N}_{P}$ is a proper multiport if

    1. (a)

the set of controlled voltage source branches $Z_{1}$ together with the
controlling current branches $Y_{1}$ and the voltage source branches $E$ do
not contain a loop of ${\cal G}_{SP}$

    2. (b)

the set of controlled current source branches $Z_{2}$ together with the
controlling voltage branches $Y_{2}$ and the current source branches $J$ do
not contain a cutset of ${\cal G}_{SP}.$

  3. 3.

Let the above conditions of 2 be satisfied. Then there exists a tree $t$ of
${\cal G}_{SP}$ that contains $Z_{1}\uplus Y_{1}\uplus E$ and does not
intersect $Z_{2}\uplus Y_{2}\uplus J.$ For such a tree, the port behaviour of
multiport ${\cal N}_{P}$ has a hybrid representation with $(t\cap
P)^{\prime}\uplus(P-t)"$ as a column base for the vector space translate of
the behaviour.

######  Remark 9.

The sufficient conditions of Theorem 68 are not necessary. Let ${\cal G}$ be a
graph on two edges $e_{1},e_{2},$ where the edges are in parallel. Let these
be the device ports of a current controlled voltage source. Then
$Y_{1}:\equiv\\{e_{1}\\},Z_{1}:\equiv\\{e_{2}\\}$ and $Y_{1}\uplus Z_{1}$
contains a loop. Let $r_{e_{1}"e_{2}^{\prime}}\neq 0.$ This network has the
unique solution $0_{e_{1}^{\prime}e_{2}^{\prime}e_{1}"e_{2}"}.$

From a practical point of view the sufficient conditions are reasonable since,
while designing a circuit, one will never force a dependency on controlled
voltages by making them form a loop with predetermined voltages or on
controlled current sources by making them form a cutset with predetermined
currents.

###  7.2 Algorithm for constructing hybrid representation of the port
behaviour

We present below an algorithm for construction of the hybrid representation of
the port behaviour of a multiport satisfying the sufficiency conditions in
Theorem 68.

We remind the reader that hybrid representation for a port behaviour
${\mbox{$\mathcal{V}$}}_{P^{\prime}P"}$ is a representative matrix of the form

$\displaystyle(F_{P_{1}^{\prime}}|F_{P_{2}^{\prime}}|F_{P_{1}"}|F_{P_{2}"})=\begin{pmatrix}I&h_{21}^{T}&g_{11}^{T}&0\\\
0&r_{22}^{T}&h_{12}^{T}&I\end{pmatrix}$ (7)

Suppose ${{\cal
A}}_{P^{\prime}P"}=(\alpha_{P^{\prime}},\beta_{P"})+{\mbox{$\mathcal{V}$}}_{P^{\prime}P"}.$
Then we can write ${{\cal A}}_{P^{\prime}P"}$ as the solution space of the
equations

$\displaystyle\begin{pmatrix}i_{P_{1}"}\\\
v_{P_{2}^{\prime}}\end{pmatrix}=\begin{pmatrix}g_{11}&h_{12}\\\
h_{21}&r_{22}\end{pmatrix}\begin{pmatrix}v_{P_{1}^{\prime}}\\\
i_{P_{2}"}\end{pmatrix}+\begin{pmatrix}s_{P_{1}"}\\\
s_{P_{2}^{\prime}}\end{pmatrix},$ (8)

where

$\displaystyle\begin{pmatrix}s_{P_{1}"}\\\
s_{P_{2}^{\prime}}\end{pmatrix}=-\begin{pmatrix}g_{11}&h_{12}\\\
h_{21}&r_{22}\end{pmatrix}\begin{pmatrix}\alpha_{P_{1}^{\prime}}\\\
\beta_{P_{2}"}\end{pmatrix}+\begin{pmatrix}\beta_{P_{1}"}\\\
\alpha_{P_{2}^{\prime}}\end{pmatrix},$ (9)

###### Algorithm I

Input: A multiport ${\cal N}_{P}:\equiv({\cal G}_{SP},{\cal
A}_{S^{\prime}S"}),$ where ${\cal A}_{S^{\prime}S"}$ is composed entirely of
voltage sources, current sources, CCVS,VCCS,CCCS,VCVS and resistors and
satisfies sufficiency conditions of
Theorem 68.
Output: A hybrid representation for the port behaviour ${{\cal
A}}_{P^{\prime}P"}$ of ${\cal N}_{P}.$
Step 1. Construct a forest $t$ of ${\cal G}_{SP}$ that contains $Z_{1}\uplus
Y_{1}\uplus E$ and does not intersect
$Z_{2}\uplus Y_{2}\uplus J.$
Step 2. Let $P_{1}:\equiv t\cap P,P_{2}:\equiv P-t.$ The set of columns
$P_{1}^{\prime}\uplus P_{2}"$ is a column base of
${\mbox{$\mathcal{V}$}}_{P^{\prime}P"}.$
Step 3. Set all internal sources to zero (i.e., the device characteristic is
the
vector space associate of the original device characteristic).
For each element $e_{m}\in P_{1},$ in turn, set
$v_{e_{m}^{\prime}}=1,v_{e_{j}^{\prime}}=0,e_{j}\in P_{1},j\neq
m,i_{P_{2}"}=0_{P_{2}"}$ and
for each $e_{r}\in P_{2}$ in turn, set $i_{e_{r}"}=1,i_{e_{j}"}=0,e_{j}\in
P_{2},j\neq r,v_{P_{1}^{\prime}}=0_{P_{1}^{\prime}}$ and compute
the corresponding vector $\begin{pmatrix}i_{P_{1}"}\\\
v_{P_{2}^{\prime}}\end{pmatrix}.$ These yield the $m^{th}$ and
$(|P_{1}|+r)^{th}$ columns respectively
of the matrix $\begin{pmatrix}g_{11}&h_{12}\\\ h_{21}&r_{22}\end{pmatrix}.$
Step 4. Keep the internal sources active (i.e., the device characteristic
remains the original device characteristic of the multiport), set
$v_{P_{1}^{\prime}}=0_{P_{1}^{\prime}},i_{P_{2}"}=0_{P_{2}"}$ and
solve the multiport to compute the corresponding vector
$\begin{pmatrix}i_{P_{1}"}\\\ v_{P_{2}^{\prime}}\end{pmatrix}.$ This yields
$\begin{pmatrix}s_{P_{1}"}\\\ s_{P_{2}^{\prime}}\end{pmatrix}.$
STOP

Algorithm I is justified by part 3 of Theorem 68: if $t$ is a forest of ${\cal
G}_{SP}$ that contains $Z_{1}\uplus Y_{1}\uplus E$ and does not intersect
$Z_{2}\uplus Y_{2}\uplus J,$ and $\bar{t}:\equiv S\uplus P-t,$ then
$t^{\prime}\uplus\bar{t}"$ is a column base of
$\hat{\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}$
$:\equiv(\mbox{$\mathcal{V}$}^{v}({\cal
G}_{SP}))_{S^{\prime}P^{\prime}}\oplus(\mbox{$\mathcal{V}$}^{i}({\cal
G}_{SP}))_{S"P"},$ such that $(t^{\prime}\uplus\bar{t}")\cap(P^{\prime}\uplus
P")=P_{1}^{\prime}\uplus P_{2}"$ is a column base of
$\hat{\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\leftrightarrow\mbox{$\mathcal{V}$}_{S^{\prime}S"}.$

###  7.3 Generalized multiports based on Dirac structures

In this subsection we examine the case where the device characteristic
contains gyrators and ideal transformers. There are three ways in which we can
approach this problem. First, we could model these devices in terms of
controlled sources. If we take the parameters of these controlled sources to
be algebraically indepedent over ${\mathbb{Q}},$ Theorem 68 would be
applicable. But this would only be an approximate model of gyrators and ideal
transformers. Since the approximation can be made arbitrarily accurate, this
may be adequate for practical purposes. A second approach would be to take the
parameters of the gyrators and ideal transformers to be algebraically
independent over ${\mathbb{Q}}.$ This problem has been tackled with some
success in the case of electrical networks with no ports (see [31] for a
detailed discussion). However, the algorithm for testing whether the network
has a unique solution in this case is very cumbersome in comparison with the
case where we have only resistors and controlled and independent sources.
Further, there are important situations where the gyrators and transformers
are used to impose constraints analogous to topological ones. Here the
assumption of algebraic independence is no longer valid. We use below an
approach with uses conventional circuit simulators for computing the port
behaviour. In brief, we proceed as follows. Let $\hat{{\cal
N}}_{P}:\equiv({\cal G}_{\hat{S}P},{\cal D}_{S_{1}^{\prime}S_{1}"}\oplus{\cal
A}_{S^{\prime}S"}),$ where $\hat{S}=S_{1}\uplus S,$ ${\cal
D}_{S_{1}^{\prime}S_{1}"}$ is a Dirac structure (i.e., satisfies $({\cal
D}_{S_{1}^{\prime}S_{1}"})_{S_{1}"S_{1}^{\prime}}={\cal
D}_{S_{1}^{\prime}S_{1}"}^{\perp}$) and ${\cal A}_{S^{\prime}S"}$ is composed
of resistors, independent and controlled sources as in Theorem 68. By Theorem
25, we know that $\hat{{\cal N}}_{P}$ is rigid iff the multiport ${{\cal
N}}_{P}:\equiv({\cal G}_{\hat{S}P},{\cal D}_{S_{1}^{\prime}S_{1}"})$ and the
generalized multiport ${\cal
N}^{g}_{P}:\equiv({\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},{\cal
A}_{S^{\prime}S"})$ are rigid, where
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}:\equiv[(\mbox{$\mathcal{V}$}^{v}({\cal
G}_{\hat{S}P}))_{\hat{S}^{\prime}P^{\prime}},(\mbox{$\mathcal{V}$}^{i}({\cal
G}_{\hat{S}P}))_{\hat{S}"P"}]\leftrightarrow{\cal D}_{S_{1}^{\prime}S_{1}"}$
is a Dirac structure (Corollary 12). We test for rigidity of ${{\cal N}}_{P}$
using a conventional simulator to compute its port behaviour
${\mbox{$\mathcal{V}$}}^{1}_{S_{1}^{\prime}P^{\prime}S_{1}"P"}.$ The following
theorem states, analogous to Theorem 68, that if certain columns of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}$ can be included in
column bases and cobases of appropriate minors of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},$ then the generalized
multiport ${\cal
N}^{g}_{P}:\equiv({\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},{\cal
A}_{S^{\prime}S"})$ is rigid.

######  Theorem 69.

Let ${\cal
N}^{g}_{P}:\equiv({\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},{\cal
A}_{S^{\prime}S"}),$ be a generalized multiport whose device characteristic
${\cal A}_{S^{\prime}S"}$ is composed entirely of voltage sources, current
sources, CCVS,VCCS,CCCS,VCVS and resistors as in Equations 4, 5, 6. Let
$Y_{1}:\equiv\tilde{Y}_{1}\uplus\hat{Y}_{1},Y_{2}:\equiv\tilde{Y}_{2}\uplus\hat{Y}_{2},Z_{1}:\equiv\tilde{Z}_{1}\uplus\hat{Z}_{1},Z_{2}:\equiv\tilde{Z}_{2}\uplus\hat{Z}_{2}.$

Let the values of resistors and controlled source parameters be algebraically
independent over ${\mathbb{Q}}.$ Further, let
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}$ be Dirac.

1\. Necessity for multiport being rigid Let
$\mbox{$\mathcal{V}$}_{S^{\prime}S"}$ be the vector space translate of ${\cal
A}_{S^{\prime}S"}.$ Then $\mbox{$\mathcal{V}$}_{S^{\prime}S"}$ has full sum
property with ${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\circ
S^{\prime}S"$ and zero intersection property with
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\times S^{\prime}S",$
only if the sets of columns $Y^{\prime}_{1}\uplus E^{\prime},Y"_{2}\uplus J",$
of ${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},$ are independent.

2\. Sufficiency for multiport being rigid The generalized multiport ${\cal
N}^{g}_{P}$ is rigid
a) if the set of columns $Z^{\prime}_{1}\uplus Y^{\prime}_{1}\uplus
E^{\prime},$ can be included in a column base of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\circ
S^{\prime}P^{\prime}$ and the set of columns $Z^{\prime}_{2}\uplus
Y^{\prime}_{2}\uplus J"$ can be included in a column cobase of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\circ
S^{\prime}P^{\prime},$ i.e., $Z"_{2}\uplus Y"_{2}\uplus J"$ is an independent
set of columns of ${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\times
S"P".$

$or$

b) if the set of columns $Z"_{2}\uplus Y"_{2}\uplus J",$ can be included in a
column base of ${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\circ
S"P"$ and the set of columns $Z"_{1}\uplus Y"_{1}\uplus E"$ can be included in
a column cobase of ${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\circ
S"P",$ i.e., $Z^{\prime}_{1}\uplus Y^{\prime}_{1}\uplus E^{\prime}$ is an
independent set of columns of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"}\times
S^{\prime}P^{\prime}.$

3\. Existence of hybrid representation Let the above conditions of 2(a) or
2(b) be satisfied. Then there exists a column base $b_{1}$ of
${\mbox{$\mathcal{V}$}}^{1}_{S^{\prime}P^{\prime}S"P"},$ that contains
$Z^{\prime}_{1}\uplus Y^{\prime}_{1}\uplus E^{\prime}\uplus Z"_{2}\uplus
Y"_{2}\uplus J".$ For such a column base, the port behaviour of ${\cal
N}^{g}_{P}$ has a hybrid representation with $(b_{1}\cap
P^{\prime})\uplus(b_{1}\cap P")$ as a column base for the vector space
translate of the behaviour.

######  Remark 10.

We note that Theorem 69 requires testing of independence of certain columns of
the port behaviour of ${\cal N}_{SP}:\equiv({\cal
G}_{S_{1}SP},D_{S_{1}^{\prime}S_{1}"})$ Usually the size of $S\uplus P$ would
be much greater than that of $S_{1}.$ Computing the port behaviour of ${\cal
N}_{SP}$ directly would be expensive. However, the ports $S\uplus P$ would
have redundancies in ${\cal N}_{SP}.$ We show in D, that in such cases we can
compute the port behaviour of a multiport in which the ports are minimized and
the independence can be reduced to testing that of a reduced set of columns in
the minimized port behaviour. Further, it is shown there that the minimized
number of ports is not greater than $|S_{1}|.$

##  8 Conclusions and future work

We have introduced the notion of rigidity for linear multiports as the
counterpart of uniqueness of solution for linear networks and shown its
utility in understanding the behaviour of linear networks composed of
multiports.

We have shown that there is an analogous notion of rigidity for pairs of
matroids and that its properties mimic those for multiports. We have exploited
this analogy for giving simple and very efficient topological tests for
rigidity of electrical multiports composed of nonzero resistors, independent
and controlled voltage and independent and controlled current sources assuming
that the parameters of the devices are algebraically independent over
${\mathbb{Q}}.$

We mention below a few lines of future research.

Gyrators and ideal transformers are important electrical components and also
means of imposing conditions similar to topological ones. In this paper, we
have handled the case where the algebraic independence condition is not valid.
If one assumes algebraic independence over ${\mathbb{Q}}$ for their
parameters, one can develop purely matroidal tests for rigidity of multiports
containing them, analogous to the theory for uniqueness of solution of
networks containing them [31, 12].

Orthogonality is an important property in computational linear algebra.
Rigidity is a weaker form of complementary orthogonality (Subsection 5.3). It
is the best that can be asked for, when the two spaces model different
physical entities (such as topological and device characteristic). Similarly
for matroids, rigidity can be regarded as a weaker form of duality (Subsection
6.4). It may be interesting to explore this aspect of rigidity.

Both matched composition and the implicit duality theorem (Theorems 11, 50)
hold for polymatroid rank functions [33]. It appears worthwhile to explore the
relevance of the notion of rigidity for such functions.

##  Appendix A Rigidity of matroid pairs: proofs

###### Proof.

(Proof of Lemma 54)

1\. We have $r(\mbox{$\cal M$}^{1}_{B})+r(\mbox{$\cal
M$}^{2}_{B})=r(\mbox{$\cal M$}^{1}_{B}\vee\mbox{$\cal
M$}^{2}_{B})+r(\mbox{$\cal M$}^{1}_{B}\wedge\mbox{$\cal M$}^{2}_{B}),$ so that
$|B|=r(\mbox{$\cal M$}^{1}_{B})+r(\mbox{$\cal M$}^{2}_{B})=r(\mbox{$\cal
M$}^{1}_{B}\vee\mbox{$\cal M$}^{2}_{B})$ iff $r(\mbox{$\cal
M$}^{1}_{B}\wedge\mbox{$\cal M$}^{2}_{B})=0.$

2\. By Theorem 48, we have
$r(\mbox{$\cal M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC})=r(\mbox{$\cal
M$}_{AB}\times A)+r(\mbox{$\cal M$}_{BC}\times C)+r(\mbox{$\cal M$}_{AB}\circ
B\wedge\mbox{$\cal M$}_{BC}\circ B)-r(\mbox{$\cal M$}_{AB}\times
B\wedge\mbox{$\cal M$}_{BC}\times B).$
Now $r(\mbox{$\cal M$}_{AB}\circ B\wedge\mbox{$\cal M$}_{BC}\circ
B)=r(\mbox{$\cal M$}_{AB}\circ B)+r(\mbox{$\cal M$}_{BC}\circ B)-r(\mbox{$\cal
M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B).$
Therefore, using Theorems 47,43, we have $r(\mbox{$\cal
M$}_{AB}\leftrightarrow\mbox{$\cal M$}_{BC})$
$=r(\mbox{$\cal M$}_{AB}\times A)+r(\mbox{$\cal M$}_{BC}\times
C)+r(\mbox{$\cal M$}_{AB}\circ B)+r(\mbox{$\cal M$}_{BC}\circ B)-r(\mbox{$\cal
M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B)-r(\mbox{$\cal M$}_{AB}\times
B\wedge\mbox{$\cal M$}_{BC}\times B)$
$=r(\mbox{$\cal M$}_{AB})+r(\mbox{$\cal M$}_{BC})-r(\mbox{$\cal M$}_{AB}\circ
B\vee\mbox{$\cal M$}_{BC}\circ B)-r(\mbox{$\cal M$}_{AB}\times
B\wedge\mbox{$\cal M$}_{BC}\times B).$ Therefore,
we have $r(\mbox{$\cal M$}_{AB}\leftrightarrow\mbox{$\cal
M$}_{BC})=r(\mbox{$\cal M$}_{AB})+r(\mbox{$\cal M$}_{BC})-|B|,$ if
$\mbox{$\cal M$}_{AB}\circ B\vee\mbox{$\cal M$}_{BC}\circ B=\mbox{$\cal
F$}_{B}$ and
$\mbox{$\cal M$}_{AB}\times B\wedge\mbox{$\cal M$}_{BC}\times
B={\mathbf{0}}_{B},$ i.e., if $(\mbox{$\cal M$}_{AB},\mbox{$\cal M$}_{BC})$ is
rigid.

∎

We need the following lemma for the proof of the result on rigidity of pairs
of matroids which are derived through the ‘$\leftrightarrow$’ operation from a
rigid pair of matroids.

######  Lemma 70.

  1. 1.

$[\mbox{$\cal M$}_{WTV}\circ TV\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal
M$}_{V})]\circ V=\mbox{$\cal M$}_{WTV}\circ V\vee\mbox{$\cal M$}_{V};$

  2. 2.

$[\mbox{$\cal M$}_{WTV}\circ TV\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal
M$}_{V})]\times T=[(\mbox{$\cal M$}_{WTV}\circ TV\vee\mbox{$\cal
M$}_{V})\times T]\vee\mbox{$\cal M$}_{T};$

  3. 3.

$\mbox{$\cal M$}_{WTV}\circ TV\leftrightarrow\mbox{$\cal M$}_{V}=(\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V})\circ T.$

###### Proof.

Let us denote $(\mbox{$\cal M$}_{WTV}\circ TV\vee\mbox{$\cal M$}_{V})$ by
$\hat{\mbox{$\cal M$}}_{TV}.$

1\. We need to show $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal M$}_{T})\circ
V=(\mbox{$\cal M$}_{WTV}\circ V\vee\mbox{$\cal M$}_{V}).$
We have $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal M$}_{T})\circ
V=\hat{\mbox{$\cal M$}}_{TV}\circ V\vee(({\mathbf{0}}_{V}\oplus\mbox{$\cal
M$}_{T})\circ V)=\hat{\mbox{$\cal M$}}_{TV}\circ V=(\mbox{$\cal M$}_{WTV}\circ
TV\circ V\vee\mbox{$\cal M$}_{V})=(\mbox{$\cal M$}_{WTV}\circ V\vee\mbox{$\cal
M$}_{V}).$

2\. We need to show that $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal
M$}_{T})\times T=(\hat{\mbox{$\cal M$}}_{TV}\times T)\vee\mbox{$\cal M$}_{T}.$

Let $\hat{b}_{T}$ be a base of $(\hat{\mbox{$\cal M$}}_{TV}\times
T)\vee\mbox{$\cal M$}_{T}.$ Then there exist bases $b^{1}_{TV},b^{2}_{T}$ of
$\hat{\mbox{$\cal M$}}_{TV},\mbox{$\cal M$}_{T},$ respectively such that
$\hat{b}_{T}=(b^{1}_{TV}\cap T)\cup b^{2}_{T}$ and $b^{1}_{TV}\cap V$ is a
base of $\hat{\mbox{$\cal M$}}_{TV}\circ V,$ i.e., $(b^{1}_{TV}\cup
b^{2}_{T})\cap V$ is a base of $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal
M$}_{T})\circ V.$ It follows that $(b^{1}_{TV}\cup b^{2}_{T})\cap
T=\hat{b}_{T}$ is independent in $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal
M$}_{T})\times T.$

Let $\hat{b}_{T}$ be a base of $(\hat{\mbox{$\cal M$}}_{TV}\vee\mbox{$\cal
M$}_{T})\times T.$ Then there exist bases $b^{1}_{TV},b^{2}_{T}$ of
$\hat{\mbox{$\cal M$}}_{TV},\mbox{$\cal M$}_{T},$ respectively such that
$(b^{1}_{TV}\cap T)\cup b^{2}_{T}=\hat{b}_{T},$ and $(b^{1}_{TV}\cup
b^{2}_{T})\cap V=b^{1}_{TV}\cap V$ is a base of $(\hat{\mbox{$\cal
M$}}_{TV}\vee\mbox{$\cal M$}_{T})\circ V=\hat{\mbox{$\cal M$}}_{TV}\circ V.$
It follows that $(b^{1}_{TV}\cap T)$ is independent in $\hat{\mbox{$\cal
M$}}_{TV}\times T$ and $(b^{1}_{TV}\cap T)\cup b^{2}_{T}=\hat{b}_{T},$ is
independent in $(\hat{\mbox{$\cal M$}}_{TV}\times T)\vee\mbox{$\cal M$}_{T}.$

3\. $\mbox{$\cal M$}_{WTV}\circ TV\leftrightarrow\mbox{$\cal
M$}_{V}=(\mbox{$\cal M$}_{WTV}\circ TV\vee\mbox{$\cal M$}_{V})\times
T=(\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V})\circ TV\times T$
$=(\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V})\times WT\circ T$(using part 1
of Theorem 43) $=(\mbox{$\cal M$}_{WTV}\leftrightarrow\mbox{$\cal
M$}_{V})\circ T.$ ∎

###### Proof.

(Proof of Theorem 55)
We have $(\mbox{$\cal M$}_{WTV}\circ TV)\vee(\mbox{$\cal
M$}_{T}\oplus\mbox{$\cal M$}_{V})=\mbox{$\cal F$}_{TV}$ iff $r[(\mbox{$\cal
M$}_{WTV}\circ TV)\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal M$}_{V})]$
$=r[((\mbox{$\cal M$}_{WTV}\circ TV)\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal
M$}_{V}))\circ V]+r[((\mbox{$\cal M$}_{WTV}\circ TV)\vee(\mbox{$\cal
M$}_{T}\oplus\mbox{$\cal M$}_{V}))\times T]=|{T\uplus V}|,$
using Theorem 43. Since $r(\mbox{$\cal M$}_{X})\leq|X|,$ we have $(\mbox{$\cal
M$}_{WTV}\circ TV)\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal
M$}_{V})=\mbox{$\cal F$}_{TV}$ iff
$((\mbox{$\cal M$}_{WTV}\circ TV)\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal
M$}_{V}))\circ V=\mbox{$\cal F$}_{V},$ and $((\mbox{$\cal M$}_{WTV}\circ
TV)\vee(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal M$}_{V}))\times T=\mbox{$\cal
F$}_{T},$
i.e., iff $\mbox{$\cal M$}_{WTV}\circ V\vee\mbox{$\cal M$}_{V}=\mbox{$\cal
F$}_{V},$ and $((\mbox{$\cal M$}_{WTV}\circ TV\vee\mbox{$\cal M$}_{V})\times
T)\vee\mbox{$\cal M$}_{T}=\mbox{$\cal F$}_{T},$
using part 1 and 2 of Lemma 70, i.e., iff $\mbox{$\cal M$}_{WTV}\circ
V\vee\mbox{$\cal M$}_{V}=\mbox{$\cal F$}_{V},$
and $(\mbox{$\cal M$}_{WTV}\circ TV\leftrightarrow\mbox{$\cal
M$}_{V})\vee\mbox{$\cal M$}_{T}=((\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V})\circ T)\vee\mbox{$\cal
M$}_{T}=\mbox{$\cal F$}_{T},$
using Theorem 49, using part 3 of Lemma 70.
Thus the full sum property holds for $\\{\mbox{$\cal M$}_{WTV},(\mbox{$\cal
M$}_{T}\oplus\mbox{$\cal M$}_{V})\\}$ iff it holds for $\\{\mbox{$\cal
M$}_{WTV},\mbox{$\cal M$}_{V}\\}$ and for $\\{(\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V}),\mbox{$\cal M$}_{T}\\}.$

We will now use Theorems 42, 47, 43 and the Implicit Duality Theorem (Theorem
50) and get the second half of the property of rigidity that is required to
complete the proof.

From the above argument, we have $(\mbox{$\cal M$}_{WTV}^{*}\circ
TV)\vee(\mbox{$\cal M$}_{T}^{*}\oplus\mbox{$\cal M$}_{V}^{*})=\mbox{$\cal
F$}_{TV},$
iff $(\mbox{$\cal M$}_{WTV}^{*}\circ V)\vee\mbox{$\cal M$}_{V}^{*}=\mbox{$\cal
F$}_{V}$ and $((\mbox{$\cal M$}_{WTV}^{*}\leftrightarrow\mbox{$\cal
M$}_{V}^{*})\circ T)\vee\mbox{$\cal M$}_{T}^{*}=\mbox{$\cal F$}_{T},$
i.e., $((\mbox{$\cal M$}_{WTV}^{*}\circ TV)\vee(\mbox{$\cal
M$}_{T}^{*}\oplus\mbox{$\cal M$}_{V}^{*}))^{*}=\mbox{$\cal F$}^{*}_{TV}$
iff $(\mbox{$\cal M$}_{WTV}^{*}\circ V\vee\mbox{$\cal
M$}_{V}^{*})^{*}=\mbox{$\cal F$}^{*}_{V}$ and $(((\mbox{$\cal
M$}_{WTV}^{*}\leftrightarrow\mbox{$\cal M$}_{V}^{*})\circ T)\vee\mbox{$\cal
M$}_{T}^{*})^{*}=\mbox{$\cal F$}^{*}_{T},$
i.e., (using Theorems 42, 47) $(\mbox{$\cal M$}_{WTV}\times TV)\ \wedge\
(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal M$}_{V})={\mathbf{0}}_{TV},$
iff $(\mbox{$\cal M$}_{WTV}^{*}\circ V)^{*}\ \wedge\ \mbox{$\cal
M$}_{V}={\mathbf{0}}_{V}$ and $(\mbox{$\cal
M$}_{WTV}^{*}\leftrightarrow\mbox{$\cal M$}_{V}^{*})^{*}\times T\ \wedge\
\mbox{$\cal M$}_{T}={\mathbf{0}}_{T},$
i.e., (using Theorems 42, 43, 50) $(\mbox{$\cal M$}_{WTV}\times TV)\ \wedge\
(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal M$}_{V})={\mathbf{0}}_{TV},$
iff $(\mbox{$\cal M$}_{WTV}\times V)\ \wedge\ \mbox{$\cal
M$}_{V}={\mathbf{0}}_{V}$ and $(\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V})\times T\ \wedge\ \mbox{$\cal
M$}_{T}={\mathbf{0}}_{T}.$
Thus the zero intersection property holds for $\\{\mbox{$\cal
M$}_{WTV},(\mbox{$\cal M$}_{T}\oplus\mbox{$\cal M$}_{V})\\}$ iff it holds for
$\\{\mbox{$\cal M$}_{WTV},\mbox{$\cal M$}_{V}\\}$ and for $\\{(\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V}),\mbox{$\cal M$}_{T}\\}.$

2\. We have $\mbox{$\cal M$}_{WTV}\leftrightarrow\mbox{$\cal
M$}_{V}:\equiv(\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal M$}_{V})\circ
WT=(\mbox{$\cal M$}_{WTV}\vee\ \mbox{$\cal M$}_{V})\times WT$ (using Theorem
47).
Rigidity of $\\{\mbox{$\cal M$}_{WTV}\leftrightarrow\mbox{$\cal
M$}_{V},\mbox{$\cal M$}_{T}\\}$ is equivalent to the full sum and zero
intersection conditions
$((\mbox{$\cal M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V})\circ
T)\vee\mbox{$\cal M$}_{T}=\mbox{$\cal F$}_{T},$ and $((\mbox{$\cal
M$}_{WTV}\leftrightarrow\mbox{$\cal M$}_{V})\times T)\wedge\mbox{$\cal
M$}_{T}={\mathbf{0}}_{T}.$
The full sum condition is equivalent to $((\mbox{$\cal
M$}_{WTV}\wedge\mbox{$\cal M$}_{V})\circ WT\circ T)\vee\mbox{$\cal
M$}_{T}=((\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal M$}_{V})\circ
T)\vee\mbox{$\cal M$}_{T}=\mbox{$\cal F$}_{T}$ and the zero intersection
condition is equivalent to $((\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal
M$}_{V})\times WT\times T)\wedge\mbox{$\cal M$}_{T}$
$=((\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V})\times T)\wedge\mbox{$\cal
M$}_{T}={\mathbf{0}}_{T}.$

3\. Let us say matroid $\mbox{$\cal M$}^{1}_{X}\geq\mbox{$\cal M$}^{2}_{X},$
iff every base of $\mbox{$\cal M$}^{1}_{X}$ contains a base of $\mbox{$\cal
M$}^{2}_{X},$ and every base of $\mbox{$\cal M$}^{2}_{X},$ is contained in a
base of $\mbox{$\cal M$}^{1}_{X}.$ We observe that $(\mbox{$\cal
M$}_{WTV}\vee\mbox{$\cal M$}_{V})\geq(\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal
M$}_{V}),$ so that $(\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V})\circ
T\geq(\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal M$}_{V})\circ T$ and
$(\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V})\times T\geq(\mbox{$\cal
M$}_{WTV}\wedge\mbox{$\cal M$}_{V})\times T.$
Therefore, if $\\{\mbox{$\cal M$}_{WTV}\wedge\mbox{$\cal M$}_{V},\mbox{$\cal
M$}_{T}\\}$ satisfies the full sum condition, so does $\\{\mbox{$\cal
M$}_{WTV}\vee\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}$ and if
$\\{\mbox{$\cal M$}_{WTV}\vee\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}$
satisfies the zero intersection condition, so does $\\{\mbox{$\cal
M$}_{WTV}\wedge\mbox{$\cal M$}_{V},\mbox{$\cal M$}_{T}\\}.$
The result now follows from the previous part. ∎

##  Appendix B Matroidal conditions for rigidity of multiports

The matroidal approach to testing rigidity of multiports is based on the
following lemma which speaks of the rigidity of
$\\{\mbox{$\mathcal{V}$}_{AB},{\cal A}_{B}\\}$ where
$\mbox{$\mathcal{V}$}_{AB}$ is over ${\mathbb{Q}}$ and
$\mbox{$\mathcal{V}$}_{B}$ is in terms of parameters which are algebraically
independent over ${\mathbb{Q}}.$

######  Lemma 71.

Let ${\cal A}^{2}_{B}:\equiv{\cal A}^{2}_{B_{1}B_{2}}$ be the solution space
of the equation

$\displaystyle{y_{B_{2}}}={D}{x_{B_{1}}}+{s}.$ (10)

where $D$ is a diagonal matrix. Let ${\cal A}^{2}_{B_{1}B_{2}}$ have
$\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}}$ as its vector space translate. Let the
diagonal entries of $D$ be algebraically independent over ${\mathbb{Q}}.$

Let $(C_{B_{1}}|C_{B_{2}})$ be the representative matrix of a vector space
$\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}}$ with entries from ${\mathbb{Q}}.$ Let
there be a set of columns $j_{1},j_{2},\cdots,j_{n}$ of
$(C_{B_{1}}|C_{B_{2}}),$ which are linearly independent, and whose complement
with respect to $B_{1}\uplus B_{2},$ say $i_{1},i_{2},\cdots,i_{m}$ is a
column base of the matrix

$\displaystyle
F=\begin{pmatrix}F_{B_{1}}|F_{B_{2}}\end{pmatrix}:\equiv\begin{pmatrix}I&D\end{pmatrix}.$
(11)

We then have the following.

  1. 1.

Let
$r(\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}})+r(\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}})\geq|B_{1}\uplus
B_{2}|=|B|.$ Then
$\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}},\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}}$
have the full sum property.

  2. 2.

Let
$r(\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}})+r(\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}})\leq|B_{1}\uplus
B_{2}|=|B|.$ Then
$\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}},\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}}$
have the zero intersection property.

  3. 3.

Let $\mbox{$\mathcal{V}$}^{1}_{AB}$ be a vector space over ${\mathbb{Q}}$ and
let $\mbox{$\mathcal{V}$}^{2}_{B}$ be the vector space translate of ${\cal
A}^{2}_{B}$ defined by Equation 10.

    1. (a)

$\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{1}_{AB}+\mbox{$\mathcal{V}$}^{2}_{B})=\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{1}_{AB})\vee\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{2}_{B})$ and $\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}^{1}_{AB})^{\perp}+(\mbox{$\mathcal{V}$}^{2}_{B})^{\perp})=\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}^{1}_{AB})^{\perp})\vee\mbox{$\cal
M$}((\mbox{$\mathcal{V}$}^{2}_{B})^{\perp}).$

    2. (b)

The following are equivalent.

      1. i.

There exists a pair of disjoint bases $b^{1},b^{2}$ of
$\mbox{$\mathcal{V}$}^{1}_{AB},\mbox{$\mathcal{V}$}^{2}_{B},$ respectively
such that $b^{1}\cup b^{2}\supseteq B.$

      2. ii.

$r(\mbox{$\mathcal{V}$}^{1}_{AB}\circ
B)+r(\mbox{$\mathcal{V}$}^{2}_{B})\geq|B|$ and
$r((\mbox{$\mathcal{V}$}^{1}_{AB})^{\perp}\circ
B)+r((\mbox{$\mathcal{V}$}^{2}_{B})^{\perp})\geq|B|.$

      3. iii.

$\\{\mbox{$\mathcal{V}$}^{1}_{AB},\mbox{$\mathcal{V}$}^{2}_{B}\\}$ is rigid.

      4. iv.

$\\{\mbox{$\cal M$}(\mbox{$\mathcal{V}$}^{1}_{AB}),\mbox{$\cal
M$}(\mbox{$\mathcal{V}$}^{2}_{B})\\}$ is rigid.

###### Proof.

1\. It is clear that $F$ is a representative matrix for
$\mbox{$\mathcal{V}$}^{2}_{B}.$ Let $(C_{2B_{1}}|C_{2B_{2}})$ be a suitable
submatrix of $(C_{B_{1}}|C_{B_{2}})$ such that

$\displaystyle\begin{pmatrix}C_{2B_{1}}&C_{2B_{2}}\\\ I&D\end{pmatrix}$ (12)

is square. This is possible since
$r(\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}})+r(\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}})\geq|B_{1}\uplus
B_{2}|=|B|.$ Perform a Laplace expansion of the determinant of this matrix
using the first set of rows as one block in the partition of rows. One term in
this expansion is $\pm det(C_{2}^{j})\times det(F^{i}),$ where $C_{2}^{j}$
denotes the submatrix of $(C_{2B_{1}}|C_{2B_{2}})$ corresponding to set of
columns $j_{1},j_{2},\cdots,j_{n}$ and all rows, $F^{i}$ denotes the submatrix
of $F$ corresponding to set of columns $i_{1},i_{2},\cdots,i_{m}$ and all
rows.

We know that the determinants of $C_{2}^{j}$ and $F^{i}$ are nonzero since
their columns are linearly independent. Therefore this term cannot be zero.
The determinant of $F^{i}$ has only one nonzero term which will have the form
$\pm D_{k1}\times\cdots\times D_{kt}.$ Suppose another pair
$C_{2}^{j^{\prime}}$ and $F^{i^{\prime}}$ in the Laplace expansion also has
nonzero determinants. The determinant of $F^{i^{\prime}}$ has only one nonzero
term which will have the form
$\pm D_{k^{\prime}1}\times\cdots\times D_{k^{\prime}t^{\prime}}.$ Since the
columns of $F^{i}$ as well as $F^{i^{\prime}}$ form column bases of the matrix
$F,$ it is clear that the sets
$\\{D_{k1},\cdots,D_{kt}\\},\\{D_{k^{\prime}1},\cdots,D_{k^{\prime}t^{\prime}}\\},$
are distinct. Therefore the Laplace expansion will be a polynomial involving
distinct subsets of $\\{D_{1},\cdots D_{|B_{2}|},\\}$ in different terms and
by algebraic independence of these variables over ${\mathbb{Q}},$ the
polynomial cannot take the value zero. Thus the matrix in Equation 12 is
nonsingular. We conclude that
$r(\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}}+\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}})=|B_{1}\uplus
B_{2}|$ and therefore that
$\mbox{$\mathcal{V}$}^{1}_{B_{1}B_{2}},\mbox{$\mathcal{V}$}^{2}_{B_{1}B_{2}}$
have full sum property.

2\. For handling the zero intersection case, when