text:
\begin{document}

\date{\today}

\title{On rack colorings for surface-knot diagrams without branch points}

\author{Kanako Oshiro}
\address{Department of Information and Communication Sciences,
Sophia University, 7-1 Kioicho, Chiyoda-ku, Tokyo 102-8554, Japan}
\ead{oshirok@sophia.ac.jp}

\author{Kokoro Tanaka}
\address{Department of Mathematics, Tokyo Gakugei University,
Nukuikita 4-1-1, Koganei, Tokyo 184-8501, Japan}

\ead{kotanaka@u-gakugei.ac.jp}

\begin{abstract}

Racks do not give us invariants of surface-knots in general.
For example, if a surface-knot diagram has branch points
(and a rack which we use satisfies some mild condition),

then it admits no rack colorings.
In this paper, we investigate rack colorings for surface-knot diagrams
without branch points and prove that
rack colorings are invariants of $S^2$-knots.
We also prove that rack colorings for $S^2$-knots
can be interpreted in terms of quandles,

and discuss a relationship with regular-equivalences of surface-knot diagrams.

\end{abstract}

\begin{keyword}
surface-knot \sep rack \sep branch point \sep quandle
\MSC Primary 57Q45 \sep Secondary 57M25
\end{keyword}

\maketitle

\section{Introduction}\label{sec:intro}

A \textit{quandle} \cite{Joy-82,Mat-82} is an algebraic system
with three axioms which correspond to the Reidemeister moves, and
is useful for studying classical knots in the $3$-space.
For example, for a given quandle, we have an invariant of oriented knots,
called a \textit{quandle coloring},
which has been extensively studied by many researchers
(cf. \cite{CESY,HHO-12,Inoue-01}).
There is an algebraic system, called a \textit{rack} \cite{FR-92}, similar to a quandle.

It has two axioms which correspond to the framed Reidemeister moves, and
is useful for studying framed classical knots in the $3$-space.
We note that a quandle is a rack by definition.
For example, for a given rack,
we have an invariant of oriented framed knots,
called a \textit{rack coloring}.
Rack colorings themselves are not invariants of (unframed) oriented knots.
However, by using rack colorings, Nelson \cite{Nel-pre} constructed
an invariant of oriented knots.
Later, the second author and Taniguchi \cite{TanakaT} gave
interpretation of his invariant in terms of quandles.

Quandles are also useful for studying surface-knots in the $4$-space.
For example, for a given quandle,
we also have an invariant of surface-knots, called
a \textit{quandle coloring}.
A quandle coloring for surface-knots has also been extensively studied
by many researchers (cf. \cite{Iwa-06,SS-05,Tan-05}).
On the contrary, as far as the authors know,
there are no study of surface-knots by using rack theory at present.
(We note that framed surface-knots, more generally
framed submanifolds of the $n$-space of codimension $2$ with $n \geq 3$,
were studied in \cite{FRS-07} by using rack theory.)
One of reasons is that surface-knot diagrams may have branch points.
For example, for a given rack,
we can also define a \textit{rack coloring} for surface-knot diagrams
in a way similar to quandle colorings.
However, if a surface-knot diagram has branch points
(and a rack which we use satisfies some mild condition),
then it admits no rack coloring.
We also observe in Example~\ref{ex:Satoh} that
even if surface-knot diagrams which we consider have no branch points,
rack colorings are not invariants of surface-knots in general.

In this paper, we investigate rack colorings for surface-knot diagrams
without branch points and prove that
rack colorings are invariants of $S^2$-knots (Theorem~\ref{thm:main1}).

We also prove that
rack colorings for $S^2$-knot diagrams without branch points can be interpreted
in terms of quandles (Theorem~\ref{thm:main2}).

We note that Theorem~\ref{thm:main2} implies Theorem~\ref{thm:main1}.
In the final section, we also discuss a relationship with
regular-equivalences of surface-knot diagrams,
where two diagrams representing the same surface-knot are said to be
regular-equivalent if they are related by a finite sequence of
\lq\lq branch-free\rq\rq\ Roseman moves.

This paper is organized as follows.
Section~\ref{sec:def} is devoted to reviewing racks, quandles,
surface-knots and their diagrams.
Our main results, Theorem~\ref{thm:main1} and \ref{thm:main2}, are stated
in Section~\ref{sec:main}.

We study rack colorings of
surface-knot diagrams with immersed curves in Section~\ref{sec:immersed}.
Section~\ref{sec:associated} provides a relationship
between a rack coloring with immersed curves and a quandle coloring

when surface-knot diagrams which we consider have no branch points.
These two sections are devoted to giving the proof of Theorem~\ref{thm:main2},
which is proven in the end of Section~\ref{sec:associated}.
As mentioned above, Theorem~\ref{thm:main2} implies Theorem~\ref{thm:main1}.
In Section~\ref{sec:reg-eq}, we discuss a relationship with regular-equivalences
of surface-knot diagrams.

\section{Definition}\label{sec:def}

\subsection{Racks and quandles}
For a non-empty set $X$ and a binary operation $*$ on $X$,

we consider the following three conditions.
\begin{enumerate}
\item[(Q1)]
For any $a \in X$, $a*a=a$.
\item[(Q2)]
For any $a \in X$, the map $*a : X \to X$, defined by $\bullet \mapsto \bullet *a$,
is bijective.
\item[(Q3)]
For any $a,b,c \in X$, $(a*b)*c=(a*c)*(b*c)$.
\end{enumerate}
These three correspond to the Reidemeister
moves of type I, II and III respectively.

A pair $(X,*)$ is called a \textit{quandle}
if it satisfies conditions (Q1), (Q2) and (Q3).
Quandles are useful for studying oriented knots and
also for oriented surface-knots.

A pair $(X,*)$ is called a \textit{rack}
if it satisfies conditions (Q2) and (Q3).
Racks are useful for studying oriented framed knots.

We remark that a quandle is a rack by definition and
that a rack/quandle $(X,*)$ is often abbreviated to $X$.
Racks and quandles have been studied in, for example, \cite{FR-92,Joy-82,Mat-82}.

\subsection{Surface-knots and their diagrams}
A \textit{surface-knot} (or a \textit{$\Sigma^2$-knot}) is
a submanifold of the $4$-space $\R^4$,
homeomorphic to a closed connected oriented surface $\Sigma^2$.

We always assume that all surface-knots are oriented in this paper.

Two surface-knots are said to be \textit{equivalent} if they can be deformed into
each other through an isotopy of $\R^4$.

A \textit{diagram} of a surface-knot is its image
via a generic projection from $\R^4$ to $\R^3$,
equipped with the height information as follows:
At a neighborhood of each double point, there are
intersecting two disks and
one is higher than the other with respect to the $4$th coordinate
dropped by the projection.
Then the height information is indicated by removing
the regular neighborhood of the double point in the lower disk
along the double point curves.

Then a diagram is regarded as a disjoint union of connected compact
oriented surfaces, each of which is called a \textit{sheet}.
A diagram is basically composed of four kinds of
local pictures,

each of which is the image of a neighborhood of
a typical point ---
a regular point, a \textit{double point},
an isolated \textit{triple point} or an isolated \textit{branch point}.
The latter three are depicted in Figure~\ref{fig:diagram}.

\begin{figure}[thbp]\centering
\includegraphics[width=0.7\textwidth]{figure/doub-tri-branch.eps}
\caption{Local picture of the projection image of a surface-knot}\label{fig:diagram}
\end{figure}

Two surface-knot diagrams are said to be \textit{equivalent}
if they are related by (ambient isotopies of $\R^3$ and)
a finite sequence of seven Roseman moves,
shown in Figure~\ref{fig:roseman}, where we omit height information for simplicity.
According to Roseman \cite{Ros-95}, two surface-knots are equivalent if and only if
they have equivalent diagrams. We refer to \cite{CS-book} for more details.

\begin{figure}[thbp]\centering

\includegraphics[width=1.0\textwidth]{figure/roseman.eps}
\caption{Roseman moves}\label{fig:roseman}
\end{figure}

\section{Rack colorings and main theorem}\label{sec:main}

\subsection{Rack colorings}

We represent the orientation of a surface-knot diagram
by assigning normal directions $\vec{n}$,
depicted by an arrow
which looks like the symbol \lq\lq $\Uparrow$\rq\rq\
as in Figure~\ref{fig:coloring-1}, to each sheet of the diagram
such that the triple $(\vec{v}_1, \vec{v}_2, \vec{n})$ matches
the orientation of $\R^3$, where the pair $(\vec{v}_1, \vec{v}_2)$
denote the orientation of the sheet.

For a surface-knot diagram $D$, let $\s(D)$ denote the set of all sheet of $D$.
For a rack $R$, a map $c: \s(D) \to R$ is
a \textit{rack coloring}
if it satisfies the following relation along each double point curve.
Let $x_j$ be the over-sheet along a double point curve, and
$x_i, x_k$ be under-sheets along the double point curve
such that the normal direction of $x_j$ points from $x_i$ to $x_k$.
Then it is required that $c(x_k)=c(x_i)*c(x_j)$ as in Figure~\ref{fig:coloring-1}.
Let $\Col_R(D)$ be the set of rack colorings of $D$ by $R$.
We note that when a rack $R$ is finite, $\Col_R(D)$ is also finite.

