\section{Introduction}
Quantum groups first appeared in the study of quantum integrable
systems. Since then, they have proven useful in many applications,
including among others conformal field theory, statistical mechanics,
representation theory and the theory of hypergeometric functions, along
with exhibiting a rich internal structure. Quantum groups have appeared
seminally in the mathematical physics literature in connection with
topological quantum field theory~\cite{witten}. More recently, the
quantum group $\mathrm{su}_q(2)$ was used to construct ``loop''~\cite{smolin} and
``spin foam''~\cite{KC} models of quantum gravity with a positive
cosmological constant.

The $6j$-symbol (or Racah-Wigner coefficients and henceforth the $6j$ or
the $q$-$6j$ for the classical and $q$-deformed versions respectively)
has been studied extensively. It first appeared in work on
$q$-hypergeometric functions~\cite{AW-rec}. Later, it was found to play
a central role in the representation theory of $\mathrm{su}_q(2)$~\cite{KR-q6j}.
It is known to satisfy some recurrence relations~\cite{AW-rec,KK-rec},
including a particular linear, three term, single argument
one~\cite{KR-q6j,MT-ptps,MT-prl}. This recurrence has been used to
analyze the asymptotics of the classical~\cite{PR,SG-rec} and
quantum~\cite{WT} $6j$.

However, this $q$-$6j$ and the need to know its numerical values for a
large number of arguments also appear in other segments of the
literature~\cite{KC,RRS}, less aware of these properties.
An explicit formula for the $q$-$6j$ is well known and involves
a number of arithmetic operations that is linear in its arguments (see
Appendix). In applications where a large number of $6j$-symbols is
needed at once, e.g.,\ for all values of one argument with others fixed
as is the case in~\cite{KC}, the total number of operations becomes
quadratic in the arguments. The above mentioned recurrence relation can
be used to greatly increase the efficiency of the calculation by
reducing the total operation count to be linear in the arguments. The
main goal of this paper is to show that, moreover, this recurrence can
be realized as a tridiagonal, symmetric eigenvalue problem, a property
not shared by most recurrence relations, especially since the
equivalence is established using only rational operations.

A significant advantage of the eigenvalue formulation is the ability to
make use of readily available, robust linear algebra packages, such as
LAPACK~\cite{Lap}, which automatically take care of the important issues
of numerical accuracy and stability. When $q=1$ or when $q$ is a
primitive root of unity, the relevant inner product becomes either
positive- or negative-definite and standard, specialized numerical
methods can be exploited to increase the efficiency of the calculation
even further. A secondary goal of this paper is to concisely collect all
the relevant information needed to readily implement such an efficient
$q$-$6j$ numerical evaluation algorithm without intimate familiarity
with the literature on quantum groups or $q$-hypergeometric functions.

Sections~\ref{sec:spinnet} and~\ref{sec:ident}, which can be skipped by
those familiar with the mathematical literature on $\mathrm{su}_q(2)$ recoupling
theory, introduce the basic notions of the spin network
formalism~\cite{Pen,KL,CFS}, define the Kauffman-Lins convention for the
$6j$-symbol and summarize basic diagrammatic identities needed for
Section~\ref{sec:rec}, where the recurrence relation is realized as an
eigenvalue problem. This is accomplished as a byproduct of an
alternative proof of the recurrence itself that generalizes the
classical argument from the Appendix of~\cite{SG-rec}. The diagrammatic
spin network formalism makes all intermediate calculations easy to check
and reproduce.  The Appendix conveniently summarizes all formulas needed
for a direct computer implementation of the recurrence-based evaluation
of the $q$-$6j$, including the connection between the Kauffman-Lins and
Racah-Wigner notational convention, which is traditionally used in
physics.

\section{Spin networks}\label{sec:spinnet}
In a variety of physical and mathematical applications, one often encounters
tensor contraction expressions of the form
\begin{equation}\label{tens-con}
	T_{j\cdots}^{lm\cdots}
		= A_{ij\cdots}^{kl\cdots} B_{k\cdots}^{im\cdots} \cdots Z_{\cdots}^{\cdots},
