# Generalized Integer Splines on Arbitrary Graphs

Lauren L. Rose  Department of Mathematics, Bard College, Annandale-on-Hudson,
NY, 12504<EMAIL_ADDRESS>and  Jeff Suzuki  Department of Mathematics, Brooklyn
College, Brooklyn, NY 11210<EMAIL_ADDRESS>
###### Abstract.

Generalized integer splines on a graph $G$ with integer edge weights are
integer vertex labelings such that if two vertices share an edge in $G$, the
vertex labels are congruent modulo the edge weight. We introduce collapsing
operations that reduce any simple graph to a single vertex, carrying with it
the edge weight information. This corresponds to a sequence of surjective maps
between the associated spline modules, leading to an explicit construction of
a $\mathbb{Z}$-module basis in terms of the edge weights.

###### Key words and phrases:

splines, number theory, module theory, graph theory

Thanks to Tom Zaslavsky for several helpful conversations.

## Introduction

Consider a graph $G$ with integer edge weights. Label the vertices so that if
two vertices are joined by an edge with weight $w$, then their vertex labels
are congruent modulo $w$. This leads to the following questions:

  * •

Given arbitrary edge weights, can we always construct a vertex labeling?

  * •

Can we find a finite set that generates all vertex labelings?

In [6], Tymozcko, et. al. introduced the study of generalized splines on a
graph with edges weighted by ideals in a commutative ring $R$. Their
foundational paper concludes with many open questions, primarily about the
$R$-module structure of sets of splines and how much this structure is
determined by properties of the ring and/or the underlying graph. A subsequent
survey article [13] describes the role that generalized splines play in
geometry and topology.

In this paper we set $R$ to be $\mathbb{Z}$, the ring of integers, although
the results in this paper hold when $R$ is an Euclidean Ring, with minor
modifications. We answer both of the above questions affirmatively, and in
doing so find a complete characterization of spline modules over $\mathbb{Z}$
for arbitrary graphs.

Generalized splines are a generalization of polynomial splines, which are
ubiquitous in applied math, computer graphics and approximation theory. They
are often defined to be piecewise polynomial functions on a polyhedral
subdivision of $\mathbb{R}^{d}$. Alfeld and others [1] studied the question of
finding dimensions and bases for vector spaces of splines of restricted
polynomial degree. In [3, 5], Billera pioneered the use of algebraic
techniques in the study of polynomial splines. When the polynomial degrees are
unrestricted, the set of all splines on a polyhedral complex will be both a
ring and an $R$-module, where $R$ is a polynomial ring in $d$ variables over a
field.

The algebraic study of polynomial splines led to a representation of splines
as vertex labels of the dual graph of the polyhedral complex [11, 10], where
the edges are labeled with linear forms. In this new representation, a set of
vertex labels is a spline if each edge label divides the difference between
its two vertex labels. This representation easily extends to arbitrary rings,
and in fact arises in geometry and topology.

When $R$ is a principal ideal domain, generalized spline modules are always
free of rank $n$, the number of vertices of the graph. In [8], Handschy, et.
al, constructed “flow-up class” bases for $n$-cycle graphs with integer edge
weights. In [9] we proved that flow-up class bases exist for spline modules
over arbitrary graphs with integer edge weights, and expanded the class of
graphs for which a flow-up class basis could be constructed.

The main result of this paper is the construction of flow-up class bases for
the spline module $S_{G}$, for any arbitrary graph $G$ with integer edge
weights. To do this, we introduce two collapsing operations that transform $G$
into a graph with fewer vertices or edges. Using these operations, we can
reduce any connected graph to a point. Then we show that each of these
operations induces a surjective $\mathbb{Z}$-module map of the associated
spline modules. The main algebraic result is that $S_{G}$ is the direct sum of
the kernels of these maps. From there, all that is left to do is to construct
a basis for each of the kernels, and show that their pre-images form a basis
for $S_{G}$. A nice feature of this construction is that the first non-zero
entry of each basis element, viewed as an $n$-tuple of $\mathbb{Z}^{n}$, can
be written in terms of least common multiples and greatest common divisors of
a subset of the edge weights.

##  1\. Preliminaries

We begin with a formal definition of a generalized integer spline. Let $G$ be
a graph with $n$ vertices, edge set $E$, and $A:E\rightarrow\mathbb{N}$ an
assignment of positive integer weights to edges of $G$.

We denote the set of splines on $(G,A)$ by $S_{G}(A)$, or just $S_{G}$ when
there is no ambiguity.

######  Definition 1.1.

Let $G$ a graph with $n$ vertices. A generalized integer spline on $G$ is an
$n$-tuple $(g_{1},g_{2},\ldots,g_{n})\in{\mathbb{Z}}^{n}$ such that if
vertices $v_{i}$ and $v_{j}$ are joined by $e\in E$, then $g_{i}\equiv
g_{j}\bmod A(e)$. We refer to these equations as the defining equations for
$S_{G}$.

######  Example 1.2.

Let $G$ be a 3-cycle with edge labels $a,b,c$ as in Figure1. By the definition
above, $(g_{1},g_{2},g_{3})\in Z^{3}$ is a spline in $S_{G}$ if the following
defining equations, one for each edge, are satisfied.

$\displaystyle g_{1}$ $\displaystyle\equiv g_{2}\bmod{a}$ $\displaystyle
g_{2}$ $\displaystyle\equiv g_{3}\bmod{b}$ $\displaystyle g_{3}$
$\displaystyle\equiv g_{1}\bmod{c}$

$g_{3}$$g_{2}$$g_{1}$$a$$b$$c$ Figure 1. A $3$-cycle

Notation: Let $(r_{1},r_{2},\ldots r_{m})$ denote the GCD and
$[r_{1},r_{2},\ldots r_{m}]$ denote the LCM of the set $\\{r_{1},r_{2},\ldots
r_{m}\\}$.

The following lemma will be used in later sections. The proofs are
straightforward, so we omit them.

######  Lemma 1.3.

Let $a,b,m,n$ in $\mathbb{N}$.

  1. (1)

$(a,(b,c))=(a,b,c)$.

  2. (2)

$[a,[b,c]]=[a,b,c]$.

  3. (3)

$[(a,c),(b,c)]=([a,b],c)$.

  4. (4)

$x\equiv a\bmod m$ and $x\equiv a\bmod n$ if and only if $x\equiv
a\bmod[m,n]$.

We will need the non-coprime version of the Chinese Remainder Theorem, which
we state for convenience.

######  Theorem 1.4 (Non-Coprime Chinese Remainder Theorem).

Let $a_{i}\in\mathbb{Z}$ and $m_{i}\in\mathbb{N}$ for $i$ between 1 and $n$.
The system of congruences

$\displaystyle x$ $\displaystyle\equiv a_{1}\bmod{m_{1}}$ $\displaystyle x$
$\displaystyle\equiv a_{2}\bmod{m_{2}}$ $\displaystyle\vdots$ $\displaystyle
x$ $\displaystyle\equiv a_{n}\bmod{m_{n}}$

has a solution if and only if

$a_{i}\equiv a_{j}\bmod(m_{i},m_{j})$

for all $i,j$ with $1\leq i,j\leq n$. If a solution exists, then it is unique
modulo $[m_{1},m_{2},\dots,m_{n}]$.

##  2\. Collapsing Operations on $G$

In this section, we define two operations on $(G,A)$ that yield another edge-
weighted graph $(G^{\prime},A^{\prime})$ with either fewer vertices or the
same number of vertices and fewer edges. We will show that for any $(G,A)$,
and vertices $v_{i}$ and $v_{j}$, there exists a sequence of operations that
yield the weighted edge $(K_{2},A_{*})$, for some $A_{*}$ in $\mathbb{N}$.
Moreover, we will show that any spline on $(K_{2},A_{*})$ can be extended to a
spline on $(G,A)$. We can then use this collapse sequence to construct a
$\mathbb{Z}$-module basis for $S_{G}$.

######  Definition 2.1.

Let $G$ be a graph and $v$ a vertex of $G$ of degree $d$.

  1. (1)

The star of $v$, denoted $st(v)$, is the subgraph consisting of $v$ and all
edges that contain $v$.

  2. (2)

A $d$-clique is a subgraph that is a complete graph on $d$ vertices.

The first collapse operation replaces the star of $v$ with a $d$-clique, where
$d$ is the degree of $v$, using the neighbors of $v$ are the vertices. All
other vertices and edges in the graph remain the same, although the new graph
may have multiple edges. We call this a star-clique operation, as we are
deleting a vertex star, and then adding new edges to the adjacent $d$ vertices
to form a $d$-clique. This generalizes the standard ${\mathbf{Y-\Delta}}$
transform that takes a 3-star to the 3-clique $K_{3}$. We now define this
process more formally.

######  Definition 2.2.

Let $v$ be a vertex of $G$ of degree $d$, with adjacent vertices
$\\{v_{1},\ldots,v_{d}\\}$ and incident edge weights
$\\{a_{1},\ldots,a_{d}\\}$. The star-clique operation transforms $(G,A)$ to
$(G_{v},A_{v})$ as follows.

  * •

Remove $v$ and the edges of $st(v)$, but keep the adjacent vertices.

  * •

Add edges between adjacent vertices to form a $d$-clique.

  * •

Label the new edge between $v_{i}$ and $v_{j}$ with $(a_{i},a_{j})$.

######  Example 2.3.

Let $v_{2}$ be a vertex of degree $1$, with adjacent vertex $v_{1}$ and
incident edge $e$ with weight $a$. The star-clique operation replaces the star
of $v_{2}$, an edge, with a 1-clique, which is the single vertex $v_{1}$. We
call this a leaf deletion. See Figure 2.

|
---|---
Figure 2. Leaf Deletion

######  Example 2.4.

Let $v_{2}$ have degree 2, with adjacent vertices $v_{1}$ and $v_{3}$ and
incident edges with weights $a$ and $b$. The star-clique operation replaces
the star of $v_{2}$, i.e. the path $v_{1}v_{2}v_{3}$, with the edge
$v_{1}v_{3}$. This is a path contraction, with edge weights $a$ and $b$
replaced by $(a,b)$ (see Figure 3).

|
---|---
Figure 3. Path Contraction Operation on $v_{2}$

######  Example 2.5.

Let $v_{4}$ be a vertex of degree $3$, with adjacent vertices $v_{1}$, $v_{2}$
and $v_{3}$ and incident edge weights $c,a,b$. The star-clique operation
replaces the star of $v_{4}$, a “$Y$-graph,” with a triangle with vertices
$v_{1},v_{2},v_{3}$. The new edges will have weights $(a,c),(a,b),(b,c)$, as
shown inn Figure 4).

|
---|---
Figure 4. Star-clique Operation ($Y$-$\Delta$ Transform)

The new graph $(G_{v},A_{v})$ has one fewer vertex, but may no longer be a
simple graph if some of the $v_{i}$’s were already be connected in $G$.

In order to turn $G_{v}$ into a simple graph, so that we can apply the star-
clique operation again, we introduce a second operation, edge collapse, that
collapses multiple edges between the same pair of vertices (see Figure 5).

######  Definition 2.6.

Let $e_{1},e_{2},\ldots e_{r}$ be multiple edges between vertices $v$ and $w$
in $G$ with labels $\\{a_{1},\ldots,a_{r}\\}$. The edge-collapes operation
transforms $(G,A)$ to $(G^{\prime},A^{\prime})$ as follows.

  * •

Remove $e_{1},e_{2},\ldots e_{r}$.

  * •

Add a new edge $e$ between $v$ and $w$.

  * •

Label $e$ with $[a_{1},a_{2},\ldots,a_{r}]$.

######  Example 2.7.

Let $v_{1},v_{2}$ be two vertices joined by edges of weights $a,b$. The edge-
collapse operation replaces these edges with a single edge of weight $[a,b]$
(see Figure 5).

|
---|---
Figure 5. Edge Collapse

######  Lemma 2.8.

Let $(G,A)$ be a simple, connected graph containing at least one vertex $v$.
Then $(G_{v},A_{v})$ is also connected.