If a rack which we consider is a quandle,
then a rack coloring is also called a \textit{quandle coloring}.

\begin{figure}[thbp]\centering
\begin{minipage}[]{0.35\hsize}
\includegraphics[width=\hsize]{figure/relation-surface-ori.eps}
\end{minipage}\qquad{\Large $c(x_i) * c(x_j) = c(x_k)$}
\caption{Coloring relation along a double point curve}
\label{fig:coloring-1}
\end{figure}

It is known that a quandle coloring by a quandle $Q$
is an invariant of surface-knots (cf. \cite{CKS-book}).
Precisely speaking, for two diagrams $D_1$ and $D_2$ of a surface-knot,
there is a bijection between $\Col_Q(D_1)$ and $\Col_Q(D_2)$.
For rack colorings, this is not the case in general.
One of the difficulties is the existence of branch points.

For example, if a diagram $D$ has branch points and
a rack $R$ has no element $a$ such that $a*a = a$,
then $D$ admits no rack coloring by $R$, that is, $\Col_R(D)$ is the emptyset.
This is because the equation $a*a =a$ for some $a \in R$ is required
as the rack coloring condition along a double point curve
one of whose endpoints is a branch point.
(We note that a non-quandle connected rack, such as a cyclic rack
\cite[Example 7]{FR-92}, has no element $a$ such that $a*a = a$.
Since we do not use the precise definition of the connectedness for racks,
we omit the details and give some comments instead.
It is known that any rack is decomposed into the connected components
each of which is also a rack.
It is also known
that any rack coloring for a surface-knot diagram by a rack
is essentially
the one by a connected component of the rack.
Hence the connectedness for racks is

suitable in considering rack colorings for surface-knot diagrams.)

\subsection{Diagrams without branch points}\label{subsec:branch}
Even if surface-knot diagrams which we consider have no branch points,
we observe, in Example~\ref{ex:Satoh} below,
that rack colorings are not invariants of surface-knots in general.
We note that every (oriented) surface-knot has a diagram
without branch points (cf. \cite{CS-92}).

\begin{example}\label{ex:Satoh}
Let $D_1$ and $D_2$ be two surface-knot diagrams as in Figure~\ref{fig:satoh}.
Both represent the same $T^2$-knot and do not have branch points.
(We note that both represent a trivial $T^2$-knot,
which bounds a solid torus in $\R^4$.)
However, for a finite non-quandle connected rack $R$,
the number of $\Col_R(D_1)$ is strictly more than that of $\Col_R(D_2)$,
since $R$ has no element $a$ such that $a*a=a$
which is required as a rack coloring condition around
the double point curve of $D_2$.
That is, the number of $\Col_R(D_2)$ is zero,
while the number of $\Col_R(D_1)$ is equal to that of $R$.

This is because Roseman moves of type B1 and B2 may change the
number of rack colorings by a finite rack in general.
We note that these diagrams are appeared in Satoh's paper \cite{Sat-01}.
We return to this example in Section~\ref{sec:reg-eq} again.