\end{equation}
where $T$, $A$, $B$, \ldots, $Z$ are invariant tensors, with each index
transforming under a representation of a group or an algebra. The
application at hand usually calls for evaluating $T$, or at least
simplifying it. An extensive literature on this subject exists for the
classical group $SU(2)$ or its Lie algebra, a subject known as
\emph{angular momentum recoupling}~\cite{Edm,YLV}. It is well known that
such tensor contractions can be very efficiently expressed, manipulated,
and simplified using diagrams known as \emph{spin networks}~\cite{Pen}.
Extensions of these techniques~\cite{KL,CFS} are also known for the
\emph{quantum} (or \emph{$q$-deformed}, since they depend on an
arbitrary complex number $q\ne0$) analogs, the quantum group $\mathrm{su}_q(2)$
or $U_q(su(2))$. The basics of this diagrammatic formalism, as needed
for the derivation of the recurrence relation, are given in this and
next sections. All relevant formulas, including explicit spin network
evaluations in terms of \emph{quantum integers} are listed in the
Appendix.

Single spin networks are edge-labeled graphs%
	\footnote{Spin networks are actually ribbon graphs, but since all
	diagrams in this paper are planar, the ribbon structure can be added
	through blackboard framing.}, %
where each vertex has valence either $1$ or $3$. General spin networks
are formal linear combinations of single spin networks. Edges
attached to univalent vertices are called \emph{free}. Spin networks
without free edges are called \emph{closed}. Conventionally, the labels
are either integers (\emph{spins}) of half-integers
(\emph{twice-spins}), which correspond to irreducible representations of
$\mathrm{su}_q(2)$.  Reference~\cite{KL} labels all spin networks with
twice-spins. Unless otherwise indicated, all conventions in this paper
follow~\cite{KL}.  Two spin networks may be equal even if not
represented with identical labeled graphs. A complete description of
these identities are given in~\cite{KL}
and~\cite{CFS}; their study constitutes \emph{spin network
recoupling} and is what allows us to equate%
	\footnote{A down-to-earth guide to this correspondence, for the
	classical $q=1$ case, can be found in Appendix~A
	of~\cite{CCK}. Complete details with proofs can be found
	in~\cite{CFS}.} %
spin networks with $\mathrm{su}_q(2)$-invariant tensors and their contractions.

In this correspondence, each index of a tensor, transforming under an
irreducible representation, corresponds to a spin network edge, labeled
by the same representation (free indices correspond to free edges). In
particular, a closed spin network corresponds to a complex number. Spin
networks form a graded algebra over $\mathbb{C}$ (as do tensors). The grading is
given by the number of free edges (free indices) and the product is
diagrammatic juxtaposition (tensor product).