###### Proof.

We consider two cases.

  * •

Case 1: If $G_{v}$ is the empty graph or has only one vertex, then it is
vacuously connected.

  * •

Case 2: Assume $G_{v}$ has 2 or more vertices. Let $x$ and $y$ be distinct
vertices of $G_{v}$. Hence they are vertices in $G$ since $G_{v}$ doesn’t
introduce new vertices. Since $G$ is connected, there is a path $P$ connecting
$x$ and $y$ in $G$. There are two cases.

    * –

First, assume $P$ does not pass through the vertex $v$. The removal of $v$
does not affect $P$, so $P$ is also a path in $G_{v}$.

    * –

Now suppose $P$ passes through the vertex $v$. Then $P$ passes through
vertices $p$ and $q$, where $p$ and $q$ are adjacent to $v$. When we form
$G_{v}$, the path $pvq$ in $G$ will be replaced by a single edge $pq$. Thus,
we can form a path $P_{v}$ from $x$ to $y$ in $G_{v}$ by replacing the edges
$pv$ and $vq$ with the edge $pq$ in $G_{v}$.

∎

A graph can always be collapsed to a single edge, and even further to a single
vertex.

######  Lemma 2.9.

Let $(G,A)$ be a connected edge-weighted graph, and let $v$ and $w$ be
vertices of $G$.

  1. (1)

We can collapse $G$ to the graph $K_{2}$ with vertices $v$ and $w$.

  2. (2)

We can collapse $G$ to the vertex $v$.

###### Proof.

Choose a vertex other than $v$ and $w$ and do a star-clique operation. This
will reduce the number of vertices by one. Now do an edge collapse to remove
multiple edges. Repeat until $v$ and $w$ are the only vertices left, and
remove any multiple edges. Since the graphs at each stage are connected, by
Lemma 2.8, we are left with a single edge between $v$ and $w$.

For part 2, a star-clique operation on $w$ will transform the edge $vw$ into
the single vertex $v$. ∎

##  3\. The Spline Modules $S_{G}$ and $S_{G^{\prime}}$

Now that we have constructed the graph collapsing operations, we describe
their effects on the spline module $S_{G}$. In order to do this, we must first
fix an ordering of the vertices $v_{1},\ldots,v_{n}$ of $G$. Next, we
partition $S_{G}$ into flow-up classes $\mathcal{F}_{i}$, which are subsets of
splines with the first $i$ entries equal to zero and the $i+1$st entry non-
zero. A flow-up class basis will be a basis that consists of an element from
each non-zero flow-up class.

######  Definition 3.1.

For $0\leq i<n$, the $i$th flow-up class, denoted $\mathcal{F}_{i}$, is the
set of splines of the form $F=(0,0,\ldots,0,f_{i+1},\ldots,f_{n})$ where
$f_{i+1}$ is non-zero. We also define
$\mathcal{F}_{n}=\left\\{\mathbf{0}\right\\}=\mathbf{0}=(0,0,\ldots,0)$, the
zero spline.

We now define the leading term of a spline to be its first non-zero entry.

######  Definition 3.2.

Let $F\in\mathcal{F}_{i}$ where $i\neq n$, so that
$F=(0,0,\ldots,0,f_{i+1},\ldots,f_{n})$ and $f_{i+1}\neq 0$. $L(F)=f_{i+1}$ is
the leading term of $F$.

######  Definition 3.3.