\begin{figure}[thbp]\centering
{\large $D_1$:} \
\begin{minipage}{0.3\hsize}
\includegraphics[width=\hsize]{figure/T2.eps}
\end{minipage} \qquad
{\large $D_2$:} \
\begin{minipage}{0.33\hsize}
\includegraphics[width=\hsize]{figure/satoh.eps}
\end{minipage}
\caption{Satoh's $T^2$-knot diagrams}\label{fig:satoh}
\end{figure}

\end{example}

\subsection{Main theorem}
The above situation is totally different for $S^2$-knots.
In fact, we can prove the following:

\begin{theorem}\label{thm:main1}
For any two diagrams $D_1$ and $D_2$
of an $S^2$-knot without branch points,

there is a bijection between $\Col_R(D_1)$ and $\Col_R(D_2)$.
\end{theorem}

This theorem says that a rack coloring is an invariant of $S^2$-knots,
even if a sequence of Roseman moves between
$D_1$ and $D_2$
may involve branch points.

For any rack $R$, we will define the associated quandle, denoted by $Q_R$,
of $R$ in Section~\ref{sec:associated}.
Then a rack coloring by $R$ can be interpreted in terms of
its associated quandle $Q_R$ as follows:

\begin{theorem}\label{thm:main2}
For any $S^2$-knot diagram $D$ without branch points,

there is a bijection between $\Col_R(D)$ and $\Col_{Q_R}(D)$.
\end{theorem}

Since quandle colorings are invariants of surface-knots,
Theorem~\ref{thm:main2} implies Theorem~\ref{thm:main1}.
Hence, in what follows,
we focus on proving Theorem~\ref{thm:main2}.
Before that,
we will show Theorem~\ref{thm:immersed} in Section~\ref{sec:immersed}
and Theorem~\ref{thm:associated} in Section~\ref{sec:associated}.
Combining these two theorems,
we will prove Theorem~\ref{thm:main2} in
the end of Section~\ref{sec:associated}.

\section{Rack colorings with immersed curves}\label{sec:immersed}

\subsection{The kink map of a rack}
For a rack $R=(R,*)$, let $\iota : R \to R$

be the map, called the (negative) \textit{kink map} \cite{TanakaT} of $R$,
characterized by the equation $\iota (a)*a=a$ for any element $a \in R$.
The map $\iota$ is well-defined by the condition (Q2).
It might be better to denote it by a symbol like \lq\lq $\iota_R$\rq\rq ,
since this map is uniquely determined by $R$.
However, we denote it by $\iota$ for simplicity.
We note that (a notion similar to) the map $\iota$
has essentially appeared in \cite{Nel-pre}.
See Remark~\ref{rem:kink} below for comments on
a hidden diagrammatic meaning of the kink map $\iota$.
It is known in \cite{TanakaT} that the kink map $\iota$ satisfies
the following three conditions.
\begin{enumerate}
\item[(K1)]
The map $\iota$ is bijective.
\item[(K2)]
For any $a,b \in R$, $\iota(a)*b=\iota(a*b)$.
\item[(K3)]
For any $a,b \in R$, $a * \iota(b)= a*b$.
\end{enumerate}
By the condition (K1), there is a unique inverse map,
denoted by $\iota^{-1}$ in a usual way, of the kink map $\iota$.

Then, for any integer $n$, a symbol $\iota^n$ does make sense,
that is, the symbol $\iota^n$ denote
the $n$-times composition of $\iota$ for $n \geq 0$ and
the $|n|$-times composition of $\iota^{-1}$ for $n < 0$.

\begin{remark}\label{rem:kink}

The kink map $\iota$ of a rack $R$
corresponds to a negative kink of a classical knot diagram
in the following sense.
The negative kink consists of the two arcs as in Figure~\ref{fig:kink}.
If we assign an element $a \in R$ to the arc which comes in,
then the arc which goes out receives the element $\iota(a) \in R$
by the rack coloring condition at the crossing,
where rack colorings for classical knots
are defined in a way similar to that for surface-knots and

we omit the details for the definition.

Thus we can think of the kink map $\iota$ as
an algebraic abstraction of the negative kink.

\begin{figure}[thbp]\centering
\begin{minipage}[]{0.3\hsize}
\includegraphics[width=\hsize]{figure/kink.eps}
\end{minipage}\qquad \qquad
\begin{minipage}[]{0.4\hsize}
{\Large $\fbox{??} * a = a$ \\
\quad \quad $\rightsquigarrow$ $\fbox{??}=\iota(a)$}
\end{minipage}
\caption{The map kink $\iota$ and a negative kink}\label{fig:kink}
\end{figure}
\end{remark}

\subsection{Rack colorings with immersed curves}
Consider a set $L$ of oriented immersed curves on a surface-knot diagram $D$.
We assume that $L$ intersects itself transversely
and each multiple point is a double point.
We further assume that $L$ intersects the double point curves of $D$
transversely, and misses triple points and branch points of $D$.
The orientation for each immersed curve of $L$ is represented
by normal directions $\vec{n}$,
depicted by an arrow
which looks like the symbol \lq\lq $\uparrow$\rq\rq\
as in Figure~\ref{fig:curve},
such that the pair $(\vec{v}, \vec{n})$ matches the orientation of $D$,
where $\vec{v}$ denote the orientation of the immersed curve.

\begin{figure}[thbp]\centering
\includegraphics[width=0.35\textwidth]{figure/immersed_curve.eps}
\caption{Local picture of oriented immersed curves on a diagram}\label{fig:curve}
\end{figure}

By cutting each sheet in $\s(D)$ along the curves of $L$,
we obtain a disjoint union of connected compact oriented
surfaces, each of which is also called a \textit{sheet} of the pair $(D,L)$.
We note that the local picture of a diagram in Figure~\ref{fig:curve}
consists of seven sheets.
We denote by $\s(D,L)$ the set of all sheet of $(D,L)$.

We note that each sheet in $\s(D,L)$ is included in a unique sheet
in $\s(D)$ as a subset.
For a rack $R$, a map $c: \s(D,L) \to R$ is a
\textit{rack coloring with immersed curves}
if it satisfies the two relation:

\begin{itemize}
\item
One is the same relation along each double point curve of $D$ as
that in (usual) rack colorings, and
\item
The other is the following relation along each oriented immersed curve of $L$.
Let $x_i$, $x_j$ be two sheets along an oriented immersed curve
such that the normal direction of the curve points from
$x_i$ to $x_j$. Then it is required that $c(x_j)=\iota(c(x_i))$
as in the left of Figure~\ref{fig:coloring-2}.
\end{itemize}

\begin{figure}[thbp]\centering
$\begin{minipage}[]{0.3\hsize}
\includegraphics[width=\hsize]{figure/immersed_curve_coloring_1st.eps}

\medskip{\Large $c(x_j)=\iota(c(x_i))$}
\end{minipage}\quad
\left( \quad
\xlongleftrightarrow[\textrm{\large Remark~\ref{rem:immersed}}]{\phantom{xxxxxxxx}}
\begin{minipage}[]{0.3\hsize}
\includegraphics[width=\hsize]{figure/immersed_curve_coloring_2nd.eps}

\medskip{\Large $c(x_j)=\iota(c(x_i))$}
\end{minipage} \ \right) $
\caption{Coloring relation along an oriented immersed curve}
\label{fig:coloring-2}
\end{figure}

See Remark~\ref{rem:immersed} below for comments on the latter
(somewhat artificial) coloring condition.
Let $\Col_R(D,L)$ be the set of rack colorings of $(D,L)$ by $R$.
We note that when a rack $R$ is finite, $\Col_R(D,L)$ is also finite.

At each double point, say $p$, of $L$ and double point curves of $D$,
the well-definedness of rack coloring with immersed curves is not so obvious.
By using the properties (K2) and (K3) of the kink map $\iota$,
we can show the following near the double point $p$.
\begin{itemize}
\item
If an arc of $L$ lies on the under-sheets,
the condition (K2) ensures the well-definedness at $p$.
The situation is illustrated on
the left of Figure~\ref{fig:well-defined}.
\item
If an arc of $L$ lies on the over-sheet,
the condition (K3) ensures the well-definedness at $p$.
The situation is illustrated on
the right of Figure~\ref{fig:well-defined}.
\end{itemize}

\begin{figure}[thbp]\centering
\includegraphics[width=0.83\hsize]{figure/well-defined.eps}

\caption{Well-definedness of rack colorings with immersed curves}
\label{fig:well-defined}
\end{figure}

\begin{remark}\label{rem:immersed}
We mention here a hidden meaning of a set $L$ of
oriented immersed curves on a surface-knot diagram $D$.
A neighborhood of an arc of $L$ on $D$ is virtually
considered as an abstraction of \lq\lq (kink)$\times [0,1]$\rq\rq\
as in the right of Figure~\ref{fig:coloring-2}.
If we replace the neighborhood of the arc of $L$ virtually
with \lq\lq (kink)$\times [0,1]$\rq\rq ,
then the (usual) rack coloring condition implies
our coloring condition along each oriented immersed curve of $L$.
\end{remark}

\begin{prop}\label{prop:immersed}

For two sets $L_1$ and $L_2$ of oriented immersed curves
on a surface-knot diagram $D$,
if $L_1$ is homologous to $L_2$, then

there is a bijection between $\Col_R(D,L_1)$ and $\Col_R(D,L_2)$.
\end{prop}

\begin{proof}[Proof of Proposition~\ref{prop:immersed}]
We may assume that $L_1$ and $L_2$, by perturbing $L_1$ or $L_2$ if necessary,
intersect transversely and each multiple point on the union $L_1 \cup L_2$
is a double pont.
We denote by $-L_1$ the set $L_1$ with the opposite orientation.
Since $L_1$ and $L_2$ are homologous,
the union $(-L_1) \cup L_2$ is null-homologous on $D$.

We choose a sheet, say $x_0$, of $(D, (-L_1) \cup L_2)$, and
assign an integer to each sheet of $(D, (-L_1) \cup L_2)$
by the following Alexander numbering-like rule:
\begin{itemize}
\item
We assign $0$ to the sheet $x_0$.
\item
For two adjacent sheets $x_1$ and $x_2$ along an arc of $(-L_1) \cup L_2$,
we suppose that the normal orientation of the arc points from $x_1$.
Then the integer assigned to $x_2$ is larger than that to $x_1$ by $1$.

\item
For two adjacent sheets along a double point curve of $D$,
the integers assigned to them are the same.
\end{itemize}
See Figure~\ref{fig:numbering}.
Since  $(-L_1) \cup L_2$ is null-homologous on $D$,
this assignment is well-defined.

\begin{figure}[thbp]\centering
\includegraphics[width=0.8\textwidth]{figure/numbering.eps}\\
\caption{Numbering on $\s(D, (-L_1) \cup L_2)$}\label{fig:numbering}
\end{figure}

Using the above numbering on $\s(D, (-L_1) \cup L_2)$,
we construct an explicit bijection $\Phi: \Col_R(D,L_1) \to \Col_R(D,L_2)$.
For a coloring $c \in \Col_R(D,L_1)$, we define $\Phi(c) \in \Col_R(D,L_2)$ as follows:
Let $x_2$ be a sheet in $\s(D, L_2)$.
The sheet $x_2$ might be divided into the further smaller
sheets on $(D, (-L_1) \cup L_2)$.
(In the case where $L_1 \cap x_2= \emptyset$, the sheet $x_2$ is not divided.)
For the sheet $x_2$,
choose one of the small sheets on $(D, (-L_1) \cup L_2)$, and denote it by $y$.
We note that $y$ is included in $x_2$ as a subset on $(D, L_2)$.
Let $x_1$ be a unique sheet in $\s(D, -L_1)$
such that $x_1$ includes $y$ as a subset on $(D, -L_1)$.
See Figure~\ref{fig:bijection-phi}.
Then we define $\Phi(c)(x_2)=\iota^n (c(x_1))$,
where $n$ is the numbering on the small sheet $y$.

The well-definedness of the map $\Phi$ is shown as follows:
Two adjacent small sheets $y$ and $y'$, included in $x_2$ as subsets on
$(D, (-L_1) \cup L_2)$, are separated by an arc, say $\alpha$, of $-L_1$.
Suppose that  the normal orientation of $\alpha$ points from $y$.
By the above rule, it holds that $n'=n+1$, where
the integer $n$ (resp. $n'$) is the numbering on the small sheet $y$ (resp. $y'$).
Let $x_1$ and $x_1'$ be the sheets in $\s(D, -L_1)$ such that
$x_1$ (resp. $x_1'$) includes $y$ (resp. $y'$) as a subset on $(D, -L_1)$.

See Figure~\ref{fig:bijection-phi}.
By the rack coloring condition for immersed curves, the equation
$c(x_1) = \iota (c(x_1'))$ holds.

Therefore, we have

$$
\iota^{n} \bigl( c(x_1) \bigr) = \iota^{n'-1} \bigl( c(x_1) \bigr)
= \iota^{n'-1} \Bigl( \iota \bigl( c(x_1') \bigr) \Bigr)
= \iota^{n'} \bigl( c(x_1') \bigr) .
$$

We can also check that
the rack coloring conditions along $L_2$ and the double point curves of $D$
on $\s(D, L_2)$ are satisfied.
The inverse map of $\Phi$ can be constructed in a way similar to the
definition of $\Phi$.
(The only difference is to replace $n$ in the definition of $\Phi$ with $-n$.)

\begin{figure}[thbp]\centering
\includegraphics[width=0.80\textwidth]{figure/bijection-phi.eps}
\caption{Local picture of the bijection $\Phi$}\label{fig:bijection-phi}
\end{figure}
\end{proof}

Since any set of oriented immersed curves on an $S^2$-knot diagram is
null-homologous, Proposition~\ref{prop:immersed} implies:

\begin{theorem}\label{thm:immersed}

For any set $L$ of oriented immersed curves on an $S^2$-knot diagram $D$,

there is a bijection between $\Col_R(D,L)$ and $\Col_R(D)$.
\end{theorem}

\section{Associated quandles}\label{sec:associated}

For a rack $R=(R,*)$ and the kink map $\iota$ of $R$,
we define a new binary operation $*^{\iota}$ on the set $R$
by $a*^{\iota}b:=\iota(a)*b$.
Then it is known in \cite{AG-03,TanakaT} that the pair $(R,*^{\iota})$
becomes a quandle.
The quandle $(R, *^{\iota})$ is called the \textit{associated quandle} of $R$
and is denoted by $Q_R$.

If a surface-knot diagram has no branch points,
then quandle colorings by $Q_R$ can be interpreted
in terms of rack colorings with immersed curves by $R$ as follows:

\begin{theorem}\label{thm:associated}
For any surface-knot diagram $D$ without branch points,
there exists a set $L$ of oriented immersed curves on $D$ such that

there is a bijection between $\Col_{Q_R}(D)$ and $\Col_R(D,L)$.
\end{theorem}

\begin{proof}[Proof of Theorem~\ref{thm:associated}]
We take a set $L$ of oriented immersed curves as
a copy of the double point curves of $D$
by pushing the double point curves slightly on the under-sheet
in the direction opposite to the normal direction of the over-sheet
along each double point curve as in the right of Figure~\ref{fig:bijection-psi},
where the normal orientation of $L$ matches that of the over-sheet.
The set $L$ is well-defined, since the surface-knot diagram $D$,
which we now consider, has no branch points.
We note that when $D$ has no triple points (and no branch points),
the set $L$ consists of oriented embedded curves.

We construct an explicit bijection $\Psi: \Col_{Q_R}(D) \to \Col_R(D,L)$.
See Figure~\ref{fig:bijection-psi},
where we depict a local picture of $\Psi$ along an arc of the double point curves.
For a coloring $c \in \Col_{Q_R}(D)$, we define $\Psi(c) \in \Col_R(D,L)$ as follows:
Let $y$ be a sheet in $\s(D,L)$.
It follows from the construction of $L$ that
there exists a unique sheet, say $x$, in $\s(D)$ such that
$x$ includes $y$ as a subset on $D$.

Then we define $\Psi(c)(y) := \iota(c(x))$ if the sheet $y$
lies between an arc of $L$ and the double point curve
that is parallel to the arc, and $\Psi(c)(y) := c(x)$ if not.
This map $\Psi$ is well-defined, since the definition of
the binary operation of $Q_R$ requires
the equality $a*^{\iota}b = \iota(a)*b$.

\begin{figure}[thbp]\centering
$$\begin{array}{ccc}
\mathrm{Col}_{Q_R}(D) &
\xlongrightarrow[1:1]{\phantom{xxxx}{\text{\Large $\Psi$}}\phantom{xxxx}} &
\mathrm{Col}_{R}(D,L) \\
\begin{minipage}[]{0.35\hsize}
\includegraphics[width=\hsize]{figure/coloring_from_associated.eps}
\end{minipage}
&
&
\begin{minipage}[]{0.35\hsize}
\includegraphics[width=\hsize]{figure/coloring_to_immersed.eps}
\end{minipage}
\end{array}$$

\caption{Local picture of the bijection $\Psi$}\label{fig:bijection-psi}
\end{figure}

To prove the bijectiveness of $\Psi$,
we construct a map $\Psi': \Col_R(D,L) \to \Col_{Q_R}(D)$ and
show that $\Psi'$ is the inverse map of $\Psi$.
For a coloring $c' \in \Col_R(D,L)$,
we define $\Psi'(c') \in \Col_{Q_R}(D)$ as follows:
Let $x$ be a sheet in $\s(D)$.
It follows from the construction of $L$ that
there exists a unique sheet, say $y$, in $\s(D,L)$ such that
$y$ is included in $x$ as a subset on $D$ and
does not lie between an arc of $L$ and the double point curve
that is parallel to the arc.
Then we define $\Psi'(c')(x) := c'(y)$.
Again the definition of the binary operation of $Q_R$
ensures the well-definedness of $\Psi'$ and
we can check that $\Psi'$ is the inverse map of $\Psi$
by an explicit calculation.
\end{proof}