\section{Diagrammatic identities}\label{sec:ident}
The spin networks with $n$ free edges  with fixed labels
(\emph{$n$-valent} spin networks) form a linear space with a natural
bilinear form (or inner product). Suppose that the free edges are
ordered in some canonical way, then, given two spin networks, we can
reflect one of them in a mirror and connect the free edges in order. The
value of the resulting closed spin network defines the bilinear form,
which is symmetric and non-degenerate~\cite{KL}.  We use the bra-ket
notation for this inner product $\braket{s'}{s}$, where $s$ and $s'$ are
two spin networks. We also let $\ket{s}$ stand for $s$ and $\bra{s'}$
for the reflection of $s'$. The existence of an inner product allows the
following identities, whose proofs can be found in~\cite{KL}.
For each identity, the corresponding well known fact of $SU(2)$
representation theory is given.

The space of $2$-valent spin networks, with ends labeled $a$ and $b$, is
$1$-dimensional if $a=b$, and $0$-dimensional otherwise.  For
non-trivial dimension, the single edge gives a complete basis and
therefore the \emph{bubble identity}:
\begin{equation}\label{bub-id}
	\bblob ~ = \delta_{ab} \frac{\bblobo}{\loopa} ~~ \bblobv ~ .
\end{equation}
This identity the diagrammatic analog of Schur's lemma for intertwiners
between irreducible representations.

The space of $3$-valent spin networks, with ends labeled $a$, $b$ and
$c$, is also $1$-dimensional if the triangle
inequalities~\eqref{tri-ineq} and parity constraints~\eqref{parity} are
satisfied, and $0$-dimensional otherwise, if $q$ is generic. When $q$ is
a primitive root of unity, the dimension also vanishes whenever the
further $r$-boundedness constraint~\eqref{r-bound} is violated. In the
case of nontrivial dimension, the canonical trivalent vertex gives a
complete basis and therefore the \emph{vertex collapse identity}:
\begin{align}\label{theta-id}
	\blobo ~ &= \frac{\blob}{\theta(a,b,c)} ~~ \blobv ~~, \\
	\theta(a,b,c) &= \thabc .
\end{align}
The normalization of the vertex, the value of the $\theta$-network, is
evaluated in Equation~\eqref{theta-def}. This identity is the diagrammatic
analog of the uniqueness (up to normalization) of the Clebsch-Gordan
intertwiner.

Now, consider the space of $4$-valent networks with free edges labeled
$a$, $b$, $c$ and $d$. There are two natural bases, the vertical
$\bra{l}$ and the horizontal $\ket{\bar{j}}$: 
\begin{equation}
	\lbasis \quad,\quad \jbasis ~~.
\end{equation}
The admissible ranges for $j$ and $l$, the dimension $n$ of this space,
and the conditions on $(a,b,c,d)$ under which $n>0$ are given by
Equations~\eqref{jmin} through~\eqref{abcdrbd}. The transition matrix
between the two bases is given by the so-called $\operatorname{Tet}$-network:
\begin{equation}
	\operatorname{Tet}(a,b,c,d;j,l) = \tetjl = \braket{\bar{j}}{l}.
\end{equation}
The coefficients expressing the vertical basis in terms of the
horizontal one define the \emph{$6j$-symbol}, which can be expressed in
terms of the $\operatorname{Tet}$-network:
\begin{align}\label{KL-6j}
	\ket{l} &= \sum_{j} \sixjkl{a}{b}{j}{c}{d}{l} \ket{\bar{j}}, \\
	\sixjkl{a}{b}{j}{c}{d}{l} &= \frac{\tetjl}{\thadj\thbcj}~\loopj~.
\end{align}
Note the subscript $KL$ for Kauffman-Lins, since this $6j$-symbol is
defined with respect to the conventions of~\cite{KL}. The
relation to the classical Racah-Wigner $6j$-symbol used in the physics
literature is given explicitly in Equation~\ref{RW-KL}.

\section{Recurrence relation for the $\operatorname{Tet}$-network}\label{sec:rec}
The identities given in the previous section allow an alternative,
elementary derivation of the three-term recurrence relation for the
$\operatorname{Tet}$-network, distinct from the standard one. The standard derivation
is given in~\cite{MT-ptps} and another is possible using the general
theory of recurrences for $q$-hypergeometric functions~\cite{KK-rec},
but neither directly yields the symmetric eigenvalue problem form.

It is easy to check, using the bubble identity, that both the vertical
and horizontal bases are orthogonal and that they are normalized as
\begin{align}
\label{norm-j}
	\braket{\bar{j}}{\bar{j}} &= \jnorm~ = \frac{\thbcj ~ \thadj}{\loopj}, \\
	\braket l l               &= \lnorm~ = \frac{\thabl ~ \thcdl}{\loopl}.
\label{norm-l}
\end{align}
Curiously, when these normalizations
are fully expanded using formulas from the Appendix,
they take
the form $(-)^\sigma P/Q$, where $P$ and $Q$ are products of positive
quantum integers. In both cases, $\sigma=(a+b+c+d)/2$, is an integer independent of
$j$ or $l$. When $q=1$ or when $q$ is a primitive root of unity, positive
quantum integers are positive real numbers. Hence the above inner
product is real and either positive- or negative-definite. On the other
hand, for arbitrary complex $q$, the normalizations~\eqref{norm-j}
and~\eqref{norm-l} can be essentially arbitrary complex numbers.

If we can find a linear operator $L$ that is diagonal in one basis, but
not in the other, then we can obtain $\braket{\bar{j}}{l}$ as matrix
elements of the diagonalizing transformation. Furthermore, if the
non-diagonal form of $L$ is tridiagonal, then the linear equations
defining $\braket{\bar{j}}{l}$ reduce to a three-term recurrence
relation.

We can construct such an operator by generalizing the argument for the
classical case, found in the Appendix of~\cite{SG-rec}.  For
brevity of notation, we introduce a special modified version of the
trivalent vertex:
\begin{equation}
	\Lvert .
\end{equation}
The unlabeled edge implicitly carries twice-spin $2$ and the bold dot
indicates the multiplicative factor of $[a]$.  Using it, we can define a
symmetric operator $L$. Its diagrammatic representation and its matrix
elements are given below.

The operator $L$ is diagonal in the $\ket{l}$-basis
and its matrix elements $L_{ll'} = \bra{l} L \ket{l'}$ are
\begin{align}
	L_{ll'} &= \Llmat~ = \frac{[a][b]}{\loopl}~\thcdl~\tetll~\delta_{ll'} \\
		&= \lambda(a,b,l) \braket{l}{l'} ,
\end{align}
with
\begin{equation}
	\lambda(a,b,l) =
		\frac{\left[\frac{a-b+l}{2}\right]\left[\frac{-a+b+l}{2}\right]
			-\left[\frac{a+b-l}{2}\right]\left[\frac{a+b+l}{2}+2\right]}{[2]} ,
\end{equation}
where we have evaluated $\operatorname{Tet}(a,a,b,b;l,2)$ as
\begin{equation}
	\label{tet-diag}
	\tetll = \frac{\thabl}{[a][b]} \lambda(a,b,l) .
\end{equation}
This result may be obtained directly from Equation~\eqref{tet-formula}, where
the sum reduces to two terms, or from more fundamental
considerations~\cite{MV}.
In the limit, $q\to 1$, the eigenvalues simplify to
$\lambda(a,b,l)=\frac{1}{4}[l(l+2)-a(a+2)-b(b+2)]$, which shows that the
operator $L$ is closely related to the ``square of angular momentum'' in
quantum mechanics, which was used to obtain the classical version of
this recurrence relation~\cite{SG-rec}.

On the other hand, in the $\ket{\bar{j}}$ basis, the operator
$L$ is not diagonal and the matrix elements
$\bar{L}_{jj'}=\bra{\bar{j}}L\ket{\bar{j}'}$, making use of the vertex
collapse identity, are
\begin{equation}
	\bar{L}_{jj'} = \Ljmat~ = \frac{[a][b]}{\thjjpp}~\tetaadjj~\tetbbcjj,
\end{equation}
with the special case $\bar{L}_{00}=0$. Fortunately, though
$\bar{L}_{jj'}$ is not diagonal, it is tridiagonal. This property is a
consequence of the conditions enforced at the central vertex in both
$\operatorname{Tet}$-networks above: the triangle inequality, $|j-j'|\le 2$, and the
parity constraint, which forces admissible values of $j$ to change by
$2$. If these conditions are violated, the matrix element
$\bar{L}_{jj'}$ vanishes.

The diagonal elements $\bar{L}_{jj}$ can be evaluated
using~\eqref{tet-diag}.
For the off-diagonal elements $\bar{L}_{j+2,j}=\bar{L}_{j,{j+2}}$
we also need
\begin{equation}
	\label{tet-offdiag}
	\tetadjj = \frac{1}{[a]}\left[\frac{a+d-j}{2}\right]~\thadjp,
\end{equation}
which can be obtained in the same way as~\eqref{tet-diag}. Finally,
we need the identities
\begin{equation}
	\thjjp = -\frac{[j+2]}{[2][j]}~\loopj
	\quad \text{and} \quad
	\thjjptwo = \loopjp \phantom{j+{}}.
\end{equation}
The $\ket{j}$-basis matrix elements can now be expressed as (again,
recall the special case $\bar{L}_{00}=0$)
\begin{align}
	\bar{L}_{jj} &= -\braket{j}{j} \frac{[2]\lambda(a,j,d)\lambda(b,j,c)}{[j][j+2]}, \\
	\bar{L}_{j,j+2} &= \braket{j{+}2}{j{+}2} \left[\frac{a+d-j}{2}\right]
			\left[\frac{b+c-j}{2}\right].
\end{align}

The transition matrix elements $\braket{\bar{j}}{l}$ can now be obtained
by solving an eigenvalue problem in the $\ket{\bar{j}}$-basis:
\begin{align}
	\bra{\bar{j}} L - \lambda_l \ket{l}
		&= \sum_{j'} \frac{\bra{\bar{j}} L - \lambda_l
\ket{\bar{j}'}}{\braket{\bar{j}'}{\bar{j}'}}
				\braket{\bar{j}'}{l}, \\
	0	&= \sum_{j'} \left(\frac{\bar{L}_{jj'}}{\braket{\bar{j}'}{\bar{j}'}}
				- \lambda_l\delta_{jj'}\right) \braket{\bar{j}'}{l}, \\
\label{tet-eig-rec}
	0 &= \sum_{j'} \left(\bar{L}_{jj'} - \lambda_l \braket{\bar{j}'}{\bar{j}'} \delta_{jj'}\right)
				\frac{\braket{\bar{j}'}{l}}{\braket{\bar{j}'}{j'}},
\end{align}
where $\lambda_l = \lambda(a,b,l)$. Since $\bar{L}_{jj'}$ is
tridiagonal, we obtain a three-term recurrence relation for the
$\braket{\bar{j}}{l}$ transition coefficients. Expanding the expression for
$\bar{L}_{jj'}$, we find the following general form of the recurrence
relation:
\begin{equation}%
\label{tet-rec}
	\frac{\bar{L}_{j,j-2}}{\braket{\overline{j-2}}{\overline{j-2}}}
			\braket{\overline{j-2}}{l}
	+ \left(\frac{\bar{L}_{jj}}{\braket{\bar{j}}{\bar{j}}}-\lambda_l\right)
			\braket{\bar{j}}{l}
	+ \frac{\bar{L}_{j,j+2}}{\braket{\overline{j+2}}{\overline{j+2}}}
			\braket{\overline{j+2}}{l}
	= 0,
\end{equation}
with the provision that $\bar{L}_{jj'}$ vanishes whenever either of the
indices fall outside the admissible range or $j=j'=0$. Finally, the transition
coefficients are uniquely determined (up to sign) by requiring the
normalization condition
\begin{equation}
	\sum_j \frac{\braket{l}{\bar{j}}\braket{\bar{j}}{l}}
		{\braket{\bar{j}}{\bar{j}}} = \braket ll.
\end{equation}
Practically, it is more convenient to recover the correct normalization
for all $j$ and fixed $l$, or vice versa, by requiring
$\braket{\bar{j}}{l}$ to agree with~\eqref{tet-formula} for $j=\underline{j}$,
cf.~\eqref{jmin}, where the sum reduces to a single term.

Once the $\operatorname{Tet}$-network has been evaluated recursively, the $6j$-symbol
can be obtained from Equation~\eqref{KL-6j}.  Alternatively, a linear,
three-term recurrence relation directly for the $6j$-symbol follows
from~\eqref{tet-rec} and the linear, two-term recurrence relations for
the bubble and $\theta$-networks, obvious from~\eqref{bub-def}
and~\eqref{theta-def}. However, because of the additional normalization
factors in Equation~\eqref{KL-6j}, this direct recurrence relation cannot be
cast in the form of a symmetric eigenvalue problem
like~\eqref{tet-eig-rec} using rational operations alone.

\ack
The author thanks Dan Christensen for many helpful discussions as well
as Nicolai Reshetikhin and an anonymous referee for pointing out
previous work on the above recurrence relation. In the course of this
work, the author was supported by Postgraduate (PGS) and Postdoctoral
(PDF) Fellowships from the Natural Science and Engineering Research
Council (NSERC) of Canada.