A spline $B\in\mathcal{F}_{i}$ is a minimal element of $\mathcal{F}_{i}$ if
$L(B)>0$, and for all $F\in\mathcal{F}_{k}$, $(L(B)\leq|L(F)|$.

For example, $\mathbf{1}=(1,1,\ldots,1)$ has leading term $1$, which is
minimal in $\mathbb{N}$. Thus, $\mathbf{1}$ is a minimal element of
$\mathcal{F}_{0}$.

Note: Although minimal elements of $\mathcal{F}_{i}$ have the same leading
term, the other terms are not in general unique.

Our strategy for constructing a basis for $S_{G}$ is to find a minimal element
from each $\mathcal{F}_{i}$, for $i<n$. The theorem below asserts that this
set will alway form a basis, called a flow-up class basis.

######  Theorem 3.4.

[9] Let $(G,A)$ be an edge labeled graph with $n$ vertices. Let
$\mathcal{B}=\left\\{B_{0},B_{1},\dots,B_{n-1}\right\\}\subset S_{G}$ where
each $B_{i}$ is a minimal element of $\mathcal{F}_{i}$. Then $\mathcal{B}$ is
a $\mathbb{Z}$-module basis for $S_{G}$.

We now look at the effect of collapsing operations on flow-up classes and
minimal elements. We begin with an example.

######  Example 3.5.

Let $G$ be the $Y$-graph with vertices $v_{1},v_{2},v_{3},v_{4}$, and edge
labels $a$, $b$, $c$, as in Figure 4. The star-clique operation on $v_{4}$
yields a $3$-cycle $G^{\prime}$ with edge labels $(a,b)$, $(b,c)$, and
$(a,c)$.

Let $(v_{1},v_{2},v_{3},v_{4})\in S_{G}$. The defining equations on $G$ are

(3.4) $\displaystyle\begin{array}[]{rcl}v_{4}&\equiv&v_{1}\bmod c\\\
v_{4}&\equiv&v_{2}\bmod a\\\ v_{4}&\equiv&v_{3}\bmod b\end{array}$

By the Theorem 1.4, Equation 3.4 has a solution if and only if

(3.8) $\displaystyle\begin{array}[]{rcl}v_{1}&\equiv&v_{2}\mod(a,c)\\\
v_{2}&\equiv&v_{3}\mod(a,b)\\\ v_{3}&\equiv&v_{1}\mod(b,c)\end{array}$

Note that these are in fact the defining equations of $S_{G^{\prime}}$. Thus
the projection map

$\phi:S_{G}\rightarrow S_{G^{\prime}}$

defined by $\phi(v_{1},v_{2},v_{3},v_{4})=(v_{1},v_{2},v_{3})$ is well
defined, due to the forward direction of Theorem 1.4, and surjective by the
reverse direction. Since it’s a projection map, it is also an
$\mathbb{Z}$-module homomorphism. Let $K$ be the kernel of $\phi$. Then
$\mathbf{g}$ is in $K=\phi^{-1}(\mathbf{0})$ if an only if
$\mathbf{g}=(0,0,0,v_{4})$ in $S_{G}$. Substituting these values into (1), we
get

(3.12) $\displaystyle\begin{array}[]{rcl}v_{4}&\equiv&0\bmod a\\\
v_{4}&\equiv&0\bmod b\\\ v_{4}&\equiv&0\bmod c\end{array}$

which have as solutions $g_{4}\equiv 0\bmod[a,b,c]$. Thus
$\mathbf{g}=(0,0,0,[a,b,c])$ is a minimal element of $\mathcal{F}_{3}$ and
forms a basis for $K$.

We can formalize this process for any graph.

######  Theorem 3.6.

Let $(G,A)$ be an edge-weighted simple graph on vertices
$\\{v_{1},\ldots,v_{n}\\}$ and let $(G_{n},A_{n})$ be the result of a star-
clique operation on vertex $v_{n}$. The map $\phi:S_{G}\rightarrow S_{G_{n}}$
defined by $\phi(g_{1},g_{2},\ldots,g_{n})=(g_{1},g_{2},\ldots,g_{n-1})$ is a
surjective $\mathbb{Z}$-module homomorphism with kernel
$\mathcal{F}_{n-1}\cup{\mathcal{F}}_{n}$.

###### Proof.

The first thing to note is that the only edges affected by a star-clique
operation are those incident to vertex $v$, say $v_{i_{1}},\ldots,v_{i_{d}}$.
Thus the defining equations for $S_{G}$ and $S_{G_{n}}$ only differ in that
$S_{G}$ includes equations

$\displaystyle g_{n}$ $\displaystyle\equiv g_{i_{1}}\bmod a_{i_{1}}$
$\displaystyle g_{n}$ $\displaystyle\equiv g_{i_{2}}\bmod a_{i_{2}}$
$\displaystyle\vdots$ $\displaystyle g_{n}$ $\displaystyle\equiv
g_{i_{d}}\bmod a_{i_{d}}$

whereas $S_{G_{n}}$ includes the equations

$g_{i_{j}}\equiv g_{i_{k}}\bmod(a_{i_{j}},a_{i_{k}}),\text{ for all }1\leq
j\leq d$

By Theorem 1.4, the first set of equations implies that second, hence $\phi$
is well defined. Also by Theorem 1.4, the second set of equations implies
there exists a $g_{n}$ satisfying the first set, and since the remaining
equations don’t involve $g_{n}$, we have shown there exists a spline in
$S_{G}$ mapping to a given spline in $S_{G_{n}}$.

Now let $K$ denote the kernel of $\phi$. Then $\mathbf{g}\in
K=\phi^{-1}(\mathbf{0})$ if and only if $\mathbf{g}=(0,\ldots,0,g_{n})$ in
$S_{G}$. If $g_{n}\neq 0$, then $\mathbf{g}$ has exactly $n$ zeroes, hence is
an element of ${\mathcal{F}}_{n-1}$. If $g_{n}=0$, then
$\mathbf{g}=\mathbf{0}$, the only element of ${\mathcal{F}}_{n}$. ∎

######  Theorem 3.7.

Let$(G,A)$ be an edge weighted graph and $(G^{\prime},A^{\prime})$ be the
result of an edge collapse operation on multiple edges
$e_{1},e_{2},\ldots,e_{r}$. Then $S_{G^{\prime}}=S_{G}$.

###### Proof.

Suppose that edges $e_{1},e_{2},\ldots,e_{r}$ each connect vertices $v$ and
$w$, and have edge labels $a_{1},a_{2},\ldots,a_{r}$. The label for the new
edge $e$ in $G^{\prime},A^{\prime}$ is $[a_{1},a_{2},\ldots,a_{r}]$. Thus the
only difference between the defining equations for $S_{G}$ and
$S_{G^{\prime}}$ are the $r$ equations $g_{v}\equiv g_{w}\bmod a_{i}$ and the
single equation $g_{v}\equiv g_{w}\bmod[a_{1},a_{2},\ldots,a_{r}]$ in
$S_{G_{e}}$. By Lemma 1.3, these two sets of equations have the same
solutions, hence $S_{G^{\prime}}=S_{G}$. ∎

In other words, collapsing multiple edges changes the graph, but not the
corresponding spline module. Putting these theorems together we now state our
main result of this section.

######  Theorem 3.8.

Let $(G^{\prime},A^{\prime})$ be the result of a sequence of collapsing
operations on an edge-weighted graph $(G,A)$ resulting in the removal of
vertices $v_{r+1},\dots v_{n}$ and the collapsing of any multiple edges. Then
the map $\phi:S_{G}\rightarrow S_{G^{\prime}}$ defined by
$\phi(g_{1},g_{2},\ldots,g_{n})=(g_{1},g_{2},\ldots,g_{r})$ is a surjective
$\mathbb{Z}$-module homomorphism with kernel
$\mathcal{F}_{r}\cup\cdots\cup\mathcal{F}_{n-1}\cup\mathcal{F}_{n}$.

###### Proof.

By Theorem 3.6, each time we do a star-clique operation, we have a surjective
$\mathbb{Z}$\- module homomorphism $\phi:S_{G}\rightarrow S_{G_{v}}$, and each
time we do an edge collapse, the module stays the same. Since $\phi$ is a
composition of finitely many surjective $\mathbb{Z}$-module homomorphisms, it
is also a surjective $\mathbb{Z}$-module homomorphism.

Let $K$ denote the kernel of $\phi$. Then $\mathbf{g}\in
K=\phi^{-1}(\mathbf{0})$ if and only if
$\mathbf{g}=(0,\ldots,0,g_{r+1},\ldots,g_{n})$ in $S_{G}$. Since $\mathbf{g}$
has at least $r$ zeroes, it is an element of $\mathcal{F}_{i}$ for some $i\geq
r$. ∎

######  Corollary 3.9.

Let $(G,A)$ be an edge-weighted graph on $n$ vertices and $v_{i}$ and $v_{j}$
be distinct vertices of $G$. The map $\phi:S_{G}\rightarrow S_{K_{2}}$ defined
by $\phi(g_{1},g_{2},\ldots,g_{n})=(g_{i},g_{j})$ is a surjective
$\mathbb{Z}$-module homomorphism.

###### Proof.

We start with $(G,A)$ and delete vertices one by one until there are only two
vertices left. Each time we end up with multiple edges, we collapse them and
replace $S_{G}$ with $S_{G_{e}}$. By Theorem 3.8, the result now follows. ∎

##  4\. A basis for $S_{G}$

We now use the map $\phi$ to compare flow-up classes and minimal elements of
$S_{G}$ and $S_{G^{\prime}}$.

######  Theorem 4.1.

Let $(G^{\prime},A^{\prime})$ be the result of collapsing operations that
remove vertices $v_{r+1},\ldots,v_{n}$. Define $\phi:S_{G}\rightarrow
S_{G^{\prime}}$ by
$\phi(g_{1},g_{2},\ldots,g_{n})=(g_{1},g_{2},\ldots,g_{r})$. Suppose $i<r$,
$F\in{\mathcal{F}_{i}}$, and $K$ is the kernel of $\phi$. Then,

  1. (1)

$\phi({\mathcal{F}})={\mathcal{F}^{\prime}_{i}}$

  2. (2)

$L(F)=L(\phi(F))$.

  3. (3)

$F$ is minimal if and only if $\phi(F)$ is minimal.

  4. (4)

Let $\mathcal{B}^{\prime}$ and $\mathcal{K}$ be flow-up class bases for
$S_{G^{\prime}}$ and $K$, respectively. Let $\mathcal{B}$ consist of a pre-
image of each element of $\mathcal{B}^{\prime}$. Then
$\mathcal{B}\cup\mathcal{K}$ is a flow-up class basis of $S_{G}$.

  5. (5)

As $R$-modules, $S_{G}\cong S_{G^{\prime}}\oplus K$.

###### Proof.

  1. (1)

If $F=(0,\ldots,0,f_{i+1},\ldots,f_{n})$ has $i$ leading zeroes, then
$\phi(F)=(0,\ldots,0,f_{i+1},\dots f_{r})$ also has $i$ leading zeroes.

  2. (2)

$L(F)=f_{i+1}=L(\phi(F))$.

  3. (3)

If $F$ is minimal but $\phi(F)$ is not, then there is some $M^{\prime}$ in
${\mathcal{F}^{\prime}_{i}}$ such that $|L(M^{\prime})|<|L(\phi{F})|$. Let $M$
be in the inverse image of $M^{\prime}$. By (2), $L(M)=L(M^{\prime})$, so
$|L(M)|<|L(\phi{F})|$, which contradicts the minimality of $F$. Conversely,
suppose $F^{\prime}=\phi(F)$ is minimal but $F$ is not. Then there exists $M$
in ${\mathcal{F}_{i}}$ such that $|L(M)|<|L({F})|$. Then $L(M)=L(\phi(M))$,
which implies $|L(\phi(M)|<|L({F^{\prime}})|$, contradicting the minimality of
$F^{\prime}$.

  4. (4)

Since $\mathcal{B}^{\prime}$ and $\mathcal{K}$ are flow-up class bases, their
leading terms are minimal in $S_{G^{\prime}}$ and $K$, respectively. Let
$\mathcal{B}$ be a set of inverse images of elements of
$\mathcal{B}^{\prime}$. By (3), these elements will minimal and there will be
one from each flow-up class $\mathcal{F}_{0},\ldots,\mathcal{F}_{r-1}$. To
complete a basis for $S_{G}$, we need a minimal element from each remaining
non-zero flow-up classes $\mathcal{F}_{r},\ldots,\mathcal{F}_{n-1}$. By
Theorem 3.8,
$K=\mathcal{F}_{r}\cup\cdots\cup\mathcal{F}_{n-1}\cup\mathcal{F}_{n}$. Thus
any flow-up class basis for $K$ will complete a basis of $S_{G}$, making
$\mathcal{B}\cup\mathcal{K}$ a flow-up class basis for $S_{G}$.

  5. (5)

This follows from (4).

∎

In fact, we can describe $S_{G}$ as the direct sum of rank 1 kernels of
collapsing maps. First, we define a complete collapse sequence of graphs.

######  Definition 4.2.

Let $(G,A)$ be a simple edge-weighted graph with $n$ vertices. A complete
collapse sequence is a set of graphs $\\{G_{n},\ldots,G_{1}\\}$, where
$G=G_{n}$ and for $2\leq i\leq n$, $G_{i-1}$ is result of collapsing
operations that remove the vertex $v_{i}$ from $G_{i}$.

Note that each $G_{i}$ contains $i$ vertices and that $G_{1}$ is a graph
consisting of the single vertex $v_{1}$.

######  Theorem 4.3.

Let $\\{G_{k}\\}$ be a complete collapse sequence of $(G,A)$. Define

$S_{G_{n}}\xrightarrow{\phi_{n}}S_{G_{n-1}}\cdots\xrightarrow{\phi_{3}}S_{G_{2}}\xrightarrow{\phi_{2}}S_{G_{1}}\xrightarrow{\phi_{1}}{0}$

by $\phi_{i}(g_{1},g_{2},\ldots,g_{i})=(g_{1},g_{2},\ldots,g_{i-1})$ for
$i>1$, and $\phi_{1}(g_{1})=0$. Let $K_{i}$ denote the kernel of $\phi_{i}$.
Then

  1. (1)

$S_{G}\cong{K}_{1}\oplus{K}_{2}\oplus\cdots\oplus{{K}}_{n}$.

  2. (2)

$K_{i}$ is a rank 1 submodule of $S_{G_{i}}$.

  3. (3)

Let $st(v_{i})$ in $G_{i}$ have edge weights $\\{c_{1},\ldots,c_{d}\\}$. Then
$m_{1}=(1)$ generates $K_{1}$ and and
$m_{i}=(0,0,\ldots,[c_{1},\ldots,c_{d}])$ generates $K_{i}$, for $i>1$.

  4. (4)

For each $i<n$, let $M_{i}$ in $S_{G}$ be a pre-image of $m_{i}$ under the map
$\phi_{n}\circ\phi_{n-1}\cdots\circ\phi_{i+1}$, and let $M_{n}=m_{n}$. Then
$\\{M_{1},\ldots M_{n}\\}$ is a flow-up class basis for $S_{G}$ where
$M_{i}\in{\mathcal{F}_{i-1}}$.

###### Proof.

By Theorem 4.1, for all $i>1$ $S_{G_{i}}\cong
S_{G_{i-1}}\oplus\mathcal{K}_{i}$. When $i=n$ and $n-1$, we have $S_{G}\cong
S_{G_{n-1}}\oplus\mathcal{K}_{n}$ and $S_{G_{n-1}}\cong
S_{G_{n-2}}\oplus\mathcal{K}_{n-1}$. Putting these together we have

$S_{G}=S_{G_{n-2}}\oplus\mathcal{K}_{n}\oplus\mathcal{K}_{n-1}$

We can continue in this manner, down to $i=2$, to get
$S_{G}\cong\mathcal{K}_{n}\oplus\mathcal{K}_{n-1}\oplus\cdots\oplus\mathcal{K}_{2}\oplus
S_{G_{1}}$. The last map $\phi_{1}:S_{G_{1}}\rightarrow 0$ is the zero map, so
$K_{1}=S_{G_{1}}$, giving us the first result. Since $G_{1}$ has no edges, and
hence no defining equations, $S_{G_{1}}=R$. Thus $K_{1}=R$ , which is
generated by the element (1). For $i>1$, elements of $K_{i}$ have form
$(0,0,\ldots,0,g_{i})$. Thus $K_{i}$ is isomorphic to a non-zero submodule of
$R$, hence $K_{i}$ has rank 1. Elements of $K_{i}$ correspond to vertex labels
$g_{i}$ for $v_{i}$ and 0 for all other vertices, so the defining equations
are $g_{i}\equiv 0\bmod A(e_{j})$ for each edge $e_{j}$ incident to $v_{i}$,
and $0\equiv 0\bmod A(e)$ for all other edges. The incident edges are
precisely the edges in $st(v_{i})$, which have weights
$\\{c_{1},\ldots,c_{d}\\}$. Then $(0,0,\ldots,0,g_{i})\in K_{i}$ if and only
if $g_{i}\equiv 0\bmod c_{j}$ for all $j$. But by Lemma 1.3, this is
equivalent to $g_{i}\equiv 0\bmod[c_{1},\ldots,c_{d}]$. So
$m_{i}=(0,0,\ldots,[c_{1},\ldots,c_{d}])$ is a minimal element of $K_{i}$,
which means $m_{i}$ generates $K_{i}$.

Finally, since $m_{i}$ is a minimal element of of the $i-1$st flow-up class of
$S_{G_{i}}$, any pre-image $M_{i}$ in $S_{G}$ will be a minimal element of
${\mathcal{F}}_{i-1}$, by Theorem 4.1. Thus the $M_{i}$’s form a flow-up class
basis of $S_{G}$. ∎

This gives a procedure for constructing a basis $\\{M_{1},\ldots M_{n}\\}$ for
$S_{G}$. For $i>1$, $M_{i}$ has leading term $[c_{1},\ldots,c_{d}]$ where
$\\{c_{1},\ldots,c_{d}\\}$ are weights of edges incident to vertex $v_{i}$ in
$G_{i}$, and we can use the Chinese Remainder Theorem to explicitly construct
the other terms of $M_{i}$. When $i=1$, $G_{1}$ is a single vertex with no
edges. Since there are no restrictions, $m_{1}=(1)$, and it’s trivial to see
that $M_{1}=(1,\ldots,1)$ is always a spline in $S_{G}$.

|
---|---
Figure 6a | Figure 6b
|
Figure 6c | Figure 6d

---
Figure 6e

Figure 6. Basis for $K_{4}$

######  Example 4.4.

Let $G=K_{4}$ with the sequence of collapsing operations in Figures 6a through
6e.

In order to find $M_{4}$, we set $g_{1}=0$, $g_{2}=0$, $g_{3}=0$ in Figure 6a.
This gives us the follow equations.

$\displaystyle g_{4}$ $\displaystyle\equiv 0\bmod 12$ $\displaystyle g_{4}$
$\displaystyle\equiv 0\bmod 15$ $\displaystyle g_{4}$ $\displaystyle\equiv
0\bmod 8$

By Theorem 4.3, the leading term $g_{4}$ will be the LCM of the edge weights
incident to $v_{4}$, so $g_{4}=[12,15,8]=120$. This gives basis element
$M_{4}=(0,0,0,120)$.

Next let $g_{1}=0$, $g_{2}=0$ in (Figure 6c). The equations are

$\displaystyle g_{3}$ $\displaystyle\equiv 0\bmod 20$ $\displaystyle g_{3}$
$\displaystyle\equiv 0\bmod 12$

which has least solution $g_{3}=[12,20]=60$. We can let $g_{4}=0$, which gives
us a basis element $M_{3}=(0,0,60,0)$.

Now consider Figure 6e and let $g_{1}=0$. Then $g_{2}\equiv 0\bmod 12$, so
$g_{2}=12$ is minimal. We are guaranteed values for $g_{3}$ and $g_{4}$ by the
Chinese Remainder Theorem, but in this case we easily find a basis element
$M_{2}=(0,12,12,12)$.

Finally, we can always set $M_{1}=\left(1,1,1,1\right)$.

In the next section we find an alternate construction of $L(M_{i})$, in terms
of the original edge weights of $G$. This construction does not require
collapsing $G$ to the graph $G_{i}$, in terms of the original edge weights of
$G$.

##  5\. Leading Terms of Basis Elements

Let $(G,A)$ be an edge-weighted graph and let $(G^{\prime},A^{\prime})$ be the
result of a star-clique operation removing vertex $v$ from $G$. Let $w$ and
$u$ be vertices in $G$ distinct from $v$. We introduce the following notation.

  * •

$(p)$ = the GCD of the edge labels of a path $p$.

  * •

$\mathcal{P}$ = the set of paths between $w$ and $u$ in $G$.

  * •

${\mathcal{Q}}$ = the set of paths between $w$ and $u$ in $G^{\prime}$.

  * •

$[\mathcal{P}]$ = the LCM of the $(p)$’s, where $p\in\mathcal{P}$.

  * •

$[\mathcal{Q}]$ = the LCM of the $(q)$’s, where $q\in\mathcal{Q}$.

Next, we show that $[\mathcal{P}]$ is invariant under the star-clique
operation.

######  Lemma 5.1.

Let $v$ be a vertex of $G$ and let $(G^{\prime},A^{\prime})$ be the result a
star-clique operation. Let $w,u$ be vertices in $G$ distinct from $v$. Then
$[\mathcal{P}]=[\mathcal{Q}]$.

###### Proof.

We partition $\mathcal{P}$ into two sets:

  * •

$\mathcal{P}_{+}$ = paths that include $v$;

  * •

${\mathcal{P}}_{-}$ = paths not including $v$.

Let $p$ be a path in $\mathcal{P}_{-}$. Since this path doesn’t includes $v$,
it will also be a path in $G^{\prime}$, hence $p$ is in $\mathcal{Q}$. Now let
$p$ be a path in $\mathcal{P}_{+}$ with edge labels
$c_{1},c_{2},\ldots,c_{n}$. Since this $p$ includes $v$, it contains two
vertices $x$ and $y$ and two edges $e$ and $f$ adjacent to $v$, with edge
labels $c_{i}$ and $c_{i+1}$. Thus,

$(p)=(c_{1},c_{2},\ldots,c_{i},c_{i+1},\ldots,c_{n})$

However, by the star-clique construction, there will be an edge in
$G^{\prime}$ directly between $x$ and $y$ with edge label $(c_{i},c_{i+1})$.
Consequently there is a path $p^{\prime}$ in $G^{\prime}$ with

$(p^{\prime})=(c_{1},c_{2},\ldots,(c_{i},c_{i+1}),\ldots,c_{n}).$

But since $(a,(b,c))=(a,b,c)$, we have $(p)=(p^{\prime})$.

Now let $q=e_{1}\cdots e_{n}$ be a path in $\mathcal{Q}$ and

$(q)=(c_{1},c_{2},\ldots,c_{n})$

If an $e_{i}$ was not an edge in $G$, then its vertices $x$ and $y$ must be
adjacent to $v$ in $G$. Thus there are edges $e_{x}$ and $e_{y}$ in $G$ with
weights $c_{x}$ and $c_{y}$, which means $e_{i}$ in $G^{\prime}$ has weight
$c_{i}=(c_{x},c_{y})$. Let $q_{i}=e_{1}\cdots e_{i-1}e_{x}e_{y}e_{i+1}e_{n}$,
then

$(q_{i})=(c_{1},c_{2},\ldots,c_{i-1},c_{x},c_{y},c_{i+1},\ldots,c_{n})$
$=(c_{1},c_{2},\ldots,c_{i-1},(c_{x},c_{y}),c_{i+1},\ldots,c_{n})$
$=(c_{1},c_{2},\ldots,c_{i-1},c_{i},c_{i+1},\ldots,c_{n})=(q)$

Since we can do this for each such edge $e_{i}$, we see that there is a path
$q^{+}$ in $G$ with $(q^{+})=(q)$. Consequently, the GCDs used to compute
$[\mathcal{P}]$ are identical to the GCDs used to compute $[\mathcal{Q}]$, so
$[\mathcal{P}]=[\mathcal{Q}]$. ∎

We now prove that $[\mathcal{P}]$ is invariant under edge-collapse.

######  Lemma 5.2.

Let $(G^{\prime},A^{\prime})$ be the result an edge-collapse operation, and
let $w,u$ be vertices of $G$. Then $[\mathcal{P}]=[\mathcal{Q}]$.

###### Proof.

Let $d_{1},d_{2},\ldots,d_{r}$ with weights $c_{1}c_{2},\ldots,c_{r}$ be the
edges in $G$ that are collapsed to an edge $d$ with weight
$c=[c_{1},c_{2},\ldots,c_{r}]$ in $G^{\prime}$.

We can partition $\mathcal{P}$ and $\mathcal{Q}$ into two sets:

  * •

$\mathcal{P}_{1}$ = paths that include any of the $d_{i}$

  * •

$\mathcal{P}_{2}$ = paths that include none of the $d_{i}$

  * •

$\mathcal{Q}_{1}$ = paths that include $d$

  * •

$\mathcal{Q}_{2}$ = paths that don’t include $d$

Let $p\in\mathcal{P}_{2}$. Since $p$ does not include any $d_{i}$, all of its
edges are in $G^{\prime}$, so $p\in\mathcal{Q}_{2}.$ Similary, if
$p\in\mathcal{Q}_{2}$ then $p\in\mathcal{P}_{2}.$ Thus
$\mathcal{P}_{2}=\mathcal{Q}_{2}$.

Now let $p_{1}\in\mathcal{P}_{1}$ contain edges $d_{1}$, with remaining edges
$e_{1},\ldots,e_{s}$ in both $G$ and $G^{\prime}$, and edge weights
$a_{1},\ldots,a_{s}$. Clearly, for each $1<i\leq r$ there is a path
$p_{i}\in\mathcal{P}_{1}$ with edges $d_{i},e_{1},\ldots,e_{s}$. Thus we have

$\displaystyle(p_{1})$ $\displaystyle=(c_{i},a_{1},a_{2},\ldots,a_{s})$
$\displaystyle(p_{2})$ $\displaystyle=(c_{i},a_{1},a_{2},\ldots,a_{s})$
$\displaystyle\vdots$ $\displaystyle(p_{r})$
$\displaystyle=(c_{i},a_{1},a_{2},\ldots,a_{s})$

These correspond directly to the path $p^{\prime}$ in $\mathcal{Q}_{1}$ with
edges $d,e_{1},\ldots,e_{s}$ and

$(p^{\prime})=([c_{1},c_{2},\ldots,c_{r}],a_{1},a_{2},\ldots,a_{s})$

Similarly, any $p^{\prime}\in\mathcal{Q}_{1}$ corresponds to
$p_{1},\ldots,p_{r}$ in $\mathcal{P_{1}}$. Let $a=(a_{1},a_{2},\ldots a_{n})$.
By repeated applications of Lemma 1.3, we have

$\displaystyle[(p_{1}),\dots(p_{r})]$
$\displaystyle=[(c_{1},a_{1},a_{2},\ldots
a_{s}),\ldots,(c_{r},a_{1},a_{2},\ldots a_{s})]$
$\displaystyle=[(c_{1},(a_{1},a_{2},\ldots a_{s})),\ldots
a_{s})),\ldots,(c_{r},(a_{1},a_{2},\ldots a_{s}))]$
$\displaystyle=[(c_{1},a),\ldots,(c_{r},a)]$
$\displaystyle=[(a,[c_{1},\ldots,c_{r})]$ $\displaystyle=(p^{\prime})$

Let $\mathcal{Q}_{1}=\\{x_{1},\dots x_{m}\\}$,
$\mathcal{Q}_{2}=\\{y_{1},\dots,y_{k}\\}$ and $y=[y_{1},\dots y_{k}].$ Then
each $x_{i}\in\mathcal{Q_{1}}$ corresponds to $r$ different paths
$x_{ij}\in\mathcal{P}_{1}$, and by above,
each$(x_{i})=[(x_{i1}),\dots(x_{ir})]$.

By repeated applications of Lemma 1.3 we have

$\displaystyle[\mathcal{Q}]$
$\displaystyle=[(x_{1}),\dots,(x_{m}),(y_{1}),\dots,(y_{k})]$
$\displaystyle=[(x_{1}),\dots,(x_{m}),[(y_{1}),\dots,(y_{k})]$
$\displaystyle=[(x_{1}),\dots,(x_{m}),y]$
$\displaystyle=[(x_{11}),\dots,(x_{1r})],\dots,[(x_{m1}),\dots,(x_{mr})],y]$
$\displaystyle=[(x_{11}),\dots,(x_{1r})],\dots,[(x_{m1}),\dots,(x_{mr})],[(x_{1}),\dots,(x_{m}),(y_{1}),\dots,(y_{k})]]$
$\displaystyle=[(x_{11}),\dots,(x_{1r}),\dots,(x_{m1}),\dots(x_{mr}),(x_{1}),\dots,(x_{m}),(y_{1}),\dots,(y_{k})]$
$\displaystyle=[\mathcal{P}]$