With Theorem~\ref{thm:immersed} and Theorem~\ref{thm:associated} in hand,
we now prove Theorem~\ref{thm:main2}.

\begin{proof}[Proof of Theorem~\ref{thm:main2}]
For an $S^2$-knot diagram $D$ without branch points,
by using Theorem~\ref{thm:associated},
there exists a set $L$ of oriented immersed curves on $D$ such that
there is a bijection between $\Col_{Q_R}(D)$ and $\Col_{R}(D,L)$.
Then, by using Theorem~\ref{thm:immersed},
there is a bijection between $\Col_{R}(D,L)$ and $\Col_{R}(D)$.
By the composition of these two bijections, we have a desired bijection.

\end{proof}

\section{Regular-equivalences and rack colorings}\label{sec:reg-eq}

Finally we discuss a relationship with
regular-equivalences of surface-knot diagrams.
As we mentioned in Subsection~\ref{subsec:branch},
any (oriented) surface-knot has a diagram without branch points.
In \cite{Sat-01},
such a \lq\lq branch-free\rq\rq\ diagram is called a \textit{regular} diagram,
and two regular diagrams are said to be
\textit{regular-equivalent} if they are related by a finite
sequence of \lq\lq branch-free\rq\rq\ Roseman moves,
that is, the moves of type $D1$, $D2$, $T1$ and $T2$
in Figure~\ref{fig:roseman}.

(For surface-knot diagrams, which may have branch points,
we can also define the notion of \lq\lq regular-equivalence\rq\rq\
in a similar way.
That is, two surface-knot diagrams are said to be
\textit{regular-equivalent} if they are related by a finite
sequence of \lq\lq branch-free\rq\rq\ Roseman moves.)

We can easily check that
there is a one-to-one correspondence between rack colorings
before and after each \lq\lq branch-free\rq\rq\ Roseman move.
(We note that there is also a one-to-one correspondence
before and after the Roseman move of type $BT$.)
Then we have the following:

\begin{theorem}\label{thm:reg-eq}
For two diagrams $D_1$ and $D_2$ of a surface-knot,
if they are regular-equivalent, then

there is a bijection between $\Col_R(D_1)$ and $\Col_R(D_2)$.
\end{theorem}

This theorem says that
rack colorings are invariants of regular-equivalence classes of

diagrams of a surface-knot.
Using a contraposition of Theorem~\ref{thm:reg-eq},
we can reprove that Satoh's examples are not regular-equivalent,
that is, Example~\ref{ex:Satoh} implies the following:

\begin{cor}\textrm{$($\cite[Theorem 3]{Sat-01}$)$}
There exist two regular surface-knot diagrams
which are equivalent but not regular-equivalent.

\end{cor}

Theorem~\ref{thm:reg-eq} cannot tell us
anything about regular-equivalence classes of diagrams of an $S^2$-knot.
Precisely speaking,
for two diagrams $D_1$ and $D_2$ of an $S^2$-knot,
it follows from Theorem~\ref{thm:main1}

that even if they are not regular-equivalent,

there is a bijection between
the two sets,
$\Col_R(D_1)$ and $\Col_R(D_2)$,

of rack colorings by a rack $R$.
However, Takase and the second author \cite{TakaseT} proved that,
for any regular $S^2$-knot diagram $D$,
there exists a regular diagram $D'$ such that
$D$ and $D'$ represent the same $S^2$-knot but they are not regular-equivalent.
They used immersion theory to prove
such a theorem
instead of rack theory.

\section*{Acknowledgments}
The authors thank Sam Nelson for several helpful comments.
The first author is partially supported by
Grant-in-Aid for Young Scientists (B) (No.~25800052),
Japan Society for the Promotion of Science.
The second author is partially supported by
Grant-in-Aid for Scientific Research (C) (No.~26400082),
Japan Society for the Promotion of Science.


text:
\begin{document}
\title{A sorting algorithm for complex eigenvalues}
\author[]{Usha Srinivasan \thanks{usha.s@nal.res.in}}
\author[]{ Rangachari Kidambi \thanks{kidambi@nal.res.in}}
\affil{Computational \& Theoretical Fluid Dynamics Division,
National Aerospace Laboratories, Bangalore 560017, India.}

\maketitle
\begin{abstract}
We present SPEC-RE, a new algorithm to sort complex eigenvalues, generated
as the solutions to algebraic equations, whose coefficients are analytic
functions of one or
many, possibly complex parameters. The fact that the eigenvalues are analytic
functions of the parameters, with atmost algebraic singularities, is used in
formulating the algorithm. Several examples are presented to demonstrate the
efficacy of the method; simple examples where other methods fail are also
presented. The algorithm is likely to be useful in several problems of physics
and engineering that require identification and sorting of eigenmodes.
\end{abstract}

\section{Introduction} \label{sec:introduction}

Linear stability analysis is ubiquitous in physics and engineering and basic
to such analysis is computation of spectral maps\footnote{The terms `modal
maps,' `eigenvalue trajectories' and `eigenpaths' will also be used to denote
these maps.}i.e
identifying eigenmodes as a function of the system parameters.

There are two broad approaches to producing such eigenmodes. The first one,
which considers the parameter variations as perturbations and then computes the
new eigenvalues as responses to these perturbations, has a long history dating
back to Jacobi in the middle of the nineteenth century. Since then, a variety
of methods like power methods and invariant subspace methods have been
developed. A nice recent review
of some of these methods is \cite{Golub-2000}. Starting with the original
system eigenvalues, the various algorithms provide means to compute first-order
eigenvalue sensitivities which are then used in a rapidly convergent iterative
method to produce new eigenvalues corresponding to the parameter change.
Some applications of this approach are \cite{Beyn-2009}, \cite{Eldred-1995}
and \cite{Wagner-2003}. We call this the `tracing' approach. Note that the
eigenmodes are produced automatically in course of the tracing. The second
approach is to solve the so-called dispersion relation (DR) for a range of
parameter values and then to sort the already determined eigenvalues, at
different values of the relevant parameter. Though this is mathematically
simpler, it seems to have been explored relatively less; some publications, in
fluid mechanics (\cite{Koch-1986}, \cite{Suslov-2006}) and electromagnetics
(\cite{Capek-2011} ) use this approach. We call this the `sorting' approach.
The `sorting' approach is the approach to use if one is interested in
identifying a few (typically 10-20) eigenmodes over a large range of parameter
values for moderate sized matrix systems (typically $N < 5000$) whereas the
`tracing' approach
has to be the preferred one if the goal is to generate very few (typically 1-2)
eigenmodes for a limited range of parameter values, but for large matrix
systems (typically $N > 5000$).

