\documentclass[12pt, notitlepage]{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathrsfs}
\usepackage{hyperref}
\usepackage[margin=1in]{geometry}

\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\title{\textbf{A GRAPH THEORETIC PROOF OF THE FUNDAMENTAL TRACE IDENTITY}}

\author{Hartmut LAUE\\[4pt]
\textit{Dipartimento di Matematica,}\\
\textit{Universit\`a degli Studi di Lecce, I-73100 Lecce, Italy}}
\date{Published in: \textit{Discrete Mathematics} \textbf{69} (1988), pp. 197--198.}

\begin{document}

% \noindent\textit{Discrete Mathematics} 69 (1988) 197--198\hfill 197\\ North-Holland

% \bigskip

% \noindent NOTE

% \bigskip

\maketitle

\medskip

\noindent Received 26 March 1986,
Revised 15 May 1987.\\
Digitized with Claude Opus 4.6 based on \href{https://doi.org/10.1016/0012-365X(88)90019-2}{a scan} from \href{https://www.elsevier.com/about/policies-and-standards/open-access-licenses/elsevier-user}{Elsevier Open Archive} \\(original scan: \href{https://doi.org/10.1016/0012-365X(88)90019-2}{doi:10.1016/0012-365X(88)90019-2}). \\
This is an unofficial re-edition of an article that appeared in an Elsevier publication. Elsevier has not endorsed this re-edition.\\
Proofread by Darij Grinberg 29 March 2026.

\medskip

{\small \noindent \textbf{Abstract.} To each circuit decomposition of a directed multigraph a permutation of the edge set is
assigned, and a lemma on the signs of the resulting permutations is proved yielding the
fundamental trace identity for matrices over a commutative unitary ring as a corollary.}

\bigskip

Let $\Gamma$ be a directed multigraph. A \textit{circuit decomposition} of $\Gamma$ is a set $D$ of
circuits\footnote{\textit{Comment by DG:} A \textit{circuit} means a closed walk with no repeated edges (but repeated vertices are allowed) that has at least one edge.
Circuits are viewed as lists of edges up to cyclic rotation (so $[\gamma_1, \ldots, \gamma_t]$ and $[\gamma_2, \ldots, \gamma_t, \gamma_1]$ are considered to be the same circuit).
} of $\Gamma$ such that each edge of $\Gamma$ occurs in exactly one element of $D$. Each
circuit $[\gamma_1, \ldots, \gamma_t] \in D$ determines a permutation of $\{\gamma_1, \ldots, \gamma_t\}$, viz.
\[
(\gamma_1, \ldots, \gamma_t) = \binom{\gamma_1, \ldots, \gamma_{t-1}, \gamma_t}{\gamma_2, \ldots, \quad \gamma_t, \gamma_1},
\]
and
\[
\sigma_D := \prod_{[\gamma_1,\ldots,\gamma_t] \in D} (\gamma_1, \ldots, \gamma_t)
\]
is a permutation of the edge set of $\Gamma$. Let
\[
\mathscr{C}(\Gamma) := \{\sigma \mid \sigma = \sigma_D \text{ for some circuit decomposition } D \text{ of } \Gamma\} .
\]

\begin{lemma}
If $\Gamma$ has more edges than vertices, then the number of even permutations
in $\mathscr{C}(\Gamma)$ is equal to the number of odd permutations in $\mathscr{C}(\Gamma)$.
\end{lemma}

\begin{proof}
By our hypothesis, there exist two distinct edges $\alpha$, $\beta$ which begin
at the same vertex. Let $\Delta$ be the set of all circuit decompositions $D$ of
$\Gamma$ with the property that $\alpha$, $\beta$ belong to the same circuit in $D$, and let $\Delta^*$
consist of the other circuit decompositions of $\Gamma$. Let $D \in \Delta$, and
$[\gamma_1, \ldots, \gamma_k, \alpha, \gamma_{k+1}, \ldots, \gamma_l, \beta, \gamma_{l+1}, \ldots, \gamma_m] \in D$.
Replacing this single circuit
by $[\alpha, \gamma_{k+1}, \ldots, \gamma_l]$ and $[\beta, \gamma_{l+1}, \ldots, \gamma_m, \gamma_1, \ldots, \gamma_k]$ yields a circuit decomposition $D^* \in \Delta^*$, and $\operatorname{sgn}(\sigma_{D^*}) = -\operatorname{sgn}(\sigma_D)$. It is easy to see that $\sigma_D \mapsto \sigma_{D^*}$ is a
bijection of $\{\sigma_D \mid D \in \Delta\}$ onto $\{\sigma_{D^*} \mid D^* \in \Delta^*\}$. The lemma follows. \qedhere
\end{proof}

\begin{corollary}[{cf.\ \cite{lew}, \cite[Theorem 4.3.(b)]{procesi1}}]
Let $R$ be a commutative ring with identity
$1$, and let $\mathscr{S}_k$ be the symmetric group on $\{1, \ldots, k\}$. If $k > n$, then for all $n \times n$ matrices $M_1, \ldots, M_k$ over $R$,
\[
\sum_{\sigma \in \mathscr{S}_k} \operatorname{sgn}(\sigma) \cdot \prod_{(i_1,\ldots,i_t)} \operatorname{Tr}(M_{i_1} \cdots M_{i_t}) = 0,
\]
where $(i_1, \ldots, i_t)$ ranges over the set of all cycles of the cycle decomposition of the
permutation $\sigma$.
\end{corollary}

\begin{proof}
We put
\[
\Phi_\sigma(M_1, \ldots, M_k) := \prod_{(i_1,\ldots,i_t)} \operatorname{Tr}(M_{i_1} \cdots M_{i_t}).
\]
Then $\Phi_\sigma$ is a $k$-fold $R$-linear mapping. Therefore we may assume that each $M_j$ is a
matrix whose only non-zero entry is a $1$, say, in the $(r_j, s_j)$-place. We define a
directed multigraph $\Gamma$ with vertex set $\{1, \ldots, n\}$ and with $k$ edges $\gamma_1, \ldots, \gamma_k$
such that $\gamma_j$ begins at $r_j$ and ends at $s_j$. Obviously, $\Phi_\sigma(M_1, \ldots, M_k) \neq 0$ if and
only if $\operatorname{Tr}(M_{i_1} \cdots M_{i_t}) \neq 0$, i.e., $s_{i_j} = r_{i_{j+1}}$ for $1 \leq j < t$ and $s_{i_t} = r_{i_1}$, for all cycles
$(i_1, \ldots, i_t)$ occurring in the cycle decomposition of $\sigma$. This is equivalent to
$\sigma = \sigma_D$ for some circuit decomposition $D$ of $\Gamma$. Therefore,
\[
\sum_{\sigma \in \mathscr{S}_k} \operatorname{sgn}(\sigma) \Phi_\sigma(M_1, \ldots, M_k) = \sum_{\sigma \in \mathscr{C}(\Gamma)} \operatorname{sgn}(\sigma) = 0,
\]
by the lemma. \qedhere
\end{proof}

The assertion of our Corollary plays a fundamental role in the theory of trace
identities (cf.\ \cite{procesi1,procesi2}). The graph theoretic approach in this note is closely related
to Swan's proof of the Amitsur--Levitzky identity \cite[I, Theorem~14]{bollobas}.

\begin{thebibliography}{9}

\bibitem{bollobas}
\href{http://doi.org/10.1007/978-1-4612-9967-7}{B.~Bollob\'as, \textit{Graph Theory} (Springer, Berlin, 1979).}

\bibitem{lew}
\href{https://doi.org/10.1007/BF01597249}{J.S.~Lew, The generalized Cayley--Hamilton theorem in $n$ dimensions, Z.~Angew.\ Math.\ Phys.~17
(1966) 650--653.}

\bibitem{procesi1}
\href{https://doi.org/10.1016/0001-8708(76)90027-X}{C.~Procesi, The invariant theory of $n \times n$ matrices, Adv.\ in Math.~19 (1976) 306--381.}

\bibitem{procesi2}
\href{https://doi.org/10.1016/0021-8693(87)90073-1}{C.~Procesi, A formal inverse to the Cayley--Hamilton theorem, J.~Algebra~107 (1987) 63--74.}

\end{thebibliography}

\bigskip

\noindent\small 0012-365X/88/\$3.50 \copyright\ 1988, Elsevier Science Publishers B.V.\ (North-Holland)

\end{document}