∎

We have the following important corollary.

######  Corollary 5.3.

Let $w,u$ be two vertices in both $G$ and $G^{\prime}$. The LCM of the GCD of
all paths from $w$ to $u$ is invariant under collapsing operations taking $G$
to $G^{\prime}$.

Using this result, we can construct leading terms of basis elements in terms
of LCMs and GCDs of the edge weights of $G$.

######  Theorem 5.4.

Let $M_{1},M_{2},\ldots M_{n}$ be a flow up class basis for $S_{G}$ and let
$\mathcal{P}_{ij}$ denote the set of paths from $v_{i}$ to $v_{j}$ in $S_{G}$
where $i<j$. Then $L(M_{1})=1$, and for $i>1$, and
$L(M_{i})=[[\mathcal{P}_{i1}],[\mathcal{P}_{i2}],\ldots,[\mathcal{P}_{i,i-1}]]$.

###### Proof.

$M_{1}=(1,\ldots,1)$ is minimal in ${\mathcal{F}}_{0}$ since 1 is minimal in
$\mathbb{N}$. We know from Theorem that $L(M_{i})=L(m_{i})$ where
$m_{i}=(0,0,\ldots,[c_{1},\ldots,c_{r}])$ is a minimal element of $K_{i}$, and
$c_{j}$ is the edge label of the edge between $v_{i}$ and $v_{j}$ , for all
$j\leq r\leq i$. (If necessary we can temporarily reorder the $v_{j}$’s
incident to $v_{i}$ so that they are vertices $v_{1},\ldots,v_{r}$.) For each
$j$, the edge $e_{j}$ with label $c_{j}$ is the only path form $v_{i}$ to
$v_{j}$ in $G_{i}$. By Lemma 1.3, this means that $c_{j}=[\mathcal{P}_{ij}]$.
Then
$L(M_{i})=[c_{1},\ldots,c_{r}]=[[\mathcal{P}_{i1}],[\mathcal{P}_{i2}],\ldots,[\mathcal{P}_{i,r}]]$.
If $r=i-1$, we are done. If $r<i$, let $p$ be a path from $v_{i}$ to $v_{k}$
where $r<k\leq i$. This path necessarily passes through some $v_{j}$ for some
$j\leq r$, so $d_{j}$ is one of the edges of $p$. Let $b$ be the GCD of the
edge weights of the remaining edges of $p$. Then $(p)=(c_{j},b)$. Since $(p)$
divides $c_{j}$, we have $[c_{j}]=[c_{j},(p)]$ and thus
$[c_{1},\ldots,c_{r}]=[c_{1},\ldots,c_{r},(p)]$. Since we can do this for any
path from $v_{i}$ to $v_{k}$, we get that
$[c_{1},\ldots,c_{r}]=[c_{1},\ldots,c_{r},[P_{ik}]]$ and by varying $k$ we get
that
$L(M_{i})=[c_{1},\ldots,c_{r},[\mathcal{P}_{i,r}],\ldots,[\mathcal{P}_{i,i-1}]]=[[\mathcal{P}_{i1}],[\mathcal{P}_{i2}],\ldots,[\mathcal{P}_{i,i-1}]]$.
∎