For real problems, the DR is rarely known in closed form; it exists as the
outcome of a matrix eigenvalue problem and is only numerically known (NDR).
Solution of such NDR is not really a problem; indeed fast and accurate numerical
implementations (for example in LAPACK) exist and work well, in general.
However, these algorithms only produce the eigenvalues for a given set of
parameters; changing the parameters produces a new set of eigenvalues with no
clarity on which of these eigenvalues belong together to say form a `mode'.
This would not be a major problem if the eigenvalues stay far apart and could be
traced separately; this is in general not the case because multiple roots are
inevitable for such systems. In the neighbourhood of such roots, the eigenvalue
trajectories can tangle and cross and the task of determining which eigenvalue
belongs to which trajectory can become quite difficult.

The spectral maps for a given system are indispensable
in solving initial / boundary value problems involving that system.
An understanding of the topography
specified by these maps as signified by the knowledge of critical points of the
map like saddles and branch points is crucial to a correct solution of such
problems. The absence of a reliable method to sort the eigenmodes correctly
has hampered a proper investigation of these problems; for example, in the
stability of fluid flows, very often only the least stable mode has been
pursued instead of
a detailed study of the modal structure. The situation is described
extensively in \cite{Suslov-2006}.

Crossing of the eigenvalue trajectories (equivalently collision of the
eigenvalues) is the main obstacle in a successful
sorting of the eigenvalues. There are a variety of crossings that have been
detailed in literature; we describe some of these below (we use $\alpha$ and
$\omega$ to denote the variable parameter and the eigenvalue respectively) -
\begin{enumerate}
\item False crossing C1. The trajectories, when plotted in the $\omega$ plane,
appear to cross i.e. there exist points in the $\omega$ plane such that
$\omega_m (\alpha_l) = \omega_n(\alpha_k)$ with $\alpha_l \ne \alpha_k.$
These are false crossings. In stability problems, where the focus is often
on the least stable mode, crossings in imaginary parts i.e.
$Im[\omega_m(\alpha)] = Im[\omega_n(\alpha)]$ lead to ambiguous definition of
various modes. However, unless the real parts also coincide at the same
$\alpha,$ these are obviously false crossings.
\item True crossing. When the above mentioned $\alpha_l = \alpha_k$,  we
have a true crossing and the eigenvalues are degenerate (\cite{Kato-1995}).
However, there are two cases to distinguish -
\begin{enumerate}
\item The non-defective case C2. A full complement of eigenvectors exists i.e
the geometric multiplicity of the repeated eigenvalue equals its algebraic
multiplicity.
\item The defective case C3. The geometric multiplicity is less than the
algebraic multiplicity. A full complement of independent eigenvectors does
not exist and generalised eigenvectors have to be used to obtain a full
complement. Two further subcases can be distinguished -
\begin{enumerate}
\item The analytic case C3A. The eigenvalues are analytic functions of the
parameter.
\item The non-analytic case C3B. The eigenvalues are non-analytic functions of
the parameter; in particular, they have branch points (BPs).
\end{enumerate}
\end{enumerate}
\item Avoided crossing C4. The eigenvalues come very close but do not actually
collide. Avoided crossings can be `broad' or `sharp'; the latter case is the
same as case C3B. Avoided crossings are of importance in  the study of chemical
reaction mechanisms and in quantum mechanics, especially to an understanding of
quantum chaos.
\end{enumerate}

Many approaches to sort eigenvalues exist in literature. We list some of these
below -
\begin{enumerate}
\item Ascending / descending order of their real or imaginary parts (S1).
\item Absolute value (S2).
\item Nearest neighbour (S3).
\item A combination of nearest neighbouring eigenvalue and nearest neighbouring
eigenvector (S4).
\end{enumerate}

S1 is the simplest to use and is reliable if the eigenvalue trajectories are
far apart. However, S1 fails even at false crossings C1. Examples are given
in \cite{Koch-1986} and \cite{Suslov-2006} which consider stability problems in
fluid mechanics. S2 and S3 negotiate the false crossings most of the time but
can fail sometimes (for example when the crossing point is on the real line) and
at true crossings. S4, which is used in some of the Open Source subroutines
(eigenshuffle.m, eigenshuffle.py \cite{eig1,eig2}) is
succesful more widely but can fail at certain types of C3 crossings. We will
provide examples of these failures in Sec 3.

In this paper, we present a simple method to sort eigenmodes
from eigenvalues that have been produced from an eigenvalue solver. The only
assumption is that the dispersion relation is an analytic function of its
parameters. \footnote{This is often the case for physical problems.} The
eigenvalues are sorted, based on their imaginary parts, at an initial point.
From these, the neighbouring values of each mode are obtained by using the
Cauchy - Riemann equations. This works in general because the eigenmodes
are analytic
and in particular at false collisions and true collisions of type C2 and C3A.
Even though the C-R criterion cannot be employed at branch points (for e.g.
a double root in the $\omega$ plane), the
algorithm can still educe such critical points. The mode-sorting algorithm
is explained in more detail in Sec. 2. We demonstrate the method on three
problems in Sec. 3. We use the algorithm to sort the temporal even
Orr-Sommerfeld (OS) modes that arise in a stability analysis of
Couette flow in 3.1. In 3.2, we apply the algorithm to sort the
jumbled eigenvalues in a model problem involving a cube-root branch point.
Finally, we sort the eigenpaths of two low dimensional
matrices in 3.3 and 3.4 and show how some currently available methods fail to
produce the correct eigenpaths.

\section{Mode sorting} \label{sec:mode}

\subsection{The algorithm}
SPEC-RE (Sorting Procedure for Eigenvalues based on Cauchy - Riemann Equations)
is based on a well-known result of function theory for polynomials \footnote{
 The roots of such polynomials are then analytic functions of the same parameter
 {\sl{with only algebraic singularities}} (p.64, \cite{Kato-1995}.)}
whose coefficients are analytic functions of a parameter.
Thus, the eigenvalue $\omega_j$ is an analytic function
 of the complex wavenumber $\alpha$ except at isolated branch points.  At any
such point of analyticity $\alpha=\alpha_p$, the quantity
 $$\displaystyle  F=\left|\frac{\partial{\mathcal{R}e}(\omega_j)}{\partial
\alpha_r}-
\frac{\partial{\mathcal{I}m}(\omega_j)}{\partial\alpha_i} \right|+
 \left|\frac{\partial{\mathcal{R}e}(\omega_j)}{\partial\alpha_i}+\frac{\partial{
\mathcal{I}m}
(\omega_j)}{\partial\alpha_r} \right|$$ has to be negligible
 since Cauchy-Riemann conditions for analytic functions have to be satisfied. In
 what follows, this quantity $F(\omega_j;\ \alpha_p)$ is called the CR residue.

The primary task of SPEC-RE is to sort each eigenvalue of the spectrum
from a given initial point in the $\alpha$ plane by minimization of the CR
residue at the points of analyticity.
The algorithm makes use of the negation of the CR criterion at the branch
points rather than prescribing a `method' to identify branch points. The
primary feature of the algorithm, for analytic points, is described in 2.2;
how the algorithm can educe non-analytic points like branch points is
explained in 2.3 and 2.4.
\begin{figure}
\centering
\includegraphics[width=4in]{grid.eps}
\caption{Schematic to explain mode sorting around a BP $\alpha_b$ by the
algorithm SPEC-RE.}
\end{figure}
\subsection{Computation of analytic traces}
 The computational domain is a rectangular patch in the $\alpha$ plane with
edges parallel to the axes. The grid points are equally spaced along both the
axes; however, the grid size in these directions may be different. The sorting
algorithm is implemented on a 4-point stencil of this grid (dashed line in
figure 1(a)); at any given pivot point $\alpha_{n,m}=(\alpha_r,\alpha_i)$
 the stencil consists of the neighbouring points $\alpha_{n-1,m} = (\alpha_r
- \delta \alpha_r, \alpha_i)$, $\alpha_{n+1,m}= (\alpha_r +
\delta \alpha_r,\alpha_i)$ and $\alpha_{n,m+1}=(\alpha_r,\alpha_i+\delta
\alpha_i)$. Given a particular eigenvalue
$\omega_j$ at $\alpha_{n,m}$, the algorithm is designed to pick one (and only
one) of the eigenvalues from the spectrum at two neighbouring points
$\alpha_{n+1,m}$ and $\alpha_{n,m+1}$
 such that the CR condition at $\alpha_{n,m}$ is satisfied. Equivalently, the
relevant complex derivatives at $\alpha_{n,m}$ must make the CR residue $F$
 to be negligible.  In the numerical procedure, these derivatives
are replaced by the central and forward differences
 $$\frac{\partial\omega_j}{\partial\alpha_r}=\frac{\omega_l(\alpha_{n+1,m})-
\omega_j(\alpha_{n-1,m})}{2 \delta\alpha_r},\   l=1,2,3,...$$
 $$\frac{\partial\omega_j}{\partial\alpha_i}=\frac{\omega_k(\alpha_{n,m+1})-
\omega_j(\alpha_{n,m})}{i\delta\alpha_i}, \  k=1,2,3,...$$
 \noindent The CR residue $F(\omega_j;\ \alpha_{n,m})$ is defined using these
central-forward differences and is actually a set of numbers
$F_{l
k}(\omega_j;\alpha_{n,m}) ; \ l=1,2,3,... \
 k=1,2,3,... $ .The indices $k_p$ and $l_p$  that correspond to the minimum of
these numbers for a given $j$, which is expected to be a negligible quantity,
are picked.  As the analyticity condition
  for $\omega_j$ at $\alpha_{n,m}$ is numerically satisfied between $\omega_j,
\omega_{l_p}$ and $\omega_{k_p}$, all three $\omega$s belong to the same
analytic function.
  In other words,
\begin{gather}
 \omega_j(\alpha_{n+1,m})=\omega_{l_p}, \tag{a}  \\
\omega_j(\alpha_{n,m+1})=\omega_{k_p}. \tag{b}
\end{gather}
  \noindent The pivot point can then be moved to one of the two adjacent points
either in the horizontal direction or the vertical
direction and the sorting procedure can be repeated for the new stencil.
Hence, starting from an initial point $\alpha_0$, the sorting procedure
picks one and only one value from the spectrum at each grid point and assigns
it to the $j$th collection
so that an analytic function $\omega_j(\alpha)$ is constructed, on the entire
rectangular patch in the $\alpha$ plane.
\subsection{Sweep direction}
In a horizontal sweep, the pivot point $\alpha_{n,m}$ moves along the direction
of increasing $\mathcal{R}e(\alpha)$, keeping $\mathcal{I}m(\alpha)$ constant.
After reaching the right-most point of the grid, the pivot point is moved to
 $\alpha_{1,m+1}$. Further computations are performed on stencils containing
$\alpha_{n,m+1}, \alpha_{n+1,m+1}$ and $\alpha_{n,m+2}$ starting from $n = 1.$
It may be noted that the eigenvalues at this level have already been sorted
from the computation at the $m$-th level, as shown in equation (b). Hence,
using the eigenvalues at the $m + $1-st level, either (i) $\omega_j$ at the
$m + 2$-nd level may be sorted, or (ii) re-sorting may be done afresh at the
$m+1$-st level.
Method (ii) will not produce any new arrangement\footnote{Re-sorting leads to a
re-arrangement of the eigenvalues, but, the re-arrangement may be the same as
the existing one.} of eigenvalues at the $m+1$-st level
 unless a branch point lies between the $m$-th and the $m+1$-st
levels. Eduction of a branch cut along the sweep direction (horizontal) by
Method (ii) will be explained in the following subsection.

The sweep direction is not rigidly fixed. A vertical sweep, for instance, will
produce a different modal map, with vertical branch cuts. One could
indeed sweep even along any family of parametric curves; the C-R equations
would then have to be
satisfied in the appropriate coordinates.

\subsection{Mode sorting around a branch point}
Assume that there exists a branch point between $\omega_j$ and $\omega_{j+k}$
located in the box formed by the $m$-th, $m+1$-st, $n$-th and $n+1$-st lines as shown in figure 1 (
i.e. $\omega_j(\alpha)$ and $\omega_{j+k}(\alpha)$ intersect at some
$\alpha_b$).
By design, the sorting algorithm produces an analytic $\omega_j$ not only
up to the $m$-th line, but also upto the point $\alpha_{n+1,m+1}$ on the
$m+1$-st line.  At the stencil formed by $\alpha_{n+1,m} $, $\alpha_{n+2,m}
$ and $\alpha_{n+1,m+1} $,
application of CR condition forces analyticity of $\omega_j$
 at both edges of the stencil and hence, does not allow the BC to cut the
$\alpha_{n+1,m} $ - $\alpha_{n+1,m+1} $ edge. The forcing of analyticity on the
lower and left edges of the box by the previous stencil leads to the BC
cutting the $\alpha_{n,m+1} $ - $\alpha_{n+1,m+1}$ edge, as shown
 in figure 1(a).
 If further computations were to be done using Method (i) to sort eigenvalues at
the $m+2$-nd level, application
of the CR condition for the stencil at $\alpha_{n,m+1}$ will be erroneous due
to the aforementioned  non-analyticity  at the $\alpha_{n,m+1} $ - $\alpha_{n
+1,m+1} $ edge. By Method (ii), $\omega_j$ values along
that line are rearranged and analytic sorting between $\omega_j(\alpha_{n,m+1})$
and $\omega_j(\alpha_{n+1,m+1})$ is ensured. Analyticity along this edge forces
non-analyticity of $\omega_j$ along the  $ \alpha_{n+1,m}$ -
$ \alpha_{n+1,m+1}$ edge, which is equivalent to the BC being horizontal in that
grid box as shown in figure 1(b). By continuation of the horizontal sweep at
the $m+1$-st level, a horizontal BC evolves naturally.
A vertical sweep, together with the application of
Method (ii) in the vertical direction would produce a vertical BC.
It should, in principle, be possible to modify the algorithm to obtain a
branch cut along a suitable complex curve from the branch point by allowing
non-analyticity at suitable edges of the stencils while sweeping. Such an
improvement will be useful in situations when some points in the $\alpha-$plane
are needed to be retained in an analytic region. However, it is not done here.
\section{Results \& Discussion}
We now present some results obtained using SPEC-RE in a few problems. We
start with a well-known problem from fluid mechanics.
\subsection{Sorting of modes in a physical problem}
The Orr - Sommerfeld (OS) equation is the basic equation of linear stability
analysis of parallel shear flows and is given by \cite{Schmid-2001}
\begin{gather}
\bigg{[} i \alpha U (D^2 - k^2) - i \alpha D^2 U - \frac{1}{Re} (D^2 - k^2)^2
\bigg{]} v = i \omega (D^2 - k^2) v
\end{gather}
where $U(y)$ is the base streaming flow, $\alpha$ is the streamwise wavenumber,
$k^2 = \alpha^2 + \beta^2$ where $\beta$ is the spanwise wavenumber, $D$ is
differentiation wrt $y, Re $ is the Reynolds number and $\omega$ the frequency.
$v$ is the normal perturbation velocity.
\begin{figure}
\centering
\includegraphics[width=5in]{couette_4modes.eps}
\caption{Temporal maps (Example 3.1) of the region $\textit{R} = [0,0.5] \times
[0,0.5]$ in the $\alpha$ plane. a) mode 1 b) mode 2 c) mode 3 d) mode 4.
The red circles indicate starting points of the trajectories. `C' and `D'
indicate cusps and double roots respectively.}
\end{figure}

For a given $U(y)$, a Chebyshev discretisation of Eq.(1) results in a NDR
which can then be solved for either $\alpha$ or $\omega.$ We solve for
We solve for $\omega$ and sort the temporal eigenvalues, into temporal
eigenmodes for the Couette flow $U(y) = y, y \in [1-,1]. \beta = 0$ is assumed.
We show in figure 2, the maps of the region $ \textit{R} = [0,0.5] \times
[-0.5,0.5]$ (in the
$\alpha$ plane ) for the lowest four OS modes. The maps are analytic at
almost all points, the only exceptional points being those at which branching
occurs. It is easy to see that basing the sorting on the real or imaginary parts
of $\omega$ will fail. Even other methods suggested in \cite{Suslov-2006}
fail, as detailed there (figure 1 of that paper), though this has not been
shown here.

\subsection{A model problem with a higher order branch point}
 \begin{figure}
\centering
\includegraphics[width=4.0in]{cuberoot_jumble.eps}
\caption{Three branches of $f(z) = z^{1/3}$ presented in jumbled form.}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=4.0in]{cuberoot_sort.eps}
\caption{SPEC-RE sorts the three branches correctly.}
\end{figure}
The previous example educed square-root branch points.
The sorting algorithm, in general, can also educe higher order branch points.
In this section, the applicability of SPEC-RE around a cube root branch point
is demonstrated. Here, the $\omega_j, \ \ j=1,2,3$ are the three branches of
the complex function (which can be thought as a factor in a
characteristic polynomial) $f(z)=z^{1/3}$. The grid size is chosen as
$(\delta\alpha_r,\delta
\alpha_i) = (5e-4,5e-4)$ The three sets of $\omega$s are randomly jumbled at
every point in the $\alpha$ plane, as shown in
figure 3, and then read by the sorting program. The three sets of sorted
values under a horizontal sweep are shown in different colors in figure 4.
\begin{figure}[h]
\centering
\subfigure[]{
\includegraphics[width=2.5in]{shuffle.eps}}
\hspace{0.1in}
\subfigure[]{
\includegraphics[width=2.5in]{specre.eps} }
\caption{Eigenmodes produced by sorting schemes (a) $S_4$  and (b) SPEC-RE.
$S_4$ interchanges the eigenvalues beyond the degenerate point $\alpha = 0.5$
whereas SPEC-RE sorts them correctly.}
\end{figure}