We see from this proof that we don’t need to check all paths from $v_{i}$ to
all vertices $v_{j}$, just paths from $v_{i}$ to $v_{j}$ where all interior
vertices have subscripts bigger than $i$. An easy way to identify these paths
is to label all vertices $v_{1}$ to $v_{i-1}$ with 0’s, and use only paths
from $v_{i}$ to the first 0 you run into.

$g_{4}$$g_{3}$$g_{2}$$g_{1}$$6$$20$$6$$8$$15$$6$
---
Figure 7. Edge-weighted $K_{4}$ Figure 8a |
---|---
Figure 8b |
Figure 8c |
Figure 8. Finding Leading Terms Using Theorem 5.4

######  Example 5.5.

We will use Theorem 5.4 to compute the leading terms of a flow class basis for
$S_{G}$, the $K_{4}$ graph of Figure 7.

  1. (1)

First, we have $L(M_{1})=1$.

  2. (2)

In order to find $L(M_{2})$ we set $g_{1}=0$ as in Figure 8a. Then $L(M_{2})$
is the LCM of the GCD of all paths from $g_{2}$ to any vertex labeled $0$.
These paths are:

     * •

$g_{2}g_{1}$, which has edge weight $6$,

     * •

$g_{2}g_{4}g_{1}$, which has edge weights $12,15$

     * •

$g_{2}g_{3}g_{1}$, which has edge weights $20,6$

     * •

$g_{2}g_{4}g_{3}g_{1}$, which has edge weights $15,8,6$

     * •

$g_{3}g_{4}g_{1}$, which has edge weights $20,8,12$

Thus $L(M_{2})=[6,(12,15),(20,6),(15,8,6),(20,8,12)]=[6,3,2,1,4]=12$.

  3. (3)

For $L(M_{3})$, we set both $g_{1}$, $g_{2}$ equal $0$ as in Figure 8b. The
paths from $g_{3}$ to any vertex labeled $0$ are:

     * •

$g_{3}g_{2}$, with edge weight $20$,

     * •

$g_{3}g_{1}$, with edge weight $6$,

     * •

$g_{3}g_{4}g_{1}$, with edge weights $8,12$

     * •

$g_{3}g_{4}g_{2}$, with edge weights $8,15$

Thus $L(M_{3})=[20,6,(8,12),(8,15)]=[20,6,4,1]=60$.

  4. (4)

Finally to compute $L(M_{4})$ we set $g_{1}$, $g_{2}$, $g_{3}$ equal to $0$,
as in Figure 8c, and find the paths from $g_{4}$ to $0$:

     * •

$g_{4}g_{1}$, with weight $12$,

     * •

$g_{4}g_{2}$, with weight $15$,

     * •

$g_{4}g_{3}$, with weight $8$,

Then $L(M_{4})=[12,15,8]=120$.

Thus the leading terms of $M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$ are $1$, $12$,
$60$, and $120$ respectively. These agree with the leading terms found in
Example 4.4, illustrating that Theorems 4.3 and 5.4 provide two different ways
to contruct the same basis for $S_{G}$.

## References

  * [1] Alfeld, P., Schumaker, L.L., Sirvent, M., On dimension and existence of local bases for multivariate spline spaces. J. Approx. Theory 70, (1992).
  * [2] L. Billera, L. Rose, A dimension series for multivariate splines, Discrete Computational Geometry, 6 (2) (1991), 107–128.
  * [3] L. Billera. The algebra of continuous piecewise polynomials, Advances in Math. 76 (1988), 170–183.
  * [4] L. Billera, L. Rose, “Modules of Piecewise Polynomials and their Freeness,” Mathematische Zeitschrift 209 (1992).
  * [5] L. Billera, Homology of smooth splines: generic triangulations and a conjecture of Strang, Transactions of the American Mathematical Society, 310 (1) (1998), 325–340.
  * [6] S. Gilbert, J. Tymoczko, S. Viel, Generalized Splines on Arbitrary Graphs, Pacific Journal of Mathematics, 281 (2) (2016), 333–364.
  * [7] R. Haas, Module and vector space bases for spline spaces, Journal of Approximation Theory 65 (1) (1991), 73–89.
  * [8] M. Handschy, J. Melnick, S. Reinders, Integer Generalized Splines on Cycles. arXiv:1409.1481 (2014).
  * [9] J. Liu, L. Rose, K. Sangam, J. Suzuki and E. Zhang, Modules Bases for Integer Splines , submitted.
  * [10] L. Rose,Combinatorial and topological invariants of modules of piecewise polynomials, Advances in Mathematics, 116 (1), (1995) 34–45.
  * [11] L. Rose, Graphs, syzygies and multivariate splines, Discrete and Computational Geomeomtry, 32 (4) (2004), 623–637.
  * [12] L. Rose, Module Bases for Multivariate Splines, Journal of Approx. Theory 86 No. 1, (1996).
  * [13] J. Tymoczko, Splines in geometry and topology, Computer Aided Geometric Design, 45 (2016), 32–47.


# Dual Quaternion Matrices in Multi-Agent Formation Control

Liqun Qi111Department of Mathematics, School of Science, Hangzhou Dianzi
University, Hangzhou 310018 China (maqilq@polyu.edu.hk). Xiangke Wang College
of Mechatronics and Automation, National University of Defence Technology,
Changsha, 410073, China; (xkwang@nudt.edu.cn).  and Ziyan Luo222Corresponding
author, Department of Mathematics, Beijing Jiaotong University, Beijing
100044, China. (zyluo@bjtu.edu.cn). This author’s work was supported by
Beijing Natural Science Foundation (Grant No. Z190002).

###### Abstract

Three kinds of dual quaternion matrices associated with the mutual visibility
graph, namely the relative configuration adjacency matrix, the logarithm
adjacency matrix and the relative twist adjacency matrix, play important roles
in multi-agent formation control. In this paper, we study their properties and
applications. We show that the relative configuration adjacency matrix and the
logarithm adjacency matrix are both Hermitian matrices, and thus have very
nice spectral properties. We introduce dual quaternion Laplacian matrices, and
prove a Gershgorin-type theorem for square dual quaternion Hermitian matrices,
for studying properties of dual quaternion Laplacian matrices. The role of the
dual quaternion Laplacian matrices in formation control is discussed.

Key words. Unit dual quaternions, formation control, dual quaternion matrices,
dual quaternion Hermitian matrices, eigenvalues.

##  1 Introduction

In 1873, Clifford [6] introduced dual quaternions. Dual quaternions now have
wide applications in robotics, 3D motion modelling and control, and computer
graphics [2, 3, 4, 5, 7, 8, 9, 10, 13, 17].

In 2011, Wang [16] proposed the study of dual quaternion matrices in his
research on formation control in 3D space. In [18], Wang and his co-authors
studied the application of dual quaternion matrices in the multiple rigid-
bodies rendezvous problem [1], and proposed three dual quaternion matrices:
the relative configuration adjacency matrix, the logarithm adjacency matrix
and the relative twist adjacency matrix. In [15], Qi and Luo studied the
spectral properties of dual quaternion matrices. If a dual number is a right
eigenvalue of a square dual quatrernion matrix, then it is also a left
eigenvalue of that matrix. They call such a right eigenvalue an eigenvalue.
They showed that an $n\times n$ dual quaternion Hermitian matrix has exactly
$n$ eigenvalues and no other right eigenvalues. Such a matrix is positive
semi-definite or positive definite if and only if its eigenvalues are all
nonnegative or positive, respectively, in the sense of [14]. Based upon this,
a singular value decomposition theorem for general dual quaternion matrices
was established. Dual quaternion matrices were also studied in [12].

In this paper, we show that the relative configuration adjacency matrix and
the logarithm adjacency matrix are dual quaternion Hermitian matrices, propose
a dual quaternion Laplacian matrix theory for the multi-robot rendezvous
problem, and study the properties and application in formation control, of
dual quaternion Laplacian matrices.

The rest of this paper is distributed as follows. Preliminary knowledge on
dual numbers, quaternions, dual quaternions and dual quaternion matrices, is
given in Section 2. In Section 3, we show that the relative configuration
adjacency matrix and the logarithm adjacency matrix are dual quaternion
Hermitian matrices, and the sum of the logarithms of relative configurations
over any cycle vanishes to zero. Dual quaternion Laplacian matrices were
introduced in Section 4. A Gershgorin-type theorem for dual quaternion
Hermitian matrices was given there for the discussion of properties of dual
quaternion Laplacian matrices. The role of the dual quaternion Laplacian
matrices in formation control is discussed in Section 5.

We denote scalars, vectors and matrices by small letters, bold small letters
and capital letters, respectively. Dual numbers and dual quaternions are
distinguished by a hat symbol.

##  2 Preliminaries

###  2.1 Dual Numbers

Denote $\mathbb{R}$ and $\hat{\mathbb{R}}$ as the set of the real numbers, and
the set of the dual numbers, respectively. Following the literature such as
[17], we use the hat symbol to denote dual numbers and dual quaternions. A
dual number $\hat{q}$ has the form $\hat{q}=q+q_{d}\epsilon$, where $q$ and
$q_{d}$ are real numbers, and $\epsilon$ is the infinitesimal unit, satisfying
$\epsilon^{2}=0$. We call $q$ the standard part of $\hat{q}$, and $q_{d}$ the
dual part or the infinitesimal part of $\hat{q}$. The infinitesimal unit
$\epsilon$ is commutative in multiplication with real numbers, complex numbers
and quaternion numbers. The dual numbers form a commutative algebra of
dimension two over the reals. If $q\not=0$, we say that $\hat{q}$ is
appreciable, otherwise, we say that $\hat{q}$ is infinitesimal. Note that a
real number is a dual number with a zero dual part. Then the dual zero is
still $0$, and the dual identity is still $1$.

In [14], a total order was introduced for dual numbers. Given two dual numbers
$\hat{p},\hat{q}\in\hat{\mathbb{R}}$, $\hat{p}=p+p_{d}\epsilon$,
$\hat{q}=q+q_{d}\epsilon$, where $p$, $p_{d}$, $q$ and $q_{d}$ are real
numbers, we say that $\hat{p}\leq\hat{q}$, if either $p<q$, or $p=q$ and
$p_{d}\leq q_{d}$. In particular, we say that $\hat{p}$ is positive,
nonnegative, nonpositive or negative, if $\hat{p}>0$, $\hat{p}\geq 0$,
$\hat{p}\leq 0$ or $\hat{p}<0$, respectively.

###  2.2 Quaternions

We adopt the notation $\mathbb{Q}$ to denote the set of the quaternions. A
quaternion $q$ has the form
$q=q_{0}+q_{1}\mathbf{i}+q_{2}\mathbf{j}+q_{3}\mathbf{k},$ where
$q_{0},q_{1},q_{2}$ and $q_{3}$ are real numbers, $\mathbf{i},\mathbf{j}$ and
$\mathbf{k}$ are three imaginary units of quaternions, satisfying

$\mathbf{i}^{2}=\mathbf{j}^{2}=\mathbf{k}^{2}=\mathbf{i}\mathbf{j}\mathbf{k}=-1,~{}~{}\mathbf{i}\mathbf{j}=-\mathbf{j}\mathbf{i}=\mathbf{k},~{}~{}\mathbf{j}\mathbf{k}=-\mathbf{k}\mathbf{j}=\mathbf{i},~{}~{}\mathbf{k}\mathbf{i}=-\mathbf{i}\mathbf{k}=\mathbf{j}.$

The real part of $q$ is Re$(q)=q_{0}$. The imaginary part of $q$ is
Im$(q)=q_{1}\mathbf{i}+q_{2}\mathbf{j}+q_{3}\mathbf{k}$. The multiplication of
quaternions satisfies the distribution law, but is noncommutative.

The conjugate of $q=q_{0}+q_{1}\mathbf{i}+q_{2}\mathbf{j}+q_{3}\mathbf{k}$ is
$q^{*}:=q_{0}-q_{1}\mathbf{i}-q_{2}\mathbf{j}-q_{3}\mathbf{k}.$ The magnitude
of $q$ is $|q|=\sqrt{q_{0}^{2}+q_{1}^{2}+q_{2}^{2}+q_{3}^{2}}.$ It follows
that the inverse of a nonzero quaternion $q$ is given by
$q^{-1}={q^{*}/|q|^{2}}.$ For any two quaternions $p$ and $q$, we have
$(pq)^{*}=q^{*}p^{*}$.

A quaternion is called imaginary if its real part is zero. If $q$ is
imaginary, then $q^{*}=-q$. In the engineering literature [17], it is called a
vector quaternion. Various 3D vectors, such as position vectors, displacement
vectors, linear velocity vectors, and angular velocity vectors, can be
represented as imaginary quaternions. As 3D vectors have cross product,
imaginary quaternions can also have cross products. That is, the cross product
of two imaginary quaternions is an imaginary quaterion, with its imaginary
part is the cross product of the two original imaginary quaternions.

If $|q|=1$, then $q$ is called a unit quaternion, or a rotation quaternion. A
spatial rotation around a fixed point of $\theta$ radians about a unit axis
$(x_{1},x_{2},x_{3})$ that denotes the Euler axis is given by the unit
quaternion
$q=(\cos(\theta/2),x_{1}\sin(\theta/2),x_{2}\sin(\theta/2),x_{3}\sin(\theta/2))$,
i.e.,

$q=\cos(\theta/2)+x_{1}\sin(\theta/2)\mathbf{i}+x_{2}\sin(\theta/2)\mathbf{j}+x_{3}\sin(\theta/2)\mathbf{k}=e^{{\theta\over
2}x}.$ (1)

where the unit axis $x$ is an imaginary unit quaternion
$x=x_{1}\mathbf{i}+x_{2}\mathbf{j}+x_{3}\mathbf{k}$. Thus, we may also write

$\ln q={\theta\over 2}x.$ (2)

Note that a unit quaternion $q$ is always invertible and $q^{-1}=q^{*}$.
Furthermore, since in general it is possible that $pq\not=qp$, it is also
possible $\ln pq\not=\ln p+\ln q$.

Two quaternions $p$ and $q$ are said to be similar if there is a nonzero
quaternion $u$ such that $p=u^{-1}qu$. We denote $p\sim q$. It is easy to
check that $\sim$ is an equivalence relation on the quaternions. Denote by
$[q]$ the equivalence class containing $q$. Then $[q]$ is a singleton if and
only if $q$ is a real number.

Denote the collection of $n$-dimensional quaternion vectors by
${\mathbb{Q}}^{n}$. For
$\mathbf{x}=(x_{1},x_{2},\cdots,x_{n})^{\top},\mathbf{y}=(y_{1},y_{2},\cdots,y_{n})^{\top}\in{\mathbb{Q}}^{n}$,
define $\mathbf{x}^{*}\mathbf{y}=\sum_{i=1}^{n}x_{i}^{*}y_{i}$, where
$\mathbf{x}^{*}=(x_{1}^{*},x_{2}^{*},\cdots,x_{n}^{*})$ is the conjugate
transpose of $\mathbf{x}$.

###  2.3 Dual Quaternions

Denote the set of dual quaternions by $\hat{\mathbb{Q}}$. A dual quaternion
$\hat{q}\in\hat{\mathbb{Q}}$ has the form

$\hat{q}=q+q_{d}\epsilon,$ (3)

where $q,q_{d}\in\mathbb{Q}$ are the standard part and the dual part of
$\hat{q}$, respectively. If $q\not=0$, then we say that $\hat{q}$ is
appreciable. If $q$ and $q_{d}$ are imaginary quaternions, then $\hat{q}$ is
called an imaginary dual quaternion. Here, the infinitesimal unit $\epsilon$
is commutative with each of those three imaginary units of quaternions. Thus,
$q_{d}\epsilon=\epsilon q_{d}$ for any $q_{d}\in\mathbb{Q}$.

The conjugate of $\hat{q}$ is

$\hat{q}^{*}=q^{*}+q_{d}^{*}\epsilon.$ (4)

By this, if $\hat{q}=\hat{q}^{*}$, then $\hat{q}$ is a dual number. If
$\hat{q}$ is imaginary, then $\hat{q}^{*}=-\hat{q}$.

The magnitude of $\hat{q}$ was defined in [14] as

$|\hat{q}|:=\left\\{\begin{aligned} |q|+{(qq_{d}^{*}+q_{d}q^{*})\over
2|q|}\epsilon,&\ {\rm if}\ q\not=0,\\\ |q_{d}|\epsilon,&\ {\rm
otherwise},\end{aligned}\right.$ (5)

which is a dual number.

Suppose that we have two dual quaternions $\hat{p}=p+p_{d}\epsilon$ and
$\hat{q}=q+q_{d}\epsilon$, their addition and multiplications are defined as

$\hat{p}+\hat{q}=\left(p+q\right)+\left(p_{d}+q_{d}\right)\epsilon$

and

$\hat{p}\hat{q}=pq+\left(pq_{d}+p_{d}q\right)\epsilon.$

See [9, 10]. Note that under these arithmetic rules, a dual number is
commutative with a dual quaternion or a dual quaternion vector.

A dual quaternion $\hat{q}$ is called invertible if there exists a quaternion
$\hat{p}$ such that $\hat{p}\hat{q}=\hat{q}\hat{p}=1$. We can derive that
$\hat{q}$ is invertible if and only if $\hat{q}$ is appreciable. In this case,
we have

$\hat{q}^{-1}=q^{-1}-q^{-1}q_{d}q^{-1}\epsilon.$

If $|\hat{q}|=1$, then $\hat{q}$ is called a unit dual quaternion. A unit dual
quaternion $\hat{q}$ is always invertible and we have
${\hat{q}}^{-1}={\hat{q}}^{*}$. The 3D motion of a rigid body can be
represented by a unit dual quaternion. We have

$\hat{q}\hat{q}^{*}=(q+q_{d}\epsilon)(q^{*}+q_{d}^{*}\epsilon)=qq^{*}+(qq_{d}^{*}+q_{d}q^{*})\epsilon=\hat{q}^{*}\hat{q}.$

Thus, $\hat{q}$ is a unit dual quaternion if and only if $q$ is a unit
quaternion, and

$qq_{d}^{*}+q_{d}q^{*}=q^{*}q_{d}+q_{d}^{*}q=0.$ (6)

For example, $\hat{q}=\mathbf{i}+\mathbf{j}\epsilon$ is a unit dual
quaternion. Suppose that there is a rotation $q\in{\mathbb{Q}}$ succeeded by a
translation $p^{b}\in{\mathbb{Q}}$, where $p^{b}$ is an imaginary quaternion.
Here, following [17], we use superscripts $b$ and $s$ to represent the
relation of the rigid body motion with respect to the body frame attached to
the rigid body and the spatial frame which is relative to a fixed coordinate
frame. Then the whole transformation can be represented using unit dual
quaternion $\hat{q}=q+q_{d}\epsilon$, where $q_{d}={1\over 2}qp^{b}$. Note
that we have

$qq_{d}^{*}+q_{d}q^{*}={1\over
2}\left[q(p^{b})^{*}q^{*}+qp^{b}q^{*}\right]={1\over
2}q\left[(p^{b})^{*}+p^{b}\right]q^{*}=0.$

Thus, a transformation of a rigid body can be represented by a unit dual
quaternion

$\hat{q}=q+{\epsilon\over 2}qp^{b},$ (7)

where $q$ is a unit quaternion to represent the rotation, and $p^{b}$ is the
imaginary quaternion to represent the translation or the position. Here, unit
quaternion $q$ serves as a rotation, taking coordinates $r^{o}$ of a point in
the original frame to coordinates $r^{n}$ in the new frame by

$r^{n}=q^{*}r^{o}q,$ (8)

where $r^{o}$ and $r^{n}$ are two imaginary quaternions, their superscripts
$o$ and $n$ represent “original” and “new” respectively. On the other hand,
every attitude of a rigid body which is free to rotate relative to a fixed
frame can be identified by a unique unit quaternion $q$. Thus, in (7), $q$ is
the attitude of the rigid body, while $\hat{q}$ represents the transformation.

The configuration change rate of a rigid body can be expressed by

$\dot{\hat{q}}\equiv{d{\hat{q}}\over dt}={1\over 2}\hat{q}\hat{\xi}^{b},$ (9)

where the unit dual quaternion $\hat{q}$ is the configuration of that rigid
body, expressed by (7), and the imaginary dual quaternion

$\hat{\xi}^{b}=\omega^{b}+\epsilon(\dot{p}^{b}+\omega^{b}\times p^{b})$ (10)

is the twist of rigid body, with angular velocity $\omega^{b}$ and linear
velocity $\dot{p}^{b}\equiv{dp^{b}\over dt}$.

Combining (7) with (2), we have

$\ln\hat{q}={1\over 2}(\theta x+\epsilon p^{b}).$ (11)

Given an imaginary quaternion $v$ and a unit quaternion $q$, the adjoint
transformation is defined as

${\rm Ad}_{q}v=qvq^{*}.$ (12)

Similarly, given an imaginary dual quaternion $\hat{v}$ and a unit dual
quaternion $\hat{q}$, the adjoint transformation of the unit dual quaternion
$\hat{q}$ is defined as

${\rm Ad}_{\hat{q}}\hat{v}=\hat{q}\hat{v}\hat{q}^{*}.$ (13)

A unit dual quaternion $\hat{q}$ serves as both a specification of the
configuration of a rigid body and a transformation taking the coordinates of a
point from one frame to another via rotation and translation. In (7), if
$\hat{q}$ is the configuration of the rigid body, then $q$ and $p^{b}$ are the
attitude of and position of the rigid body respectively. They have the
following property:

Property A: If the configurations of rigid bodies $i$ and $j$ are
$\hat{q}_{i}$ and $\hat{q}_{j}$, and the transformation (relative
configuration) from rigid body $i$ to $j$ is $\hat{q}_{ij}$, then
$\hat{q}_{j}=\hat{q}_{i}\hat{q}_{ij}$.

Consider two unit dual quaternions $\hat{q}$ and $\hat{q}_{t}$ defined as in
(7). The left-invariant error from $\hat{q}$ to $\hat{q}_{t}$ is

$\hat{q}_{e}=\hat{q}_{t}^{*}\hat{q}=q_{e}+{\epsilon\over 2}q_{e}p_{e}^{b},$
(14)

where $q_{e}=q_{t}^{*}q$ and $p_{e}^{b}=p^{b}-{\rm Ad}_{q_{e}^{*}}p_{t}^{b}$.

Two dual quaternions $\hat{p}$ and $\hat{q}$ are said to be similar if there
is an appreciable quaternion $\hat{u}$ such that
$\hat{p}=\hat{u}^{-1}\hat{q}\hat{u}$. We denote $\hat{p}\sim\hat{q}$. Then
$\sim$ is an equivalence relation on the dual quaternions. Denote by
$[\hat{q}]$ the equivalence class containing $\hat{q}$. Then $[\hat{q}]$ is a
singleton if and only if $\hat{q}$ is a dual number.

Denote the collection of $n$-dimensional dual quaternion vectors by
${\hat{\mathbb{Q}}}^{n}$.

For $\hat{\mathbf{x}}=(\hat{x}_{1},\hat{x}_{2},\cdots,\hat{x}_{n})^{\top}$,
$\hat{\mathbf{y}}=(\hat{y}_{1},\hat{y}_{2},\cdots,\hat{y}_{n})^{\top}\in{\hat{\mathbb{Q}}}^{n}$,
define
$\hat{\mathbf{x}}^{*}\hat{\mathbf{y}}=\sum_{i=1}^{n}\hat{x}_{i}^{*}\hat{y}_{i}$,
where
$\hat{\mathbf{x}}^{*}=(\hat{x}_{1}^{*},\hat{x}_{2}^{*},\cdots,\hat{x}_{n}^{*})$
is the conjugate transpose of $\hat{\mathbf{x}}$. We say $\hat{\mathbf{x}}$ is
appreciable if at least one of its component is appreciable. We also say that
$\hat{\mathbf{x}}$ and $\hat{\mathbf{y}}$ are orthogonal to each other if
$\hat{\mathbf{x}}^{*}\hat{\mathbf{y}}=0$. By [14], for any
$\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$,
$\hat{\mathbf{x}}^{*}\hat{\mathbf{x}}$ is a nonnegative dual number, and if
$\hat{\mathbf{x}}$ is appreciable, $\hat{\mathbf{x}}^{*}\hat{\mathbf{x}}$ is a
positive dual number.

###  2.4 Dual Quaternion Matrices

Denote the collections of $m\times n$ dual quaternion matrices by
${\hat{\mathbb{Q}}}^{m\times n}$. Then $\hat{A}\in{\hat{\mathbb{Q}}}^{m\times
n}$ can be written as

$\hat{A}=A+A_{d}\epsilon,$

where $A,A_{d}\in{\mathbb{Q}}^{m\times n}$ are the standard part and the
infinitesimal part of $\hat{A}$, respectively.

The conjugate transpose of $\hat{A}$ is

$\hat{A}^{*}=A^{*}+A_{d}^{*}\epsilon.$

A square dual quaternion matrix $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ is
called normal if $\hat{A}^{*}\hat{A}=\hat{A}\hat{A}^{*}$, Hermitian if
$\hat{A}^{*}=\hat{A}$; unitary if $\hat{A}^{*}\hat{A}=I_{n}$, where $I_{n}$ is
the $n\times n$ identity matrix; and invertible (nonsingular) if
$\hat{A}\hat{B}=\hat{B}\hat{A}=I_{n}$ for some
$\hat{B}\in{\hat{\mathbb{Q}}}^{n\times n}$. Indeed, if
$\hat{A}=A+A_{d}\epsilon$ and $\hat{B}=B+B_{d}\epsilon$ satisfy
$\hat{A}\hat{B}=I_{n}$, then $B=A^{-1}$ and $B_{d}=-A^{-1}A_{d}A^{-1}$. This
further implies $\hat{B}\hat{A}=I_{n}$. Thus, the inverse of $\hat{A}$ is
unique, denoted by $\hat{A}^{-1}$, and we have
$\hat{A}^{-1}=A^{-1}-A^{-1}A_{d}A^{-1}\epsilon$.

We have $(\hat{A}\hat{B})^{-1}=\hat{B}^{-1}\hat{A}^{-1}$ if $\hat{A}$ and
$\hat{B}$ are invertible, and
$\left(\hat{A}^{*}\right)^{-1}=\left(\hat{A}^{-1}\right)^{*}$ if $\hat{A}$ is
invertible.

Suppose that $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ is an Hermitian
matrix. For any $\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$, we have
$(\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}})^{*}=\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}}.$
Thus, $\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}}$ is a dual number. A dual
quaternion Hermitian matrix $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ is
called positive semi-definite if for any
$\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$,
$\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}}\geq 0$; $\hat{A}$ is called
positive definite if for any $\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$ with
$\hat{\mathbf{x}}$ being appreciable, we have
$\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}}>0$ and is appreciable. A square
dual quaternion matrix $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ is unitary
if and only if its column (row) vectors form an orthonormal basis of
${\hat{\mathbb{Q}}}^{n}$. Then, $\hat{A}$ is a dual quaternion Hermitian
matrix if and only if $A$ and $A_{d}$ are two quaternion Hermitian matrices.