\subsection{$2 \times 2$ normal and non-normal matrices}
For the next example, we use two simple $2 \times 2$ matrices, given by
\begin{gather*}
A_1 = \begin{bmatrix}
\alpha & 0 \\
0 & 1 - \alpha \end{bmatrix}, \,\,
A_2 = \begin{bmatrix}
\alpha & 0 \\
\epsilon & 1 - \alpha \end{bmatrix},
\end{gather*}
where $\alpha \in [0,1]$ and $\epsilon$ is a fixed positive number. Note that
$A_1$ is normal whereas $A_2$ is non-normal; they have the same eigenvalues
$\omega_1 = \alpha$ and $\omega_2 = 1 - \alpha$ however. Sort $S_3$ fails to
produce $\omega_1$ and $\omega_2$ for both $A_1$ and $A_2$.
Sort $S_4$ produces the correct eigenpath for $A_1$ but fails for $A_2.$
SPEC-RE produces the correct
sort in both cases. The correct eigenpaths and the mis-sorted ones are shown
in figure 5, for $\epsilon = 0.1$.
$A_2$ has defective eigenvalues, and consequently a
generalised eigenvector, at $\alpha = 0.5$; $S_4$ which makes use of both
eigenvalue and eigenvector distance fails to sort correctly. In general, $S_4$
is expected to fail in such defective situations. This leads us to our last
example involving a $5 \times 5$ matrix.
\subsection{A $5 \times 5$ matrix with defective eigenvalues}
Consider the $5 \times 5$ matrix whose non-zero elements are given by
\begin{gather*}
B(1,1) = \alpha (1 + i) + \alpha^2, \, B(2,2) = \alpha(- \cos \theta_1 + i
\sin \theta_1) + \alpha^2, \,\, B(3,3) = \alpha (- \cos \theta_2 + i
\sin \theta_2) + \alpha^3, \\
B(4,4) = \alpha (\cos \theta_3 - i \sin \theta_3) + \alpha^4, \,\,
B(5,5) = \alpha ( \cos \theta_4 + i \sin \theta_4) + \alpha^5, \\
{\rm{and}} \,\,B(2,1) = B(3,2) = B(4,3) =
B(5,4) = 0.1.
\end{gather*}
$\theta_1 = 3 \pi / 20, \theta_2 = 11 \pi / 20, \theta_3 = 7 \pi / 20,
\theta_4 = \pi / 20$ and $B(i,i)$ have been chosen to produce a quintuple
eigenvalue of 0 at $\alpha = 0.$ $\alpha \in [-1,1].$ The results of sorting by
eigenshuffle and by the current algorithm
SPEC-RE are shown in figure 6(a,b) respectively. The starting
eigenvalues, for $\alpha = -1$ are marked with a star in fig 6(a) and the
end eigenvalues, for $\alpha = 1$ are marked with a circle in fig 6(b).
$S_4$ jumbles the eigenvalues at the defective point (fig 6(a)), so that the
green curve
continues as red, the blue as black, the black as magenta, the red as blue and
finally the magenta as green. SPEC-RE maintains the correct eigenvalue
positions for the entire $\alpha$ range (fig 6(b)).
\begin{figure}[h]
\centering
\subfigure[]{
\includegraphics[width=2.5in]{shuffle5curve.eps}}
\hspace{0.1in}
\subfigure[]{
\includegraphics[width=2.5in]{specre5.eps} }
\caption{Eigenmodes of the $5 \times 5$ matrix $B$ of Example 3.4. The
parameter $\alpha \in [-1,1].$ Sorting scheme $S_4$ produces the eigenpaths in
(a). Clearly, there is a mix-up of the modes beyond the quintuple root $\alpha
= 0.$ SPEC-RE produces the five correct eigenpaths in (b). The five eigenvalues
at $\alpha = -1$ are marked
with a star in (a) and at $\alpha = 1$ by a circle in (b).}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=3.0in]{five2one_roots.eps}
\caption{Use of an L stencil in Example 3.4 results in missing eigenmodes
beyond the quintuply degenerate eigenvalue at zero.}
\end{figure}
The last two examples show how true crossings can be misinterpreted as
avoided crossings (of the sharp kind) if the sorting is not proper. This
could lead to a wrong inference of eigenstate exchange when none exists.
In systems which allow both C3A and C3B type crossings, this could lead to
misidentification of eigenmodes leading to wrong conclusions.

For the application of this algorithm, the initial sorting point should be a
point where all eigenvalues are simple. The C-R equations involve first order
derivatives in two directions; a numerical implementation could, in principle
use finite differences of any order.
For sorting at the point next to the initial one, we use a 3-point L stencil
(forward differences in both directions) and 4-point T stencils (central
difference in the sweep direction and forward in the other) for the
subsequent grid points. The T stencil is found to be necessary as the L
stencil can result in improper sorting under certain circumstances, for
example, if a grid point corresponds to a multiple eigenvalue. In the latter
case, the same mode can be picked multiple times since the mode is chosen
based on the forward difference, which involves the multiple eigenvalue, at
which grid point the modes are indistinguishable. A T stencil avoids this by
including an upstream value as well, by using a central difference. Usage of
an L stencil in Example 3.4 results in the wrong eigenmodes shown in figure 7.

\section{Conclusion} \label{sec:conclusion}

An algorithm SPEC-RE, based on the analytic structure of the dispersion
relation, has been devised to sort complex eigenvalues into modal
families. The method makes full use of the fact that the eigenvalues are
analytic functions of the parameters, something that the methods currently in
existence do not.
Collisions of eigenvalues, whether false or true, are handled easily
unlike say in \cite{Suslov-2006}. The method can be easily extended to
multi-parameter mode sorting, with the C-R criterion being applied with respect
to one parameter at a time, with all other parameters kept fixed. Even
generalised eigenvalue problems of polynomial type are amenable to this method
because these can be transformed to linear
eigenvalue problems which standard routines can solve. This algorithm can be
even used to sort numbers that are not necessarily eigenvalues, as long as they
are obtained by an analytic process, for e.g. they could be roots of a
transcendental equation.

\section*{Acknowledgments}

The support of National Board of Higher Mathematics, India is gratefully
acknowledged.

config: arxiv


TITLE: How to prove this property about a measurable function f
QUESTION [1 upvotes]: Let $\mathcal{A}$ be a $\sigma$-algebra in $X$ and $f:X \to \mathbb{R}^N$ a measurable function. Prove that $G\subset \mathbb{R}^N$ open $\implies f^{-1}(G) \in\mathcal{A}$.
My attempet: If we write $f(x)=(f_1(x),\dots, f_N(x))$ where $f_i:X \to \mathbb{R}$, we have that
$$ f_i=P_i \circ f$$ where $P_i:\mathbb{R}^N \to \mathbb{R}$ is the projection of the $i$-coordinate. Since $P_i$ is continuous and an open map it's true that $P_i(G)=A \subset \mathbb{R}$ open and then follows that
$$f_i^{-1}(A)=f^{-1}(P^{-1}_i(A))). $$
By the description of the open sets in $\mathbb{R}$ we can write $A$ as an disjoint countable union of open intervals and maybe with some work we can prove by this that $f^{-1}_i(A) \in \mathcal{A}$. The real problem here is that it's not true that $P^{-1}_i(A)=G$. There is a way to make this argument work?

REPLY [1 votes]: Any open set $G$ in $\mathbb R^{n}$ is a union of sets of the type $(a_1,b_1)\times (a_2,b_2)\times \cdots \times (a_n,b_n)$ with $a_i, b_i \in \mathbb Q$ for each $i$. Since $f_i^{-1}(a_i,b_i) \in \mathcal A$ for each $i$ it follows that $f^{-1}(G) \in  \mathcal A$.


TITLE: Prove that if the row vectors of a $n\times n$ matrix spans $\mathbb{R}^n$, then the columns are linearly independent
QUESTION [1 upvotes]: I was able to prove that if a $n \times n$ matrix has linearly independent columns, then the row vectors span $\mathbb{R}^n$. However, I am unsure how to prove the other way. So far, my proof is:
Let the row vectors of A be $\vec r_{1},...,\vec r_{n}$. Then, $ span(\mathbb{R}^n)=\{\vec r_{1},...,\vec r_{n}\}$ and there exists some scalars $c_{1},...,c_{n}$ such that $c_{1} \vec r_{1}+...+c_{n}\vec r_{n}=\mathbb{R}^n$
I don't know if what I have done so far is correct.
Thanks in advanced for you help.

REPLY [0 votes]: if $R_i = \sum\limits_{j=1}^{n} a_{i,j} e_{i,j}$ for $ 1 \leq i \leq n$ are $n$-linearly  independents row vectors that span $\mathbb{R}^n$, then $C_j = \sum\limits_{i=1}^{n} a_{i,j} e_{i,j}$ are $n$-linearly independents column vectors that span $\mathbb{R}^n$. Let $x=\sum\limits_{i=1}^{n} \lambda_i R_i \in \mathbb{R}^n$,  we have:
\begin{align}
x &=\sum\limits_{i=1}^{n} \lambda_i R_i\\
& = \sum\limits_{i=1}^{n}\lambda_i \sum\limits_{j=1}^{n} a_{i,j} e_{i,j}\\
& = \sum\limits_{j=1}^{n}\lambda_j \left(\sum\limits_{i=1}^{n} a_{i,j} e_{i,j}\right)\\
& = \sum\limits_{j=1}^{n}\lambda_jC_j
\end{align}
We can change indexation of $\lambda_i$ to $\lambda_j$ and switch the sum signs because they are a finite sums.