Suppose that $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$. If there are
$\hat{\lambda}\in\hat{\mathbb{Q}}$,
$\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$, where $\hat{\mathbf{x}}$ is
appreciable, such that

$\hat{A}\hat{\mathbf{x}}=\hat{\mathbf{x}}\hat{\lambda},$ (15)

then we say that $\hat{\lambda}$ is a right eigenvalue of $\hat{A}$, with
$\hat{\mathbf{x}}$ as an associated right eigenvector. If there are
$\hat{\lambda}\in\hat{\mathbb{Q}}$,
$\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$, where $\hat{\mathbf{x}}$ is
appreciable, such that

$\hat{A}\hat{\mathbf{x}}=\hat{\lambda}\hat{\mathbf{x}},$

then we say that $\hat{\lambda}$ is a left eigenvalue of $\hat{A}$, with
$\hat{\mathbf{x}}$ as an associated left eigenvector. If $\hat{\lambda}$ is a
dual number and a right eigenvalue of $\hat{A}$, then it is also a left
eigenvalue of $\hat{A}$, as a dual number is commutative with a dual
quaternion vector. In this case, we say that it is an eigenvalue of $\hat{A}$,
with $\hat{\mathbf{x}}$ as an associated eigenvector.

The following theorems are proved in [15].

######  Theorem 2.1.

Suppose that $\hat{\lambda}=\lambda+\lambda_{d}\epsilon\in\hat{\mathbb{Q}}$ is
a right eigenvalue of $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$, with
associated right eigenvector
$\hat{\mathbf{x}}=\mathbf{x}+\mathbf{x}_{d}\epsilon\in{\hat{\mathbb{Q}}}^{n}$.
Then

$\hat{\lambda}={\hat{\mathbf{x}}^{*}\hat{A}\hat{\mathbf{x}}\over\hat{\mathbf{x}}^{*}\hat{\mathbf{x}}},$
(16)

$\lambda$ is a right eigenvalue of the quaternion matrix $A$ with a right
eigenvector $\mathbf{x}$, i.e., $\mathbf{x}\not=\mathbf{0}$ and

$A\mathbf{x}=\mathbf{x}\lambda.$ (17)

We also have

$\lambda={\mathbf{x}^{*}A\mathbf{x}\over\mathbf{x}^{*}\mathbf{x}}.$ (18)

######  Theorem 2.2.

A right eigenvalue $\hat{\lambda}$ of an Hermitian matrix
$\hat{A}=A+A_{d}\epsilon\in{\hat{\mathbb{Q}}}^{n\times n}$ must be a dual
number, hence an eigenvalue of $\hat{A}$, and its standard part $\lambda$ is a
right eigenvalue of the quaternion Hermitian matrix $A$. Furthermore, assume
that $\hat{\lambda}=\lambda+\lambda_{d}\epsilon$,
$\hat{\mathbf{x}}=\mathbf{x}+\mathbf{x}_{d}\epsilon\in{\hat{\mathbb{Q}}}^{n}$
is an eigenvector of $\hat{A}$, associate with the eigenvalue $\hat{\lambda}$,
where $\mathbf{x},\mathbf{x}_{d}\in{\mathbb{Q}}^{n}$. Then we have

$\lambda_{d}={\mathbf{x}^{*}A_{d}\mathbf{x}\over\mathbf{x}^{*}\mathbf{x}}.$
(19)

A dual quaternion Hermitian matrix has at most $n$ dual number eigenvalues and
no other right eigenvalues.

An eigenvalue of a positive semi-definite Hermitian matrix
$\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ must be a nonnegative dual number.
In that case, $A$ must be positive semi-definite. An eigenvalue of a positive
definite Hermitian matrix $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ must be
an appreciable positive dual number. In that case, $A$ must be positive
definite.

######  Theorem 2.3.

Suppose that $\hat{A}=A+A_{d}\epsilon\in{\hat{\mathbb{Q}}}^{n\times n}$ is an
Hermitian matrix. Then there are unitary matrix
$\hat{U}\in{\hat{\mathbb{Q}}}^{n\times n}$ and a diagonal matrix
$\hat{\Sigma}\in{\hat{\mathbb{R}}}^{n\times n}$ such that
$\hat{\Sigma}=\hat{U}^{*}\hat{A}\hat{U}$, where

$\hat{\Sigma}:={\rm
diag}\left(\lambda_{1}+\lambda_{1,1}\epsilon,\cdots,\lambda_{1}+\lambda_{1,k_{1}}\epsilon,\lambda_{2}+\lambda_{2,1}\epsilon,\cdots,\lambda_{r}+\lambda_{r,k_{r}}\epsilon\right),$
(20)

with the diagonal entries of $\hat{\Sigma}$ being $n$ eigenvalues of
$\hat{A}$,

$\hat{A}\hat{\mathbf{u}}_{i,j}=\hat{\mathbf{u}}_{i,j}(\lambda_{i}+\lambda_{i,j}\epsilon),$
(21)

for $j=1,\cdots,k_{i}$ and $i=1,\cdots,r$,
$\hat{U}=(\hat{\mathbf{u}}_{1,1},\cdots,\hat{\mathbf{u}}_{1,k_{1}},\cdots,\hat{\mathbf{u}}_{r,k_{r}})$,
$\lambda_{1}>\lambda_{2}>\cdots>\lambda_{r}$ are real numbers, $\lambda_{i}$
is a $k_{i}$-multiple right eigenvalue of $A$,
$\lambda_{i,1}\geq\lambda_{i,2}\geq\cdots\geq\lambda_{i,k_{i}}$ are also real
numbers, $\sum_{i=1}^{r}k_{i}=n$. Counting possible multiplicities
$\lambda_{i,j}$, the form $\hat{\Sigma}$ is unique.

######  Theorem 2.4.

Suppose that $\hat{A}\in{\hat{\mathbb{Q}}}^{n\times n}$ is Hermitian. Then
$\hat{A}$ has exactly $n$ eigenvalues, which are all dual numbers. There are
also $n$ eigenvectors, associated with these $n$ eigenvalues. The Hermitian
matrix $\hat{A}$ is positive semi-definite or definite if and only if all of
these eigenvalues are nonnegative, or positive and appreciable, respectively.

##  3 Graph Model of Multi-Agent Formation Control

Following [11, 18], we model the rigid bodies in the multi-agent formation
control by an undirected graph. We assume that the rigid-bodies are omni-
directional, i.e., rigid-body $i$ can sense rigid body $j$ if and only if
rigid-body $j$ can sense rigid body $i$. Then multiple rigid-bodies are
modelled by an undirected graph $G=(V,E)$, called the mutual visibility graph.
Here, the vertex set $V$ is the set of rigid bodies. Edge $(i,j)\in E$ if
rigid-bodies $i$ and $j$ are mutual visual. Let $n=|V|$, where $|V|$ means the
cardinality of the set $V$. As in spectral graph theory, we have adjacency
matrix $\hat{A}(G)$. Then we have the following three $n\times n$ dual
quaternion matrices: the relative configuration adjacency matrix $\hat{C}(G)$,
the logarithm adjacency matrix $\hat{L}n(G)$, and the relative twist adjacency
matrix $\hat{T}(G)$. Recall the concepts of relative configuration, twist and
logarithm of dual quaternions discussed in Section 2. The $(i,j)$ entries of
$\hat{C}(G),\hat{L}n(G)$ and $\hat{T}(G)$ are the relative configuration
$\hat{q}_{ij}$, the logarithm of the relative configuration
$\ln\hat{q}_{ij}={1\over 2}(\theta_{ij}x_{ij}+\epsilon p_{ij}^{b})$, and the
relative twist $\hat{\xi}_{ij}^{b}$, respectively, if $i,j=1,\cdots,n,i\not=j$
and $(i,j)\in E$. The $(i,j)$ entries of $\hat{C}(G),\hat{L}n(G)$ and
$\hat{T}(G)$ are zero otherwise.

Note that $\hat{q}_{ij}$ is a unit dual quaternion, $\ln\hat{q}_{ij}$ is a
unit imaginary dual quaternion, and $\hat{\xi}_{ij}^{b}$ is an imaginary dual
quaternion.

We have the following theorem.

######  Theorem 3.1.

The relative configuration adjacency matrix $\hat{C}(G)$ and the logarithm
adjacency matrix $\hat{L}n(G)$ are dual quaternion Hermitian matrices. For a
cycle $\\{j_{1},\cdots,j_{k}\\}$, with $j_{k+1}=j_{1}$, of $G$, we have

$\prod_{i=1}^{k}\hat{q}_{j_{i}j_{i+1}}=1.$ (22)

###### Proof.

For $i,j=1,\cdots,n$, $i\not=j$, by Property A,
$\hat{q}_{j}=\hat{q}_{i}\hat{q}_{ij}$. Thus, we have

$\hat{q}_{ij}=(\hat{q}_{i})^{-1}\hat{q}_{j}.$

Thus,

$\hat{q}_{ji}=(\hat{q}_{j})^{-1}\hat{q}_{i}=(\hat{q}_{ij})^{-1}.$ (23)

Since $\hat{q}_{ij}$ is a unit dual quaternion, this implies that

$\hat{q}_{ji}=(\hat{q}_{ij})^{*}.$ (24)

This shows that $\hat{C}(G)$ is an Hermitian matrix. By (23), we have

$\ln\hat{q}_{ji}=-\ln\hat{q}_{ij}.$

Since $\ln\hat{q}_{ij}$ is an imaginary dual quaternion, this implies

$\ln\hat{q}_{ji}=\left(\ln\hat{q}_{ij}\right)^{*}.$

Thus, $\hat{L}n(G)$ is also an Hermitian matrix.

On the cycle $\\{j_{1},\cdots,j_{k}\\}$, we have
$\hat{q}_{j_{i+1}}=\hat{q}_{j_{i}}\hat{q}_{j_{i}j_{i+1}}$ for $i=1,\cdots,k$.
This implies (22). ∎

Formula (22) shows that if there is a cycle in the mutual visibility graph
$G$, then we may always delete one edge in that cycle without affecting the
description of mutual visibility. Repeating this process, eventually the
mutual visibility graph contains no cycle. If the original mutual visibility
graph is connected, then we obtain a reduced mutual visibility graph, which is
a tree. Then we may apply the formation control strategy described in [17].

##  4 Dual Quaternion Laplacian Matrices

In the last section, we show that the relative configuration adjacency matrix
$\hat{C}(G)$ and the logarithm adjacency matrix $\hat{L}n(G)$ are dual
quaternion Hermitian matrices. This lays the base for us to study the
stability issue of the multi-agent formation control problem. In this section,
we set the dual quaternion Laplacian matrix theory such that we have a tool to
tackle this issue. Before doing this, we establish a Gershgorian type theorem
for dual quaternion Hermitian matrices.

######  Theorem 4.1.

Suppose that $\hat{H}=(\hat{h}_{ij})\in{\hat{\mathbb{Q}}}^{n\times n}$ is an
Hermitian matrix. Then the $n$ eigenvalues of $\hat{H}$ lay in the following
$n$ sets:

$S_{i}=\left\\{\hat{\lambda}\in{\hat{\mathbb{D}}}:|\lambda-\hat{h}_{ii}|\leq\sum_{j\not=i}|\hat{h}_{ij}|\right\\},$

for $i=1,\cdots,n$.

###### Proof.

Suppose that $\hat{\lambda}$ is an eigenvalue of $H$ with an eigenvector
$\hat{\mathbf{x}}$. Then $\hat{\lambda}\in{\hat{\mathbb{R}}}$, and
$\hat{\mathbf{x}}\in{\hat{\mathbb{Q}}}^{n}$ is appreciable. By (15), we have

$\sum_{j=1}^{n}\hat{h}_{ij}\hat{x}_{j}=\hat{\lambda}\hat{x}_{i},$

i.e.,

$\sum_{j\not=i}\hat{h}_{ij}\hat{x}_{j}=\left(\hat{\lambda}-\hat{h}_{ii}\right)\hat{x}_{i},$

for $i=1,\cdots,n$. Assume that
$\left|\hat{x}_{i}\right|=\max_{j=1,\cdots,n}\left|\hat{x}_{j}\right|$. Since
$\hat{\mathbf{x}}$ is appreciable, $\left|\hat{x}_{i}\right|$ must be
appreciable. Then we have

$|\lambda-\hat{h}_{ii}|\leq\sum_{j\not=i}|\hat{h}_{ij}|.$

This proves the theorem. ∎

Suppose that we have a mutual visibility graph $G=(V,E)$ with $|V|=n$. For
each $i\in V$, let $d(i)$ be the number of edges $(i,j)\in E$. Let
$D(G)=(d_{ij})$ be an $n\times n$ real diagonal matrix, with its $i$th
diagonal entry being $d(i)$. Let $A(G)=(a_{ij})$ be an $n\times n$ traceless
matrix, with $a_{ij}=1$ if and only if $(i,j)\in E$. Here, the word
“traceless” means that the diagonal entries of $A$ are zero. Let
$L(G)=D(G)-A(G)$. Then $D(G)$, $A(G)$ and $L(G)$ are the degree matrix, the
adjacency matrix and the Laplacian matrix of $G$. Spectral graph theory are
based upon these three matrices.

We now extend these to dual quaternion matrices. We keep the degree matrix
without any change as the degree $d(i)$, which is the number of rigid-bodies
that can be sensed by the rigid-body $i$. This is meaningful in formation
control. Then we call an $n\times n$ dual quaternion Hermitian matrix
$\hat{H}=\left(\hat{h}_{ij}\right)$ a dual quaternion adjacency matrix, if
$\hat{h}_{ij}=\left(\hat{h}_{ji}\right)^{*}$ is a unit dual quaternion for any
$i<j$ satisfying that the rigid body $i$ can be sensed by the rigid body $j$,
and other entries $0$. Apparently, the relative configuration adjacency matrix
$\hat{C}(G)$ and the logarithm adjacency matrix $\hat{L}n(G)$ are of such a
type. Furthermore, we call $\hat{L}(\hat{H})=D-\hat{H}$ the dual quaternion
Laplacian matrix, associated with $\hat{H}$.

######  Theorem 4.2.

A dual quaternion Laplacian matrix is a positive semi-definite dual quaternion
Hermitian matrix. Its $n$ eigenvalues are nonnegative dual numbers.

###### Proof.

By the definition of dual quaternion Laplacian matrices and Theorem 4.1, all
the eigenvalues of a dual quaternion Laplacian matrix are nonnegative dual
numbers. By Theorem 2.4, this matrix is positive semi-definite. ∎

##  5 Formation Control of Multiple Rigid-Bodies

The objective of this study is to design a universal control scheme without
requiring decoupling rotational and translational dynamics to make all the
connected rigid-bodies rendezvous, i.e., converge into a predefined or
unspecified configuration based upon error dynamics with perfect and
instantaneous measurements. Assume that there are $n$ rigid bodies as
described in the last section. The positions of these $n$ rigid bodies are
denoted by a dual quaternion vector
$\hat{\mathbf{z}}=(\hat{z}_{1},\cdots,\hat{z}_{n})^{\top}\in{\hat{\mathbb{Q}}^{n}}$.
Each rigid body $i$ is assumed to have an onboard sensor to measure relative
positions of neighboring rigid bodies, that is
$\hat{z}_{ij}\in\hat{\mathbb{Q}}$ when $(i,j)\in E$ for the mutual visibility
graph $G=(V,E)$. Here, $\hat{z}_{i,j}$ may be the relative configuration
$\hat{q}_{ij}$, the logarithm of the relative configuration $\ln\hat{q}_{ij}$,
the relative twist $\hat{\xi}_{ij}^{b}$, or simply

$\hat{z}_{ij}=\hat{z}_{j}-\hat{z}_{i}.$

Assume that each rigid body $i$ has a point kinematic model given by the
single integrator

${{d\hat{z}_{i}}\over dt}=\hat{u}_{i},$ (25)

where $\hat{u}_{i}\in\mathbb{Q}$ represents the velocity control input. Let
$\hat{\mathbf{v}}=(\hat{v}_{1},\cdots,\hat{v}_{n})^{\top}\in{\hat{\mathbb{Q}}^{n}}$
be the targeted formation configuration, satisfying
$\hat{L}\hat{\mathbf{v}}=0$. Then we consider the control law

$\hat{u}_{i}=\sum_{(i,j)\in E}\hat{l}_{ij}(\hat{z}_{j}-\hat{z}_{i}),$ (26)

where $\hat{l}_{ij}$ are the entries of the Laplacian matrix $\hat{L}$, for
$i=1,\cdots,n$.

Under the control law (26), the overall closed-loop dynamics of the $n$ rigid
bodies becomes

${{d\hat{\mathbf{z}}}\over dt}=-\hat{L}\hat{\mathbf{z}}.$ (27)

Then, as studied in [11], if $\hat{L}$ is positive semi-definite, and its
eigenvalues are positive except at one zero eigenvalue, the system is stable.
Hence, Theorem 4.2 paves a way for such a study.

## References

  * [1] H. Ando, Y. Oasa, I. Suzuki and M. Yamashita, Distributed memoryless point convergence algorithm for mobile robots with limited visibility”, IEEE Transactions on Robotics and Automation 15 (1999) 818-828.
  * [2] H. Abaunza, P. Castillo, A. Victorino and R. Lozano, “Dual quaternion modeling and control of a quad-rotor aerial manipulator”, Journal of Intelligent & Robotic Systems 88 (2017) 267-283.
  * [3] G. Brambley and J. Kim, “Unit dual quaternion-based pose optimization for visual runway observations”, IET Cyber-Systems and Robotics 2 (2020) 181-189.
  * [4] S. Bultmann, K. Li and U.D. Hanebeck, “Stereo visual SLAM based on unscented dual quaternion filtering”, 2019 22th International Conference on Information Fusion (FUSION) (2019) 1-8.
  * [5] J. Cheng, J. Kim, Z. Jiang and W. Che, “Dual quaternion-based graph SLAM”, Robotics and Autonomous Systems 77 (2016) 15-24.
  * [6] W.K. Clifford, “Preliminary sketch of bi-quaternions”, Proceedings of the London Mathematical Society 4 (1873) 381-395.
  * [7] K. Daniilidis, “Hand-eye calibration using dual quaternions”, The International Journal of Robotics Research 18 (1999) 286-298.
  * [8] C.M. Hoffmann and W. Yang, “Compliant motion constraint”, Z. Li and W.Y. Sit, eds., Computer Mathematics, Proceedings of the Sixth Asian Symposium (ASCM 2003), World Scentific, Singapore, 2003, 1-16.
  * [9] B. Kenright, “A beginners guide to dual-quaternions”, 20th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, Plzen, Czech, 2012.
  * [10] G. Leclercq, Ph. Lefévre and G. Blohm, “3D kinematics using dual quaternions: Theory and applications in neuroscience”, Frontiers in Behavioral Neuroscience 7 (2013) Article 7, 1-25.
  * [11] Z. Lin, L. Wang, Z. Han and M. Fu, “Distributed formation control of multi-agent systems using complex Laplacian”, IEEE Transactions on Automatic Control 59 (2014) 1765-1777.
  * [12] C. Ling, H. He and L. Qi, “Singular values of dual quaternion matrices and their low-rank approximations”, Numerical Functional Analysis and Optimization 43 (2022) 1423-1458.
  * [13] X. Peng, X. Shi and Y. Gong, “Dual-quaternion-based modelling and control for motion tracking of a tumbling target”, Journal of Systems Engineering and Electronic 30 (2019) 985-994.
  * [14] L. Qi, C. Ling and H. Yan, “Dual quaternions and dual quaternion vectors”, Communications on Applied Mathematics and Computation 4 (2022) 1494-1508.
  * [15] L. Qi and Z. Luo, “Eigenvalues and singular values of dual quaternion matrices”, to appear in: Pacific Journal of Optimization.
  * [16] X. Wang, Formation Control in Three Dimensional Space and with Nonlinear Dynamics, Ph.D. Thesis (in Chinese), National University of Defence Technology, Changsha, China, 2011.
  * [17] X. Wang, C. Yu and Z. Lin, “A dual quaternion solution to attitude and position control for rigid body coordination”, IEEE Transactions on Robotics 28 (2012) 1162-1170.
  * [18] X. Wang, C. Yu and Z. Zheng, “Multiple rigid-bodies rendezvous problem based on unit dual quaternions”, manuscript.