TITLE: Simple integration problem
QUESTION [2 upvotes]: I need to find the work done by some stationary particle on another. The work is defined as a scalar product of force and displacement ($W=\int_{}^{} \vec{F} \cdot d \vec{r}$). The force is inversely proportional to the square of distance between the two particles: $F=k/r^2$ where $k>0$.

Suppose the stationary particle is located at $r=a$. The other particle is located at $r=0$. Then the initial distance between them is $|\vec{r_0}|=a$. Later the other particle reaches some point where the distance between them is $r_1$. All the vectors here are in the direction of the $r$ axis, so they are all positive. Then the work done by the force $F$ is:
$$
W=\int_{r_0}^{r_1} \frac{k}{r^2} dr = -\frac{k}{r_1}-\left(-\frac{k}{r_0} \right)
$$
But it turns to be wrong. The correct work should be $-\frac{k}{r_0}-\left(-\frac{k}{r_1} \right)$, that is the negative of my $W$. Where I messed up the signs?

REPLY [0 votes]: It's just that your $dr$ should be $-dr$ as you are decreasing $r$.
You can always check your answer whether it is positive or not. If Force and displacement are in same direction, work done by force must be positive...


TITLE: Show that $\int_2^{+ \infty} \frac{\log(t)^2}{t(t-1)}dt \leq 4$
QUESTION [1 upvotes]: I couldn't prove this inequality
$$
\int_2^{+ \infty} \frac{\log(t)^2}{t(t-1)}dt \leq 4
$$
I've tried integration by parts but it doesn't work.

REPLY [1 votes]: We have
\begin{align*}
 \int_2^\infty \frac{\ln^2 t}{t(t - 1)}\,\mathrm{d} t
 & \overset{t = 1/x} =
 \int_0^{1/2} \frac{\ln^2 x}{1 - x} \,\mathrm{d} x \\
 &\le \int_0^{1/2} \frac{\ln^2 x}{1 - 1/2} \,\mathrm{d} x\\
 &= 2\int_0^{1/2} \ln^2 x \,\mathrm{d} x\\
 &= \ln^2 2 + 2 + 2\ln 2\\
 &< 4.
\end{align*}


TITLE: How to find a perpendicular line from a point to a line.
QUESTION [1 upvotes]: I have something i am trying to take a consistent measurement of, but the issue is that the sample is not always consistent with rotation.
However from the sample I have a point, and 2 parallel lines.
Given A as the reference point, | | are lines B & C respectively, and D is the measurement point, it would look something like this.
            B   C
            |   |
    A-------| D |
            |   |

I need to find a way to make sure that the point D in-between lines B & C is always consistent, regardless of rotation, using the reference point A.
So my thought is to make a line that intersects Line B from Point A.
This Line must be made to always be perpendicular.
I then take the middle point of this new line that falls in-between lines B & C which will always give me a consistent location for D.
Only how do I figure out the slope to give the line from point a to Line B so that the line is perpendicular to Line B and C?

REPLY [0 votes]: The distance from point $A$ to line $B$ is minimized when the line through $A$ is perpendicular to line $B$.
Given the slope $m$ of line $B$, use slope $-{1\over m}$ (the slope at which the lines will be perpendicular) and find the line with that slope that passes through point $A$ (located at $(x_0,y_0)$):
$$(y-y_0)=-{1\over m}(x-x_0)$$
Solving for the $b$ term in the form $y=ax+b$:
$$y=-{1\over m}x+{x_0\over m}+y_0$$
In other words, $b={x_0\over m}+y_0$.


TITLE: Failing To Frame Convex Non-Linear Problem as SOCP
QUESTION [0 upvotes]: I'm trying to reproduce an equation from equation 5 in the paper here:
https://web.stanford.edu/~boyd/papers/pdf/rob_downlink_bf.pdf
The equation is an SOCP of the form:
$\sqrt{1+\frac{1}{\gamma}}*\Re(\bar{h_i^*}\omega_i) \ge \sqrt{\sum_{j=1}^{m}|\bar{h_i^*}\omega_j|+\sigma^2}$ (1)
$\Im(\bar{h_i^*}\omega_i) == 0$ (2)
Where $\sigma$ is a constant and $\omega$ is a complex matrix to optimize over. The RHS of equation (1) is just the 2-norm of that vector.
Gurobi only takes SOCP problems of the form:
$x^Tx \le y^2$
As mentioned here: http://www.gurobi.com/documentation/6.0/refman/cs_grbmodel_addqconstr.html
So I need to convert the form above into that. I squared each side such that
$x^Tx$ is now simply the magnitude of each element, or $(\Re(\bar{h_i^*}\omega_j)^2 + \Im(\bar{h_i^*}\omega_j)^2$, where $\bar{h_i^*}\omega_j$ is a symbolic expression. Similarly, for the RHS to be in the form of $y^2$ I set
$y = (1+1/\gamma)\Re(\bar{h_i^*}\omega_i)^2$
$\gamma$ is a constant, and again $\bar{h_i^*}\omega_i$ is a symbolic matrix. Since Gurobi doesn't support complex numbers, my matrix looks like this for the 2x2 case:
$\omega = \left\lgroup
\matrix{\omega{x}_{00} + \omega{y}_{00}i & \omega{x}_{01} + \omega{y}_{01}i\cr \omega{x}_{10} + \omega{y}_{10}i & \omega{x}_{11} + \omega{y}_{11}i}
\right\rgroup$
Where x are the real variables and y are complex. My h matrix looks like this:
$h = \left\lgroup
\matrix{-0.1288 - 0.3574i & -0.0605 + 0.5454i\cr -1.0419 + 0.3075i & -0.7424 - 1.4344i}
\right\rgroup$
When multiplying out the symbolic matrices and feeding it into Gurobi, it reports that the Q matrix is not positive semi-definite. This is odd first of all because Gurobi thinks it's a QP problem and not SOCP. When I look at the equations I'm passing in from the LP file, Q is indeed not positive semidefinite.
$ qp0: - 0.3574 w_x_0_0 - 0.1288 w_y_0_0 + 0.5454 w_x_1_0
   - 0.0605 w_y_1_0 = 0
 qp1: [ - 0.0234610110401747 w_x_0_0 ^ 2
   + 0.130201325244696 w_x_0_0 * w_y_0_0
   - 0.0220402355268722 w_x_0_0 * w_x_1_0
   - 0.19868999101415 w_x_0_0 * w_y_1_0 - 0.180644229978472 w_y_0_0 ^ 2
   + 0.0611582311902494 w_y_0_0 * w_x_1_0
   + 0.551333872581191 w_y_0_0 * w_y_1_0 + 0.1443242 w_x_0_1 ^ 2
   - 0.37426712 w_x_0_1 * w_x_1_1 + 0.18374044 w_x_0_1 * w_y_1_1
   + 0.1443242 w_y_0_1 ^ 2 - 0.18374044 w_y_0_1 * w_x_1_1
   - 0.37426712 w_y_0_1 * w_y_1_1 - 0.00517637519167612 w_x_1_0 ^ 2
   - 0.0933287613071126 w_x_1_0 * w_y_1_0 - 0.420673606751233 w_y_1_0 ^ 2
   + 0.30112141 w_x_1_1 ^ 2 + 0.30112141 w_y_1_1 ^ 2 ] <= -1
 qp2: 0.3075 w_x_0_1 - 1.0419 w_y_0_1 - 1.4344 w_x_1_1
   - 0.7424 w_y_1_1 = 0
 qp3: [ 1.18011186 w_x_0_0 ^ 2 + 0.66485712 w_x_0_0 * w_x_1_0
   - 3.44557872 w_x_0_0 * w_y_1_0 + 1.18011186 w_y_0_0 ^ 2
   + 3.44557872 w_y_0_0 * w_x_1_0 + 0.66485712 w_y_0_0 * w_y_1_0
   - 1.5352074663722 w_x_0_1 ^ 2 - 0.906183503041465 w_x_0_1 * w_y_0_1
   - 2.18780693547312 w_x_0_1 * w_x_1_1
   + 4.22708818459407 w_x_0_1 * w_y_1_1 - 0.133722731157141 w_y_0_1 ^ 2
   - 0.645695971454058 w_y_0_1 * w_x_1_1
   + 1.2475569793288 w_y_0_1 * w_y_1_1 + 2.60866112 w_x_1_0 ^ 2
   + 2.60866112 w_y_1_0 ^ 2 - 0.7794547791991751 w_x_1_1 ^ 2
   + 3.01198797220716 w_x_1_1 * w_y_1_1 - 2.90974915634021 w_y_1_1 ^ 2 ]
   <= -1$
Does anyone have an idea of where I can debug this going wrong? When I feed the same problem into CVX (but using things like norm()) it finds a valid solution, but the transformation of the problem is very slow. I would like to go directly to the solver and skip the transformation step if possible.

REPLY [0 votes]: you can try to transform the SOCP problem to SDP problem and use the standard solver (such as CVX) to solve the SDP problem