#  Nonconcavity of the Spectral Radius
in Levinger’s Theorem

Lee Altenberg
Information and Computer Sciences,
University of Hawai‘i at Mānoa
<EMAIL_ADDRESS>

and

Joel E. Cohen
Laboratory of Populations,
Rockefeller University & Department of Statistics, Columbia University, New
York
Department of Statistics, University of Chicago
<EMAIL_ADDRESS>
(Date: . _Linear Algebra and Its Applications_
doi.org/10.1016/j.laa.2020.07.028 )

###### Abstract.

Let ${\bf A}\in\mathbb{R}^{n\times n}$ be a nonnegative irreducible square
matrix and let $r({\bf A})$ be its spectral radius and Perron-Frobenius
eigenvalue. Levinger asserted and several have proven that
$r(t):=r((1{-}t){\bf A}+t{\bf A}^{\\!\top})$ increases over $t\in[0,1/2]$ and
decreases over $t\in[1/2,1]$. It has further been stated that $r(t)$ is
concave over $t\in(0,1)$. Here we show that the latter claim is false in
general through a number of counterexamples, but prove it is true for ${\bf
A}\in\mathbb{R}^{2\times 2}$, weighted shift matrices (but not cyclic weighted
shift matrices), tridiagonal Toeplitz matrices, and the 3-parameter Toeplitz
matrices from Fiedler, but not Toeplitz matrices in general. A general
characterization of the range of $t$, or the class of matrices, for which the
spectral radius is concave in Levinger’s homotopy remains an open problem.

_Dedicated to the memory of Bernard Werner Levinger (1928–2020)_

Keywords: circuit matrix, convexity, direct sum, homotopy, nonuniform
convergence, skew symmetric
MSC2010: 15A18, 15A42, 15B05, 15B48, 15B57

##  1\. Introduction

The variation of the spectrum of a linear operator as a function of variation
in the operator has been extensively studied, but even in basic situations
like a linear homotopy $(1{-}t){\bf X}+t{\bf Y}$ between two matrices ${\bf
X},{\bf Y}$, the variational properties of the spectrum have not been fully
characterized. We focus here on Levinger’s theorem about the spectral radius
over the convex combinations of a nonnegative matrix and its transpose,
$(1{-}t){\bf A}+t{\bf A}^{\\!\top}$.

We refer to ${\bf B}(t)=(1{-}t){\bf A}+t{\bf A}^{\\!\top}$, $t\in[0,1]$, as
_Levinger’s homotopy_ ,111Also called Levinger’s transformation Psarrakos and
Tsatsomeros [12]. and the spectral radius of Levinger’s homotopy as
_Levinger’s function_ $r(t)\,{:=}\,r({\bf B}(t))=r((1{-}t){\bf A}+t{\bf
A}^{\\!\top})$.

On November 6, 1969, the _Notices of the American Mathematical Society_
received a three-line abstract from Bernard W. Levinger for his talk at the
upcoming AMS meeting, entitled “An inequality for nonnegative
matrices.”Levinger [8] We reproduce it in full:

“Theorem. Let $A\geq 0$ be a matrix with nonnegative components. Then
$f(t)=p(tA+(1{-}t)A^{T})$ is a monotone nondecreasing function of $t$, for
$0\leq t\leq 1/2$, where $p(C)$ denotes the spectral radius of the matrix $C$.
This extends a theorem of Ostrowski. The case of constant $f(t)$ is
discussed.”

Levinger presented his talk at the Annual Meeting of the American Mathematical
Society at San Antonio in January 1970. Miroslav Fiedler and Ivo Marek were
also at the meeting [9]. Fiedler developed an alternative proof of Levinger’s
theorem and communicated it to Marek [10]. Fiedler did not publish his proof
until 1995 [5]. Levinger appears never to have published his proof.

Marek Marek [10, 11] published the first proofs of Levinger’s theorem,
building on Fiedler’s ideas to generalize it to operators on Banach spaces.
Bapat Bapat [1] proved a generalization of Levinger’s theorem for finite
matrices. He showed that a necessary and sufficient condition for non-constant
Levinger’s function is that ${\bf A}$ have different left and right normalized
(unit) eigenvectors (_Perron vectors_) corresponding to the Perron-Frobenius
eigenvalue (_Perron root_).

Fiedler Fiedler [5] proved also that Levinger’s function $r(t)$ is concave in
some open neighborhood of $t=1/2$, and strictly concave when ${\bf A}$ has
different left and right normalized Perron vectors. The extent of this open
neighborhood was not elucidated.

Bapat and Raghavan Bapat and Raghavan [2, p. 121] addressed the concavity of
Levinger’s function in discussing “an inequality due to Levinger, which
essentially says that for any ${\bf A}\geq 0$, the Perron root, considered as
a function along the line segment joining ${\bf A}$ and ${\bf A}^{\\!\top}$,
is concave.” The inference about concavity would appear to derive from the
theorem of Bapat [1, Theorem 3] that $r(t\,{\bf A}+(1{-}t){\bf
B}^{\\!\top})\geq t\,r({\bf A})+(1{-}t)\,r({\bf B})$ for all $t\in[0,1]$, when
${\bf A}$ and ${\bf B}$ have a common left Perron vector and a common right
Perron vector. The same concavity conclusion with the same argument appears in
Stanczak et al. [13, Corollary 1.17].

However, concavity over the interval $t\in[0,1]$ would require that for all
$t,h_{1},h_{2}\in[0,1]$, $r(t\,{\bf F}(h_{1})+(1{-}t){\bf F}(h_{2}))\geq
t\,r({\bf F}(h_{1}))+(1{-}t)r({\bf F}(h_{2}))$, where ${\bf
F}(h)\,{:=}\,h\,{\bf A}+(1{-}h){\bf B}^{\\!\top}$. While Theorem 3.3.1 of
Bapat and Raghavan [2] proves this for $h_{1}=1$ and $h_{2}=0$, it cannot be
extended generally to $h_{1},h_{2}\in(0,1)$ because ${\bf F}(h_{1})$ and ${\bf
F}(h_{2})^{\\!\top}$ will not necessarily have common left eigenvectors and
common right eigenvectors.

Here, we show that the concavity claim is true for $2\times 2$ and other
special families of matrices. We also show that for each of these matrix
families, counterexamples to concavity arise among matrix classes that are
“close” to them, in having extra or altered parameters. Table 1 summarizes our
results.

Table 1. Classes of nonnegative matrices with concave Levinger’s function (left), and matrix classes “close” to them with nonconcave Levinger’s function (right). Concave |  | Nonconcave |
---|---|---|---
$2\times 2$ |  Theorem 2 |  $3\times 3$, $4\times 4$ |  Eqs. (1), (3)
Tridiagonal Toeplitz |  Theorem 3 | 4-parameter Toeplitz |  Eq. (4)
Fiedler’s 3-parameter Toeplitz |  Theorem 5 | 4-parameter Toeplitz |  Eq. (4)
$n\times n$ weighted shift matrix |  Theorem 8 |  $n\times n$ cyclic weighted shift matrix |  Eq. (8)

##  2\. Matrices that Violate Concavity

###  2.1. A Simple Example

Let

$\displaystyle{\bf A}$ $\displaystyle=\begin{pmatrix}0&1&0\\\ 0&0&0\\\
0&0&2/5\end{pmatrix}$ to give (1) $\displaystyle{\bf B}(t)$
$\displaystyle=(1{-}t){\bf A}+t{\bf A}^{\\!\top}=\begin{pmatrix}0&1{-}t&0\\\
t&0&0\\\ 0&0&2/5\end{pmatrix}.$

The eigenvalues of ${\bf B}(t)$ are
$\\{2/5,+\sqrt{t(1{-}t)},-\sqrt{t(1{-}t)}\\}$, plotted in Figure 1. On the
interval $t\in[1/5,4/5]$, $r({\bf B}(t))=\sqrt{t(1{-}t)}$ is strictly concave.
On the intervals $t\in[0,1/5]$ and $t\in[4/5,1]$, $r({\bf B}(t))$ is constant.
It is clear from the figure that $r({\bf B}(t))$ is not concave in the
neighborhood of $t=1/5$ (and $t=4/5$), since for all small $\epsilon>0$,

(2) $\displaystyle\frac{1}{2}[r({\bf B}(1/5-\epsilon)+r({\bf
B}(1/5+\epsilon)]>r({\bf B}(1/5))=2/5.$

By the continuity of the eigenvalues in the matrix elements [7, 2.4.9], we can
make ${\bf B}(t)$ irreducible and yet preserve inequality (2) in a
neighborhood of $t=1/5$ by adding a small enough positive perturbation to each
element of ${\bf A}$.

Figure 1. Eigenvalues of the matrix ${\bf B}(t)$ from (1),
$\lambda_{1}=2/5,\lambda_{2}=+\sqrt{t(1{-}t)},\lambda_{3}=-\sqrt{t(1{-}t)}$,
showing that the spectral radius $r({\bf B}(t))$ (thick top line) is not
concave around the points $t=0.2$ and $t=0.8$.

The basic principle behind this counterexample is that the maximum of two
concave functions need not be concave. Here ${\bf B}(t)$ is the direct sum of
two block matrices. The eigenvalues of the direct sum are the union of the
eigenvalues of the blocks, which are different functions of $t$. One block has
a constant spectral radius and the other block has a strictly concave spectral
radius. The spectral radius of ${\bf B}(t)$ is their maximum.

Another example of this principle is constructed by taking the direct sum of
two $2\times 2$ blocks, each of which is a Levinger homotopy of the matrix
$\begin{pmatrix}0&1\\\ 0&0\end{pmatrix}$, but for values of $t$ at opposite
ends of the unit interval, one $2\times 2$ block, ${\bf A}_{1}$, with
$t_{1}=511/512$ and the other $2\times 2$ block, ${\bf A}_{2}$, with
$t_{2}=1/8$. We take a weighted combination of the two blocks with weight $h$,
${\bf A}(h)=(1-h){\bf A}_{1}\oplus h{\bf A}_{2}$, to get:

(3) $\displaystyle{\bf A}(h)$
$\displaystyle=\begin{pmatrix}0&(1{-}h)\frac{511}{512}&0&0\\\
(1{-}h)\frac{1}{512}&0&0&0\\\ 0&0&0&h\frac{1}{8}\\\
0&0&h\frac{7}{8}&0\end{pmatrix}.$

The eigenvalues of ${\bf B}(t,h)=(1{-}t){\bf A}(h)+t{\bf A}(h)^{\\!\top}$ are
plotted in Figure 2. We see that there is a narrow region of $h$ below $h=0.5$
where the maximum eigenvalue switches from block 2 to block 1 and back to
block 2 with increasing $t\in[0,1]$, making $r({\bf B}(t,h))=r((1{-}t){\bf
A}(h)+t{\bf A}(h)^{\\!\top})$ at $h=0.4$ nonconcave with respect to the
interval $t\in[0,1]$.

Figure 2. Eigenvalues of ${\bf B}(t,h)$ for a two-parameter homotopy:
Levinger’s homotopy ${\bf B}(t,h)=(1{-}t){\bf A}(h)+t{\bf A}(h)^{\\!\top}$,
$t\in[0,1]$, and a second homotopy ${\bf A}(h)=(1{-}h){\bf A}_{1}\oplus h{\bf
A}_{2}$, $h\in[0,1]$ (3). The dark band at $h=0.4$ is $r({\bf B}(t,0.4))$,
showing that the spectral radius is nonconcave in $t$ where it jumps between
the two concave upper manifolds.

As in example 1, ${\bf A}(h)$ may be made irreducible by positive perturbation
of the $0$ values without eliminating the nonconcavity.

The principle here may be codified as follows.

######  Proposition 1.

Let ${\bf A}={\bf A}_{1}\oplus{\bf A}_{2}\in\mathbb{R}^{n\times n}$, where
${\bf A}_{1}$ and ${\bf A}_{2}$ are irreducible nonnegative square matrices.
Then $r(t)\,{:=}\,r((1-t){\bf A}+t{\bf A}^{\\!\top})$ is not concave in
$t\in(0,1)$ if there exists $t^{*}\in(0,1)$ such that

  1. (1)

$r((1-t^{*}){\bf A}_{1}+t^{*}{\bf A}_{1}^{\\!\top})=r((1-t^{*}){\bf
A}_{2}+t^{*}{\bf A}_{2}^{\\!\top})$,

and

  2. (2)

$\left.\displaystyle\frac{{\rm d}}{{\rm d}t}r((1-t){\bf A}_{1}+t{\bf
A}_{1}^{\\!\top})\right|_{t=t^{*}}\neq\left.\displaystyle\frac{{\rm d}}{{\rm
d}t}r((1-t){\bf A}_{2}+t{\bf A}_{2}^{\\!\top})\right|_{t=t^{*}}$.

###### Proof.

Let $r^{*}\,{:=}\,r(t^{*})=r((1-t^{*}){\bf A}_{1}+t^{*}{\bf
A}_{1}^{\\!\top})=r((1-t^{*}){\bf A}_{2}+t^{*}{\bf A}_{2}^{\\!\top})$. Since
the spectral radius of a nonnegative irreducible matrix is a simple eigenvalue
by Perron-Frobenius theory, it is analytic in the matrix elements [14, Fact
1.2]. Thus for each of ${\bf A}_{1}$ and ${\bf A}_{2}$, Levinger’s function is
analytic in $t$, and therefore has equal left and right derivatives around
$t^{*}$. So we can set $s_{1}={\rm d}r((1-t){\bf A}_{1}+t{\bf
A}_{1}^{\\!\top})/{\rm d}t|_{t=t^{*}}$ and $s_{2}={\rm d}r((1{-}t){\bf
A}_{2}+t{\bf A}_{2}^{\\!\top})/{\rm d}t|_{t=t^{*}}$. Then

$\displaystyle r((1{-}t^{*}{-}\epsilon){\bf A}_{1}+(t^{*}{+}\epsilon){\bf
A}_{1}^{\\!\top})$ $\displaystyle=r^{*}+\epsilon
s_{1}+\mathcal{O}(\epsilon^{2}),$ $\displaystyle r((1{-}t^{*}{-}\epsilon){\bf
A}_{2}+(t^{*}{+}\epsilon){\bf A}_{2}^{\\!\top})$ $\displaystyle=r^{*}+\epsilon
s_{2}+\mathcal{O}(\epsilon^{2}).$

For a small neighborhood around $t^{*}$,

$\displaystyle r(t^{*}{+}\epsilon)$
$\displaystyle=r((1{-}t^{*}{-}\epsilon){\bf A}+(t^{*}{+}\epsilon){\bf
A}^{\\!\top})$ $\displaystyle=\max\left\\{\,r((1{-}t^{*}{-}\epsilon){\bf
A}_{1}+(t^{*}{+}\epsilon){\bf A}_{1}^{\\!\top}),r((1{-}t^{*}{-}\epsilon){\bf
A}_{2}+(t^{*}{+}\epsilon){\bf A}_{2}^{\\!\top})\,\right\\}$
$\displaystyle=r^{*}+\left\\{\begin{array}[]{ll}\displaystyle\epsilon\min(s_{1},s_{2})+\mathcal{O}(\epsilon^{2}),&\qquad\epsilon<0,\\\
\epsilon\max(s_{1},s_{2})+\mathcal{O}(\epsilon^{2}),&\qquad\epsilon>0.\end{array}\right.$

A necessary condition for concavity is
$\frac{1}{2}(r(t^{*}{+}\epsilon)+r(t^{*}{-}\epsilon))\leq r(t^{*}).$ However,
for small enough $\epsilon>0$, letting
$\delta=\max(s_{1},s_{2})-\min(s_{1},s_{2})>0$,

$\displaystyle\frac{r(t^{*}{+}\epsilon)+r(t^{*}{-}\epsilon)}{2}$
$\displaystyle=r^{*}+\epsilon\frac{\max(s_{1},s_{2})-\min(s_{1},s_{2})}{2}+\mathcal{O}(\epsilon^{2})$
$\displaystyle=r^{*}+\epsilon\delta/{2}+\mathcal{O}(\epsilon^{2})>r^{*}.$

The condition for concavity is thus violated. ∎

###  2.2. Toeplitz Matrices

The following nonnegative irreducible Toeplitz matrix has a nonconcave
Levinger’s function:

(4) $\displaystyle{\bf A}$ $\displaystyle=\begin{pmatrix}5&0&6&0\\\ 1&5&0&6\\\
0&1&5&0\\\ 8&0&1&5\end{pmatrix}$

A plot of Levinger’s function for (4) is not unmistakably nonconcave, so
instead we plot the second derivative of $r({\bf B}(t))$ in Figure 3, which is
positive at the boundaries $t=0$ and $t=1$, and becomes negative in the
interior.

Figure 3. The second derivative of Levinger’s function for the Toeplitz matrix
(4).

###  2.3. Weighted Circuit Matrices

Another class of matrices where Levinger’s function can be nonconcave is the
weighted circuit matrix. A weighted circuit matrix is an $n\times n$ matrix in
which there are $k\in[1,n]$ distinct integers
$i_{1},i_{2},\ldots,i_{k}\in\\{1,2,\ldots,n\\}$ such that all elements are
zero except weights $c_{j}$, $j=1,\ldots,k$, at matrix positions
$(i_{1},i_{2}),(i_{2},i_{3}),\ldots,(i_{k-1},i_{k}),(i_{k},i_{1})$, which form
a circuit. We refer to a _positive weighted circuit matrix_ when the weights
are all positive numbers.

When focusing on the spectral radius of a positive weighted circuit matrix, we
may without loss of generality consider its non-zero principal submatrix,
whose canonical permutation of the indices gives a _positive cyclic weighted
shift matrix_ , ${\bf A}$, with elements

(7) $\displaystyle A_{ij}$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle c_{i}>0,&\qquad
j=i\text{ mod }n+1,\quad i\in\left\\{\,1,\ldots,n\,\right\\},\\\
0,&\qquad\text{otherwise.}\end{array}\right.$

Equation (7) defines a cyclic _downshift_ matrix, while an _upshift_ matrix
results from replacing $j=i\text{ mod }n+1$ with $i=j\text{ mod }n+1$, which
is equivalent for our purposes. Cyclic weighted shift matrices have the form

$\displaystyle\begin{pmatrix}0&c_{1}&0&0\\\ 0&0&c_{2}&0\\\ 0&0&0&c_{3}\\\
c_{4}&0&0&0\\\ \end{pmatrix}.$

If one of the weights $c_{i}$ is set to $0$, the matrix becomes a positive
non-cyclic weighted shift matrix. In Section 3.4, we show that Levinger’s
function of a positive non-cyclic weighted shift matrix is strictly concave.
Cyclicity from a single additional positive element $c_{i}>0$ allows
nonconcavity.

Here we provide an example of nonconcavity using a cyclic shift matrix with
_reversible weights_ , which have been the subject of recent attention [4].
Figure 4 shows Levinger’s function for a $16\times 16$ cyclic weighted shift
matrix with two-pivot reversible weights

(8) $\displaystyle c_{j}$
$\displaystyle=16+\sin\left(2\pi\frac{j}{16}\right),$ $\displaystyle\quad
j=1,\ldots,16.$

Levinger’s function is convex for most of the interval $t\in[0,1]$, and is
concave only in the small interval around $t=1/2$.

Figure 4. Nonconcave Levinger’s function for a $16\times 16$ two-pivot
reversible cyclic weighted shift matrix with weights $c_{j}=16+\sin(2\pi
j/16)$, (8).

##  3\. Matrices with Concave Levinger’s Function

Here we show that several special classes of nonnegative matrices have concave
Levinger’s functions: $2\times 2$ matrices, non-cyclic weighted shift
matrices, tridiagonal Toeplitz matrices, and Fiedler’s 3-parameter Toeplitz
matrices.

###  3.1. $2\times 2$ Matrices

######  Theorem 2.

Let ${\bf A}\in\mathbb{R}^{2\times 2}$ be nonnegative and irreducible. Then
the spectral radius and Perron-Frobenius eigenvalue $r(t):=r((1{-}t){\bf
A}+t{\bf A}^{\\!\top})$ is concave over $t\in(0,1)$, strictly when ${\bf A}$
has different left and right Perron-Frobenius eigenvectors.

###### Proof.

Let $a,b,c,d\in(0,\infty),t\in(0,1)$, and assume $b\neq c$ to assure that
${\bf A}\neq{\bf A}^{\\!\top}$ and the left and right Perron-Frobenius
eigenvectors are not colinear. Let

${\bf A}:=\begin{pmatrix}a&b\\\ c&d\end{pmatrix},\quad{\bf B}(t):=(1{-}t){\bf
A}+t{\bf A}^{\\!\top}.$

The Perron-Frobenius eigenvalue of ${\bf B}(t)$ is obtained by using the
quadratic formula to solve the characteristic equation. After some
simplification,

$r(t):=r({\bf B}(t))=\frac{a+d+\sqrt{(a-d)^{2}+4t(1{-}t)(b-c)^{2}+4bc}}{2}.$

The first derivative with respect to $t$ is

$r^{\prime}(t)=\frac{{\left(1{-}2\,t\right)}\,{{\left(b-c\right)}}^{2}}{\sqrt{(a-d)^{2}+4t(1{-}t)(b-c)^{2}+4bc}}.$

The denominator above is positive for all $t\in(0,1)$ because of the
assumption that $b\neq c$. The second derivative is, again after some
simplification,

(9) $\displaystyle
r^{\prime\prime}(t)=-\frac{2\,(b-c)^{2}\,\left((a-d)^{2}+(b+c)^{2}\right)}{{{\left((a-d)^{2}+4t(1{-}t)(b-c)^{2}+4bc\right)}}^{3/2}}<0.$

The numerator in the fraction above is positive because $b\neq c$, and the
minus sign in front of the fraction guarantees strict concavity for all
$t\in(0,1)$. ∎

###  3.2. Tridiagonal Toeplitz Matrices

######  Theorem 3 (Tridiagonal Toeplitz Matrices).

Let ${\bf A}\in\mathbb{R}^{n\times n}$, $n\geq 2$, be a tridiagonal Toeplitz
matrix with diagonal elements $b\geq 0$, subdiagonal elements $a\geq 0$, and
superdiagonal elements $c\geq 0$, with $\max(a,\ c)>0$. Then for $t\in(0,1)$,
$r((1{-}t){\bf A}+t{\bf A}^{\\!\top})$ is concave in $t$, increasing on
$t\in(0,1/2)$, and decreasing on $t\in(1/2,1)$, all strictly when $a\neq c$.

###### Proof.

The eigenvalues of a tridiagonal Toeplitz matrix ${\bf A}$ with $a,c\neq 0$
are [6, 22-5.18] [3, Theorem 2.4]

(10) $\displaystyle\lambda_{k}({\bf A})$ $\displaystyle=b+2\sqrt{ac}\
\cos\left(\frac{k\pi}{n{+}1}\right).$

The matrix $(1{-}t){\bf A}+t{\bf A}^{\\!\top}$ has subdiagonal values
$(1{-}t)a+tc$ and superdiagonal values $ta+(1{-}t)c$. Since at least one of
$a,c$ is strictly positive, $(1{-}t)a+tc>0$ and $ta+(1{-}t)c>0$ for
$t\in(0,1)$. Therefore (10) is applicable.

Writing $\lambda_{k}(t)\,{:=}\,\lambda_{k}((1{-}t){\bf A}+t{\bf
A}^{\\!\top})$, we obtain

$\displaystyle\lambda_{k}(t)$
$\displaystyle=b+2\sqrt{((1{-}t)a+tc)(ta+(1{-}t)c)}\
\cos\left(\frac{k\pi}{n{+}1}\right).$

It is readily verified that the first derivatives are

$\displaystyle\displaystyle\frac{{\rm d}}{{\rm d}t}\lambda_{k}(t)$
$\displaystyle=\cos\left(\frac{k\pi}{n{+}1}\right)\frac{(a-c)^{2}(1{-}2t)}{\sqrt{((1{-}t)a+tc)(ta+(1{-}t)c)}},$
and the second derivatives are $\displaystyle\displaystyle\frac{{\rm
d}^{2}}{{\rm d}t^{2}}\lambda_{k}(t)$
$\displaystyle=-\cos\left(\frac{k\pi}{n{+}1}\right)\frac{(a^{2}-c^{2})^{2}}{2\big{[}((1{-}t)a+tc)(ta+(1{-}t)c)\big{]}^{3/2}}.$

Since $(1{-}t)a+tc>0$ and $ta+(1{-}t)c>0$ for $t\in(0,1)$, the denominators
are positive. When $a=c$ both derivatives are identically zero. When $a\neq
c$, the factors not dependent on $k$ are strictly positive for all $t\in(0,1)$
except for $t=1/2$ where the first derivative of all the eigenvalues vanishes.

Because the second derivatives have no sign changes on $t\in(0,1)$, and since
$[(1{-}t)a+tc][ta+(1{-}t)c]>0$, there are no inflection points. Therefore each
eigenvalue is either convex in $t$ or concave in $t$, depending on the sign of
$\cos(k\pi/(n+1))$. The maximal eigenvalue is

$\displaystyle r(t)=\lambda_{1}(t)=b+2\sqrt{((1{-}t)a+tc)(ta+(1{-}t)c)}\
\cos(\pi/(n{+}1)).$

From its first derivative, since $\cos(\pi/(n{+}1))>0$, $r(t)$ is increasing
on $t\in(0,1/2)$ and decreasing on $t\in(1/2,1)$, strictly when $a\neq c$.
Since its second derivative is negative, $r(t)$ is concave in $t$ on
$t\in(0,1)$, strictly when $a\neq c$. ∎

###  3.3. Fiedler’s Toeplitz Matrices

Fiedler Fiedler [5, p. 180] established this closed formula for the spectral
radius of a special Toeplitz matrix.

######  Theorem 4 (Fiedler’s 3-Parameter Toeplitz Matrices).

Consider a Toeplitz matrix ${\bf A}\in\mathbb{C}^{n\times n}$, $n\geq 3$, with
diagonal values $(v,0,\ldots,0,v,w,u,0,\ldots,0,u)$, with
$v,w,u\in\mathbb{C}$:

(11) $\displaystyle{\bf A}$ $\displaystyle=\begin{pmatrix}w&u&0&\cdots&0&u\\\
v&w&u&0&\cdots&0\\\ 0&v&w&u&\cdots&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\\ 0&0&\cdots&v&w&u\\\
v&0&\cdots&0&v&w\end{pmatrix}.$

Let $\omega=e^{2\pi i/n}$. The eigenvalues of ${\bf A}$ are

$\displaystyle\lambda_{j+1}({\bf A})$
$\displaystyle=w+\omega^{j}u^{(1{-}1/n)}v^{1/n}+\omega^{n-j}u^{1/n}v^{(1{-}1/n)},\qquad
j=0,1,\ldots,n{-}1.$

We apply Theorem 4 to the Levinger function.

######  Theorem 5.

Let ${\bf A}$ be defined as in (11) with $u,v,w>0$. Then
$r(t)\,{:=}\,r((1{-}t){\bf A}+t{\bf A}^{\\!\top})$ is concave in $t$ for
$t\in(0,1)$, strictly if $u\neq v$.

###### Proof.

For $u,v,w>0$, $r({\bf A})=\lambda_{1}({\bf
A})=w+u^{(1{-}1/n)}v^{1/n}+u^{1/n}v^{(1{-}1/n)}$ from Theorem 4.

Let ${\bf B}(t)=(1{-}t){\bf A}+t{\bf A}^{\\!\top}$. Then ${\bf B}(t)$ is again
a Toeplitz matrix of the form (11), with diagonal values
$(1{-}t)v{+}tu,0,\ldots,0,(1{-}t)v{+}tu,w,(1{-}t)u{+}tv,$ $0,\ldots,0$,
$(1{-}t)u{+}tv$ for matrix elements $A_{i,i{+}m}$, with
$m\in\left\\{\,1{-}n,n{-}1\,\right\\}$, and $i\in$$\\{\max(1,1{-}m)$,
$\ldots$, $\min(n,n{-}m)$$\\}$. So again by Theorem 4,

$\displaystyle r({\bf B}(t))=w$ $\displaystyle+[(1{-}t)u+tv]^{(1{-}1/n)}\
[(1{-}t)v+tu]^{1/n}$ $\displaystyle+[(1{-}t)u+tv]^{1/n}\
[(1{-}t)v+tu]^{(1{-}1/n)}.$

It is readily verified that

$\displaystyle\displaystyle\frac{{\rm d}^{2}}{{\rm d}t^{2}}r({\bf B}(t))$
$\displaystyle=-\frac{n-1}{n^{2}u^{2}v^{2}}(u-v)^{2}(u+v)^{2}$
$\displaystyle\quad\times\left([(1{-}t)v+u]^{1/n}[(1{-}t)u+tv]^{(1{-}1/n)}+[(1{-}t)v+u]^{(1{-}1/n)}[(1{-}t)u+tv]^{1/n}\right)$
$\displaystyle\leq 0,$

with equality if and only if $u=v$. ∎

With the simple exchange of $A_{1n}$ and $A_{n1}$ in (11), ${\bf A}$ would
become a circulant matrix, which has left and right Perron vectors colinear
with the vector of all ones, ${\bf e}$, and would therefore have a constant
Levinger’s function.

###  3.4. Weighted Shift Matrices

An $n\times n$ weighted shift matrix, ${\bf A}$, has the form

$\displaystyle A_{ij}=\left\\{\begin{array}[]{ll}\displaystyle c_{i},&\qquad
j=i+1,\quad i\in\left\\{\,1,\ldots,n-1\,\right\\},\\\
0,&\qquad\text{otherwise},\end{array}\right.$

where $c_{i}$ are the weights. It is obtained from a cyclic shift matrix be
setting any one of the weights to $0$ and appropriately permuting the indices.
Unless we explicitly use “cyclic”, we mean _non-cyclic shift matrix_ when we
write “shift matrix”.

We will show that Levinger’s function for positive weighted shift matrices is
strictly concave. First we develop some lemmas.

######  Lemma 6.

Let ${\bf c}\in\mathbb{C}^{n+1}$ be a vector of complex numbers and
$\alpha\in\mathbb{C}$, $\alpha\neq 0$. Then the roots of a polynomial
$p(x)=\sum_{k=0}^{n}x^{k}\alpha^{n-k}c_{k}$ are $r_{j}=\alpha f_{j}({\bf c})$,
where $f_{j}:\mathbb{C}^{n+1}\rightarrow\mathbb{C}$, $j=1,\ldots,n$.

###### Proof.

We factor and apply the Fundamental Theorem of Algebra to obtain

$\displaystyle p(x)$
$\displaystyle=\sum_{k=0}^{n}x^{k}\alpha^{n-k}c_{k}=\alpha^{n}\sum_{k=0}^{n}\left(\frac{x}{\alpha}\right)^{k}c_{k}=\alpha^{n}\prod_{j=1}^{n}\left(\frac{x}{\alpha}-f_{j}({\bf
c})\right).$

Hence the roots of $p(x)$ are $\left\\{\,\alpha f_{j}({\bf c})\ |\
j=1,\ldots,n\,\right\\}$. ∎

######  Lemma 7.

Let $\alpha,\beta\in\mathbb{C}\backslash 0$, ${\bf A}(\alpha,\beta)=[A_{ij}]$
be a hollow tridiagonal matrix, where $A_{ij}>0$ for $j=i+1$ and $j=i-1$,
$A_{ij}=0$ otherwise, and

$\displaystyle
A_{ij}=\left\\{\begin{array}[]{ll}\displaystyle\alpha\,c_{ij},&\qquad
j=i+1,\quad i\in\left\\{\,1,\ldots,n-1\,\right\\},\\\ \beta\,c_{ij},&\qquad
j=i-1,\quad i\in\left\\{\,2,\ldots,n\,\right\\},\end{array}\right.$

so ${\bf A}(\alpha,\beta)$ has the form

$\displaystyle{\bf A}(\alpha,\beta)$
$\displaystyle=\begin{pmatrix}0&\alpha\,c_{12}&0&\cdots&0&0&0\\\
\beta\,c_{21}&0&\alpha\,c_{23}&\cdots&0&0&0\\\
0&\beta\,c_{32}&0&\ddots&0&0&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
0&0&0&\ddots&0&\alpha\,c_{n{-}2,n{-}1}&0\\\
0&0&0&\cdots&\beta\,c_{n{-}1,n{-}2}&0&\alpha\,c_{n{-}1,n}\\\
0&0&0&\cdots&0&\beta\,c_{n,n{-}1}&0\end{pmatrix}.$

Let ${\bf c}\in\mathbb{C}^{2(n-1)}$ represent the vector of $c_{ij}$
constants.

Then the eigenvalues of ${\bf A}$ are of the form
$\sqrt{\alpha\beta}\>f_{h}({\bf c})$, $h=1,\ldots,n$, where
$f_{h}\colon\mathbb{C}^{2(n-2)}\rightarrow\mathbb{C}$ are functions of the
$c_{ij}$ constants that do not depend on $\alpha$ or $\beta$.

###### Proof.

The characteristic polynomial of ${\bf A}$ is

$\displaystyle p_{\bf A}(\lambda)$ $\displaystyle=\det(\lambda{\bf I}-{\bf
A})$ $\displaystyle=\begin{vmatrix}\lambda&-\alpha\,c_{12}&0&\cdots&0&0&0\\\
-\beta\,c_{21}&\lambda&-\alpha\,c_{23}&\cdots&0&0&0\\\
0&-\beta\,c_{32}&\lambda&\ddots&0&0&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
0&0&0&\ddots&\lambda&-\alpha\,c_{n{-}2,n{-}1}&0\\\
0&0&0&\cdots&-\beta\,c_{n{-}1,n{-}2}&\lambda&-\alpha\,c_{n{-}1,n}\\\
0&0&0&\cdots&0&-\beta\,c_{n,n{-}1}&\lambda\end{vmatrix}.$

The characteristic polynomial has the recurrence relation

(12) $\displaystyle p_{{\bf A}_{k}}(\lambda)$ $\displaystyle=\lambda\ p_{{\bf
A}_{k-1}}(\lambda)-\alpha\,\beta\,c_{k,k{-}1}\ c_{k{-}1,k}\ p_{{\bf
A}_{k-2}}(\lambda),$ $\displaystyle\quad k\in\left\\{\,3,\ldots,n\,\right\\},$
with initial conditions (13) $\displaystyle p_{{\bf A}_{2}}(\lambda)$
$\displaystyle=\lambda^{2}-\alpha\,\beta\ c_{12}\ c_{21},\quad\text{and}$ (14)
$\displaystyle p_{{\bf A}_{1}}(\lambda)$ $\displaystyle=\lambda,$

where ${\bf A}_{k}$ is the principal submatrix of ${\bf A}$ over indices
$1,\ldots,k$.

We show by induction that for all $k\in\left\\{\,2,\ldots,n\,\right\\}$,

(15) $\displaystyle p_{{\bf A}_{k}}(\lambda)$
$\displaystyle=\sum_{j=0}^{k}\lambda^{j}(\alpha\beta)^{(k-j)/2}\,g_{jk}({\bf
c})=\sum_{j=0}^{k}\lambda^{j}\sqrt{\alpha\beta}^{\,(k-j)}g_{jk}({\bf c}),$

where each $g_{jk}\colon\mathbb{C}^{2(n-1)}\rightarrow\mathbb{C}$,
$k\in\left\\{\,2,\ldots,n\,\right\\}$, $j\in\left\\{\,0,\ldots,k\,\right\\}$,
is a function of constants ${\bf c}$.

From (13), we see that (15) holds for $k=2$: $p({\bf
A}_{2})(\lambda)=\lambda^{2}-\alpha\,\beta\,c_{12}\,c_{21}.$

For $k=3$, from the recurrence relation (12) and initial conditions (14),
(13), we have

$\displaystyle p({\bf A}_{3})(\lambda)$ $\displaystyle=\lambda\,p_{{\bf
A}_{2}}(\lambda)-\alpha\beta\,c_{32}\,c_{23}\,p_{{\bf
A}_{1}}(\lambda)=\lambda(\lambda^{2}-\alpha\beta\,c_{12}\,c_{21})-\alpha\beta\,c_{32}\,c_{23}\,\lambda$
$\displaystyle=\lambda^{3}-\lambda\sqrt{\alpha\beta}^{\,2}(c_{12}\,c_{21}+c_{32}\,c_{23}),$

which satisfies (15). These are the basis steps for the induction.

For the inductive step, we need to show that if (15) holds for $k-1,k-2$ then
it holds for $k$. Suppose that (15) holds for $2\leq k-1,k-2\leq n-1$. Then

$\displaystyle p_{{\bf A}_{k}}(\lambda)=\lambda\,p_{{\bf
A}_{k-1}}(\lambda)-\alpha\beta\,c_{k,k{-}1}\,c_{k{-}1,k}\ p_{{\bf
A}_{k-2}}(\lambda)$
$\displaystyle=\lambda\sum_{j=0}^{k{-}1}\lambda^{j}\sqrt{\alpha\beta}^{\,(k{-}1{-}j)}g_{j,k{-}1}({\bf
c})-\alpha\beta\,c_{k,k{-}1}\,c_{k{-}1,k}\sum_{j=0}^{k-2}\lambda^{j}\sqrt{\alpha\beta}^{\,(k-2-j)}g_{j,k-2}({\bf
c})$
$\displaystyle=\sum_{j=1}^{k}\lambda^{j}\sqrt{\alpha\beta}^{\,(k{-}j)}g_{j-1,k{-}1}({\bf
c}){-}\sum_{j=0}^{k{-}2}\lambda^{j}\sqrt{\alpha\beta}^{\,(k-j)}c_{k,k{-}1}\,c_{k{-}1,k}\
g_{j,k-2}({\bf c}),$

which satisfies (15). Thus by induction $p_{{\bf A}_{n}}(\lambda)$ satisfies
(15).

Then Lemma 6 implies that the parameters $\left\\{\,\alpha,\beta\,\right\\}$
appear as the linear factor $\sqrt{\alpha\beta}$ in each root of the
characteristic polynomial of ${\bf A}(\alpha,\beta)$ — its eigenvalues. ∎

######  Theorem 8 (Weighted Shift Matrices).

Levinger’s function is strictly concave for nonnegative weighted shift
matrices with at least one positive weight.

###### Proof.

Let the positive weighted shift matrix ${\bf A}$ be defined as

$\displaystyle A_{ij}=\left\\{\begin{array}[]{ll}\displaystyle c_{i}\geq
0,&\qquad j=i+1,\quad i\in\left\\{\,1,\ldots,n-1\,\right\\},\\\
0,&\qquad\text{otherwise},\end{array}\right.$

where $c_{i}$ are the weights and $c_{i}>0$ for at least one $i=1,\ldots,n-1$.

By Lemma 7, all the eigenvalues of Levinger’s homotopy ${\bf B}(t)=(1{-}t){\bf
A}+t{\bf A}^{\\!\top}$ are of the form $\lambda_{i}({\bf
B}(t))=\sqrt{t(1{-}t)}\,f_{i}({\bf c})$, where ${\bf c}$ is the vector of
weights, and $f_{i}\colon\mathbb{R}^{n-1}\rightarrow\mathbb{R}$, since ${\bf
B}(t)$ is a direct sum of one or more (if some $c_{i}=0$) Jacobi matrices and
these have real eigenvalues [6, 22.7.2].

If at least one weight $c_{i}$ is positive, then ${\bf B}(t)$ has a principal
submatrix $\begin{pmatrix}0&(1{-}t)c_{i}\\\ t\,c_{i}&0\end{pmatrix}$ with a
positive spectral radius for $t\in(0,1)$. Thus by Horn and Johnson [7,
Corollary 8.1.20(a)], $r({\bf B}(t))>0$ for $t\in(0,1)$. Therefore for
$t\in(0,1)$, $r({\bf B}(t))=\lambda_{1}({\bf
B}(t))=\sqrt{t(1{-}t)}\>f_{1}({\bf c})>0$. Since $\sqrt{t(1{-}t)}$ is strictly
concave in $t$ for $t\in(0,1)$, Levinger’s function is strictly concave in $t$
for $t\in(0,1)$. ∎

######  Corollary 9.

Levinger’s function is strictly concave for a nonnegative hollow tridiagonal
matrix, ${\bf A}\in\mathbb{R}^{n\times n}$, in which $A_{ii}=0$ for
$i\in\left\\{\,1,\ldots,n\,\right\\}$, and where for each
$i\in\left\\{\,1,\ldots,n-1\,\right\\}$, $A_{i,i+1}\,A_{i+1,i}=0$, and for at
least one $i$, $A_{i,i+1}>0$.

###### Proof.

${\bf A}$ is derived from a weighted shift matrix by swapping some elements of
the superdiagonal $A_{i,i+1}$ to the transposed position in the subdiagonal,
$A_{i+1,i}$. The determinant of Levinger’s homotopy $\det(\lambda{\bf I}-{\bf
B}(t))=\det(\lambda{\bf I}-(1-t){\bf A}-t{\bf A}^{\\!\top})$ remains unchanged
under such swapping because the term $\alpha\beta\,c_{k,k{-}1}\,c_{k{-}1,k}$
in (12), which is $(1-t)t\,c_{k{-}1,k}^{2}$ in the weighted shift matrix,
remains invariant under swapping as $t(1-t)\,c_{k,k{-}1}^{2}$. ∎

We complete the connection to positive weighted circuit matrices with this
corollary.

######  Corollary 10.

By setting one or more, but not all, of the weights in a positive weighted
circuit matrix to $0$, Levinger’s function becomes strictly concave.

###### Proof.

A positive weighted circuit matrix where some but not all of the positive
weights are changed to $0$ is, under appropriate permutation of the indices, a
nonnegative weighted shift matrix to which Theorem 8 applies. ∎

What kind of transition does Levinger’s function make during the transition
from a cyclic weighted shift matrix with nonconcave Levinger’s function to a
weighted shift matrix with its necessarily concave Levinger’s function, as one
of the weights is lowered to $0$? Does the convexity observed in Figure 4 at
the boundaries $t=0$ and $t=1$ flatten and become strictly concave for some
positive value of that weight? We examine this transition for the cyclic shift
matrix in example (8) (Figure 4). The minimal weight is
$c_{12}=16+\sin\left(2\pi\frac{12}{16}\right)=15$. Figure 5 plots Levinger’s
function as $c_{12}$ is divided by factors of $2^{8}$.

Figure 6 plots the second derivatives of Levinger’s function. We observe non-
uniform convergence to the $c_{12}=0$ curve. As $c_{12}$ decreases, the second
derivative converges to the $c_{12}=0$ curve over wider and wider intervals of
$t$, but outside of these intervals the second derivative _diverges_ from the
$c_{12}=0$ curve, attaining larger values near and at the boundaries $t=0$ and
$t=1$ with smaller $c_{12}$. Meanwhile for $c_{12}=0$, Levinger’s function is
proportional to $\sqrt{t(1-t)}$, the second derivative of which goes to
$-\infty$ as $t$ goes to $0$ or $1$. When $c_{12}>0$, ${\bf B}(0)$ and ${\bf
B}(1)$ are irreducible, and when $c_{12}=0$, ${\bf B}(t)$ is irreducible for
$t\in(0,1)$. But for $c_{12}=0$, ${\bf B}(0)$ and ${\bf B}(1)$ are reducible
matrices. While the eigenvalues are always continuous functions of the
elements of the matrix, the derivatives of the spectral radius need not be,
and in this case, we see an unusual example of nonuniform convergence in the
second derivative of the spectral radius.

Figure 5. Levinger’s function for the cyclic weighted shift matrix from (8) in
the limit as weight $c_{12}$ goes toward $0$ by being multiplied by successive
powers of $2^{-8}$. The topmost line with $c_{12}=15\times 1$ is the same as
the curve in Figure 4 but with an expanded Y-axis.

Figure 6. The second derivative of Levinger’s function for the cyclic weighted
shift matrix from (8) as weight $c_{12}$ goes toward $0$ by being multiplied
by successive powers of $2^{-8}$.

##  4\. Matrices with Constant Levinger’s Function

Bapat [1] and Fiedler [5] identified matrices with colinear left and right
Perron vectors as having constant Levinger’s function. Here we make explicit a
property implied by this constraint that appears not to have been described.
We use the centered representation of Levinger’s homotopy. The _symmetric_
part of a square matrix ${\bf A}$ is

(16) $\displaystyle{\bf S}({\bf A})\,{:=}\,({\bf A}+{\bf A}^{\\!\top})/2.$

The _skew symmetric_ part of ${\bf A}$ is

(17) $\displaystyle{\bf K}({\bf A})\,{:=}\,({\bf A}-{\bf A}^{\\!\top})/2.$

Then ${\bf A}={\bf S}({\bf A})+{\bf K}({\bf A})$. Levinger’s homotopy in this
centered representation is now, suppressing the ${\bf A}$ argument,

$\displaystyle{\bf C}(p)$ $\displaystyle\,{:=}\,{\bf S}+p\,{\bf K},\qquad
p\in[-1,1],$ and Levinger’s function is $\displaystyle c(p)$
$\displaystyle\,{:=}\,r((p+1)/2)=r({\bf S}+p\,{\bf K}).$

The range of $p$ in this centered representation may be extended beyond
$[-1,1]$, while maintaining ${\bf C}(p)\geq{{\bf 0}}$, to the interval
$p\in[-\alpha,\alpha]$ where

$\displaystyle\alpha=\min_{i,j}\frac{A_{ij}+A_{ji}}{|A_{ji}-A_{ij}|}\geq 1.$

######  Theorem 11.

Let ${\bf A}\in\mathbb{R}^{n\times n}$ be irreducible and nonnegative. Then
$r((1{-}t){\bf A}+t{\bf A}^{\\!\top})$ is constant in $t\in[0,1]$ if and only
if the Perron vector of ${\bf A}+{\bf A}^{\\!\top}$ is in the null space of
${\bf A}-{\bf A}^{\\!\top}$.

###### Proof.

Bapat [1] and Fiedler [5] proved that $r((1{-}t){\bf A}+t{\bf A}^{\\!\top})$
is constant in $t\in[0,1]$ if and only if the left and right Perron vectors of
${\bf A}$ are colinear. Suppose the left and right Perron vectors of ${\bf A}$
are colinear. Without loss of generality, they can be normalized to sum to $1$
in which case they are identical. Let the left and right Perron vectors of
${\bf A}$ be ${\bf x}$. Then

$\displaystyle\frac{1}{2}({\bf A}+{\bf A}^{\\!\top}){\bf x}$
$\displaystyle=r({\bf A})\ {\bf x},$ and $\displaystyle({\bf A}-{\bf
A}^{\\!\top}){\bf x}$ $\displaystyle=r({\bf A})\ ({\bf x}-{\bf x})={{\bf 0}}.$

Hence ${\bf x}$ is the Perron vector of ${\bf A}+{\bf A}^{\\!\top}$ and ${\bf
x}>{{\bf 0}}$ is in the null space of ${\bf A}-{\bf A}^{\\!\top}$.

For the converse, let the Perron vector of ${\bf A}+{\bf A}^{\\!\top}$ be
${\bf x}>{{\bf 0}}$, and let ${\bf x}$ be in the null space of ${\bf A}-{\bf
A}^{\\!\top}$. Then

$\displaystyle({\bf A}+{\bf A}^{\\!\top}){\bf x}$ $\displaystyle=r({\bf
A}{+}{\bf A}^{\\!\top})\ {\bf x}\text{ and }({\bf A}-{\bf A}^{\\!\top}){\bf
x}={\bf A}{\bf x}-{\bf A}^{\\!\top}{\bf x}={{\bf 0}},$

which gives

$\displaystyle{\bf A}{\bf x}$ $\displaystyle=\frac{1}{2}[({\bf A}+{\bf
A}^{\\!\top})+({\bf A}-{\bf A}^{\\!\top})]{\bf x}=\frac{1}{2}r({\bf A}{+}{\bf
A}^{\\!\top})\ {\bf x}+{{\bf 0}}=\frac{r({\bf A}{+}{\bf A}^{\\!\top})}{2}\
{\bf x}$ and $\displaystyle{\bf A}^{\\!\top}{\bf x}$
$\displaystyle=\frac{1}{2}[({\bf A}+{\bf A}^{\\!\top})-({\bf A}-{\bf
A}^{\\!\top})]{\bf x}=\frac{1}{2}r({\bf A}{+}{\bf A}^{\\!\top})\ {\bf x}-{{\bf
0}}=\frac{r({\bf A}{+}{\bf A}^{\\!\top})}{2}\ {\bf x}$

hence ${\bf x}$ is a Perron vector of ${\bf A}$ and of ${\bf A}^{\\!\top}$. ∎

######  Corollary 12.

Let ${\bf S}={\bf S}^{\\!\top}\in\mathbb{R}^{n\times n}$ be a nonnegative
irreducible symmetric matrix, and ${\bf K}=-{\bf
K}^{\\!\top}\in\mathbb{R}^{n\times n}$ be a nonsingular skew symmetric matrix
such that ${\bf A}={\bf S}+{\bf K}\geq{{\bf 0}}$. Then $n$ is even and ${\bf
A}$ has a non-constant Levinger’s function.

###### Proof.

If ${\bf K}$ is a nonsingular skew symmetric matrix, $n$ must be even, since
odd-order skew symmetric matrices are always singular [6, 2-9.27]. If ${\bf
C}(p):={\bf S}+p\,{\bf K}$ with ${\bf K}$ nonsingular, then because the null
space of ${\bf K}$ is $\\{{{\bf 0}}\\}$, ${\bf C}(p)$ must have a non-constant
Levinger’s function $c(p)$ by Theorem 11. ∎

The following corollary pursues the observation made by an anonymous reviewer
that a matrix ${\bf A}$ with colinear left and right Perron vectors is
orthogonally similar to a direct sum $\begin{pmatrix}r({\bf
A})\end{pmatrix}\oplus{\bf F}$ for some square matrix ${\bf F}$. This entails
that the skew symmetric part of ${\bf A}$ is orthogonally similar to
$\begin{pmatrix}r({\bf A})-r({\bf A})\end{pmatrix}\oplus({\bf F}-{\bf
F}^{\\!\top})/2=\begin{pmatrix}0\end{pmatrix}\oplus({\bf F}-{\bf
F}^{\\!\top})/2$, and is thus singular.

######  Corollary 13.

Let ${\bf S}={\bf S}^{\\!\top}\in\mathbb{R}^{n\times n}$ be a nonnegative
irreducible symmetric matrix, and ${\bf K}=-{\bf
K}^{\\!\top}\in\mathbb{R}^{n\times n}$ be a skew symmetric matrix, such that
${\bf A}={\bf S}+{\bf K}\geq{{\bf 0}}$. Let ${{\bf Q}}=({{\bf
Q}}^{\\!\top})^{-1}$ be an orthogonal matrix that diagonalizes ${\bf S}$ to

$\displaystyle{\boldsymbol{\Lambda}}$ $\displaystyle\,{:=}\,{{\bf
Q}}^{\\!\top}{\bf S}{{\bf Q}}=\begin{pmatrix}r({\bf S})&0&\cdots&0\\\
0&\lambda_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\lambda_{n}\end{pmatrix}.$

Then ${\bf A}$ has a constant Levinger’s function if and only if

(18) $\displaystyle{\bf K}_{1}$ $\displaystyle\,{:=}\,{{\bf Q}}^{\\!\top}{\bf
K}{{\bf Q}}=\begin{pmatrix}0&{{\bf 0}}^{\\!\top}\\\ {{\bf 0}}&{\bf
K}_{2}\end{pmatrix}=\begin{pmatrix}0\end{pmatrix}\oplus{\bf K}_{2},$

where ${\bf K}_{2}=-{\bf K}_{2}^{\\!\top}\in\mathbb{R}^{n{-}1\times n{-}1}$
and ${{\bf 0}}^{\\!\top}=(0\ldots 0)\in\mathbb{R}^{n{-}1}$.

###### Proof.

Since ${\bf S}$ is real and symmetric, ${\bf S}={{\bf
Q}}{\boldsymbol{\Lambda}}{{\bf Q}}^{\\!\top}$ is in Jordan canonical form. Let
${\bf x}>{{\bf 0}}$ be the normalized Perron vector of ${\bf S}$. Then ${\bf
x}=[{{\bf Q}}]_{1}$ is the first column of ${{\bf Q}}$, and the other columns
of ${{\bf Q}}$ are orthogonal to ${\bf x}$, so ${\bf x}^{\\!\top}{{\bf
Q}}=(1\>0\cdots 0)$. The necessary and sufficient condition from Theorem 11
for ${\bf A}$ to have constant Levinger’s function is that ${\bf
x}^{\\!\top}{\bf K}={{\bf 0}}^{\\!\top}$, equivalent to

$\displaystyle{\bf x}^{\\!\top}{\bf K}$ $\displaystyle={\bf x}^{\\!\top}{{\bf
Q}}{\bf K}_{1}{{\bf Q}}^{\\!\top}=(1\>0\cdots 0){\bf K}_{1}{{\bf
Q}}^{\\!\top}={{\bf 0}}^{\\!\top}.$

Since ${{\bf Q}}$ is orthogonal, it has null space $\\{{{\bf 0}}\\}$, so
$(1\>0\cdots 0){\bf K}_{1}{{\bf Q}}^{\\!\top}={{\bf 0}}^{\\!\top}$ if and only
if $(1\>0\cdots 0){\bf K}_{1}={{\bf 0}}^{\\!\top}$, which is the top row of
${\bf K}_{1}$. ${\bf K}_{1}$ and ${\bf K}_{2}$ must be skew symmetric since
${\bf K}$ is skew symmetric, as can be seen immediately from transposition.
The skew symmetry of ${\bf K}_{1}$ implies its first column must also be all
zeros as its first row is, establishing the form given in (18). ∎

##  5\. Conclusions

We have shown that it is not in general true that the spectral radius along a
line from a nonnegative square matrix ${\bf A}$ to its transpose — Levinger’s
function — is concave. Our counterexamples to concavity have a simple
principle in the case of direct sums of block matrices, namely, that the
maximum of two concave functions need not be concave. However, for the other
examples we present — Toeplitz matrices, and positive circuit or cyclic
weighted shift matrices — whatever principles underly the nonconcavity remain
to be discerned. Also remaining to be discerned are the properties of matrix
families — a few of which we have presented here — that guarantee concave
Levinger functions. A general characterization of the range of $t$ for which
the spectral radius is concave in Levinger’s homotopy remains an open problem.

## Biographical Note

Bernard W. Levinger (Berlin, Germany, September 3, 1928 – Fort Collins,
Colorado, USA, January 17, 2020) and his family fled Nazi Germany to England
in 1936, to Mexico in 1940, and to the United States in 1941, which initially
placed them in an immigration prison and deported them to Mexico, but which
ultimately allowed their immigration, whereupon they settled in New York City.
Levinger graduated from Bronx High School of Science and earned a doctorate in
mathematics from New York University. He was Professor of Mathematics and
Professor Emeritus at Colorado State University, Fort Collins. He leaves a
large family, including his wife Lory of more than 65 years.[15]

## Acknowledgements

L.A. thanks Marcus W. Feldman for support from the Stanford Center for
Computational, Evolutionary and Human Genomics and the Morrison Institute for
Population and Resources Studies, Stanford University; the Mathematical
Biosciences Institute at The Ohio State University, for its support through
U.S. National Science Foundation awards DMS-0931642 and DMS-1839810, “A Summit
on New Interdisciplinary Research Directions on the Rules of Life”; and the
Foundational Questions Institute and Fetzer Franklin Fund, a donor advised
fund of Silicon Valley Community Foundation, for FQXi Grant number FQXi-RFP-
IPW-1913. J.E.C. thanks the U.S. National Science Foundation for grant
DMS-1225529 during the initial phase of this work and Roseanne K. Benjamin for
help during this work.

## References

  * Bapat [1987] Bapat, R.B., 1987.  Two inequalities for the Perron root.  Linear Algebra and Its Applications 85, 241–248.
  * Bapat and Raghavan [1997] Bapat, R.B., Raghavan, T.E.S., 1997\.  Nonnegative Matrices and Applications.  Cambridge University Press, Cambridge, UK.
  * Böttcher and Grudsky [2005] Böttcher, A., Grudsky, S.M., 2005\.  Spectral Properties of Banded Toeplitz Matrices.  Society for Industrial and Applied Mathematics, Philadelphia, PA.  doi:10.1137/1.9780898717853.
  * Chien and Nakazato [2020] Chien, M.T., Nakazato, H., 2020\.  Symmetry of cyclic weighted shift matrices with pivot-reversible weights.  The Electronic Journal of Linear Algebra 36, 47–54.
  * Fiedler [1995] Fiedler, M., 1995.  Numerical range of matrices and Levinger’s theorem.  Linear Algebra and Its Applications 220, 171–180.
  * Hogben [2014] Hogben, L. (Ed.), 2014.  Handbook of Linear Algebra.  2nd ed., Chapman and Hall, Boca Raton, FL.
  * Horn and Johnson [2013] Horn, R.A., Johnson, C.R., 2013\.  Matrix Analysis.  2nd ed., Cambridge University Press, Cambridge.
  * Levinger [1970] Levinger, B.W., 1970.  An inequality for nonnegative matrices.  Notices of the American Mathematical Society 17, 260.  URL: http://www.ams.org/journals/notices/197001/197001FullIssue.pdf.
  * Marek [1974] Marek, I., 1974.  An inequality involving positive kernels.  Časopis pro Pěstování Matematiky 99, 77–87.
  * Marek [1978] Marek, I., 1978.  Perron root of a convex combination of a positive kernel and its adjoint.  Acta Universitatis Carolinae. Mathematica et Physica 19, 3–14.
  * Marek [1984] Marek, I., 1984.  Perron roots of a convex combination of a cone preserving map and its adjoint.  Linear Algebra and Its Applications 58, 185–200.
  * Psarrakos and Tsatsomeros [2003] Psarrakos, P.J., Tsatsomeros, M.J., 2003\.  The Perron eigenspace of nonnegative almost skew-symmetric matrices and Levinger’s transformation.  Linear Algebra and Its Applications 360, 43–57.
  * Stanczak et al. [2009] Stanczak, S., Wiczanowski, M., Boche, H., 2009.  Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms. volume 3.  Springer Science & Business Media.
  * Tsing et al. [1994] Tsing, N.K., Fan, M.K., Verriest, E.I., 1994.  On analyticity of functions involving eigenvalues.  Linear Algebra and Its Applications 207, 159–180.
  * [15] Bernard Levinger, 1928–2020.  URL: https://www.legacy.com/obituaries/coloradoan/obituary.aspx?n=bernard-levinger&pid=195155578.


# Tree-structured Auxiliary Online Knowledge Distillation
††thanks: This research is supported by National Natural Science Foundation of
China (Grant No. 6201101015) , Beijing Academy of Artificial
Intelligence(BAAI), Natural Science Foundation of Guangdong Province (Grant
No. 2021A1515012640), the Basic Research Fund of Shenzhen City (Grant No.
JCYJ20210324120012033 and JCYJ20190813165003837), National Key R&D Program of
China (No. 2021ZD0112905)and Overseas Cooperation Research Fund of Tsinghua
Shenzhen International Graduate School (Grant No. HW2021008).

1st Wenye Lin  Tsinghua Shenzhen International Graduate School
Tsinghua University
Shenzhen, China
<EMAIL_ADDRESS>2nd Yangning Li  Tsinghua Shenzhen International
Graduate School
Tsinghua University
Shenzhen, China
<EMAIL_ADDRESS>3rd Yifeng Ding  Tsinghua Shenzhen International
Graduate School
Tsinghua University
Shenzhen, China
<EMAIL_ADDRESS>4th Hai-Tao Zheng *Corresponding author.
Tsinghua Shenzhen International Graduate School
Tsinghua University
Shenzhen, China
<EMAIL_ADDRESS>
###### Abstract

Traditional knowledge distillation adopts a two-stage training process in
which a teacher model is pre-trained and then transfers the knowledge to a
compact student model. To overcome the limitation, online knowledge
distillation is proposed to perform one-stage distillation when the teacher is
unavailable. Recent researches on online knowledge distillation mainly focus
on the design of the distillation objective, including attention or gate
mechanism. Instead, in this work, we focus on the design of the global
architecture and propose Tree-Structured Auxiliary online knowledge
distillation (TSA), which adds more parallel peers for layers close to the
output hierarchically to strengthen the effect of knowledge distillation.
Different branches construct different views of the inputs, which can be the
source of the knowledge. The hierarchical structure implies that the knowledge
transfers from general to task-specific with the growth of the layers.
Extensive experiments on 3 computer vision and 4 natural language processing
datasets show that our method achieves state-of-the-art performance without
bells and whistles. To the best of our knowledge, we are the first to
demonstrate the effectiveness of online knowledge distillation for machine
translation tasks. 111Code is available at https://github.com/Linwenye/Tree-
Supervised.

###### Index Terms:

online knowledge distillation, ensemble learning, neural machine translation

##  I Introduction

Deep neural networks have led to a series of successes in computer vision and
natural language processing [17]. They show superiority in representing
complex concepts due to the large size of parameters [15]. However, the
cumbersome neural networks are computationally expensive, hindering their
applications in real-world problems with limited resources. To this end,
knowledge distillation [12] is proposed to transfer the knowledge from a large
teacher model to a compact student model.

Traditional knowledge distillation requires a two-stage training process, in
which a high-capacity teacher model is pre-trained in the first stage, and
then transfers the knowledge of the teacher to a compact student model in the
second stage [12, 3]. This two-stage process increases the pipeline complexity
and training cost. To simplify the distillation procedure, online knowledge
distillation [32, 16] is proposed, which simultaneously trains a set of
student models and distills their knowledge from each other in a peer-teaching
manner. This approach requires a one-stage learning procedure and leverages
peer network to provide the teacher knowledge. Recent researches on online
knowledge distillation aim at improving the quality of the knowledge learned
from peers. ONE [16] and CL-ILR [23] introduces an ensemble teacher which
gathers the students’ knowledge with a gate mechanism. OKDDip [6] further
boosts the performance by maintaining the peer variety through an attention
mechanism. These approaches mainly focus on the design of the distillation
objective.

By contrast, in this work, we demonstrate that the design of the overall
architecture for online knowledge distillation is another key factor for the
performance of the student model. We adopt the original distillation objective
as that in DML [32] without bells and whistles, and show that the tree
structure for online knowledge distillation is the key to our state-of-the-art
performance. We propose a unified framework, the tree-structured auxiliary
online knowledge distillation (TSA). During training, TSA hierarchically adds
more auxiliary peers in later layers, which naturally forms a tree structure
(See Fig. 1). Different branches construct different views of the inputs,
which can be the source of the knowledge. The hierarchical structure implies
that the knowledge transfers from general to task-specific with the growth of
the layers. Each branch of the tree is trained with joint objective loss
terms: a conventional softmax cross-entropy loss to match the ground-truth
hard labels, and a distillation loss that aligns each classifier’s class
posterior with the class probabilities of peers. The whole tree is trained
together, with the sum of loss from every classifier as the overall loss. At
the inference stage, all auxiliary modules are removed to keep the original
architecture unchanged, thereby making the framework feasible to be put into
deployment. Extensive experiments on both computer vision and natural language
processing tasks show that our method is simple but effective and generalizes
well to different domains.

Our main contributions are summarized as below:

  1. 1.

We introduce tree-structured auxiliary online knowledge distillation, a
unified framework for online knowledge distillation. The framework is simple
but effective. We show that the tree structure is another key factor for the
performance and provide a general perspective to get better understanding of
online knowledge distillation. This could inspire new effective methods.

  2. 2.

We implement two variants of TSA: a balanced tree and an unbalanced tree.
Experiments show significant improvements in our method over vanilla training
and existing online knowledge distillation methods. Typically, with online
knowledge distillation of the balanced variant, all the networks gain an
average of 3% to 4% improvement in accuracy on CIFAR-100, where MobileNetV3
and ResNet-18 reach the best accuracies ever reported for these architectures.
On ImageNet, ResNet-34 obtains 74.97% accuracy, which is 1.8% above the
vanilla one.

  3. 3.

To the best of our knowledge, we are the first to demonstrate the
effectiveness of online knowledge distillation for machine translation. On
IWSLT translation tasks, we gain an average of 0.9 BLEU improvement over
vanilla Transformer for three datasets. Experiment on large-scale translation
task WMT’17 reveals that our method generalizes well to large datasets.

Figure 1: Deep tree-structured auxiliary online knowledge distillation
example. On the left is an original network. On the right is training the
network with TSA. In this example, we split the original network into three
layers in a tree, and add replicas with different initialization to form a
binary tree during training. Every classifier is trained to learn from both
hard labels and soft targets from peers. At inference time, replicas are
removed and the whole network recovers to the original architecture. With this
tree manner, block on layer 1 is supervised by four classifiers, while block
on layer 2 is supervised by two. Earlier layers are given more powerful
“instructions” from more classifiers. Because of different initialization,
multiple branches provide various and abundant information to extract robust
features for down-stream tasks.

##  II Related work

###  II-A Knowledge Distillation

Knowledge distillation is a ubiquitous technique for model compression and
acceleration. It trains a smaller student model to imitate the output
distribution of a larger teacher model via a $L_{2}$ loss on logits (i.e.
before Softmax) [3] or cross-entropy [12]. Recently, many researches attempt
to further improve the performance by discovering different knowledge from the
teacher, such as intermediate representations [21], attention maps [28], and
flow of solution process (FSP) [26]. However, the limitation to these methods
is that they need a pre-trained teacher and conduct a two-stage distillation
process.

###  II-B Deeply Supervised Nets

Deeply supervised nets (DSN) [18] emphasizes the direct supervision on
intermediate layer by introducing classifier to each layer, aiming at
extracting more discriminative features. Self-distill [31] further facilitates
this kind of supervision on hidden layers through distilling knowledge from
the later classifier to earlier ones. However, a deeply supervised method may
downgrade the performance of deep nets. Features transition from general to
specific by layer-by-layer transformation [27, 30]. But DSN breaks the
procedure by direct supervision on earlier layers. Our method retains this
procedure in deep nets, while yielding more variety in later layers.

###  II-C Multi-branch Online Knowledge Distillation

Deep mutual learning [32], co-teaching [9] and co-distillation [2] differ from
previous methods. They enhance robustness or accuracy from training two or
more networks simultaneously and let them teach each other during training.
ONE [16] and CL-ILR [23] construct auxiliary branches and let each branch
learn from an ensemble teacher with a gate. OKDDip [6] gains some performance
from boosting peer diversity by introducing attention mechanism. The wisdom
behind these methods resembles ensemble learning, but the difference is that
every network will benefit from the knowledge taught by others during
training, while ensemble learning works at inference time by gathering the
knowledge together.

##  III Tree-structured auxiliary online knowledge distillation

###  III-A A Unified Framework

Our TSA offers a unified perspective on designing architecture for online
knowledge distillation. TSA dispenses with redesigning auxiliary modules, and
leverages the original network block. We describe the framework as follows:
for a target network, our TSA first splits the original network by depth into
a few parts (i.e. network block), then adds more counterparts for ones close
to the output layer, forming a tree structure. (Examples are shown in Fig. 1.)
Different initialization for each branch provide different view of the inputs
and is the source of the knowledge transferred to each other. Sharing the same
early layers not only cuts down the computational cost but also increases the
performance of the overall architecture. We will discuss the underlying
reasons in the following section. For a batch of data, inputs flow from the
root to every leaf along all the branches simultaneously. Knowledge
distillation is performed for outputs from every leaf. The whole tree is
trained collaboratively to minimize a global loss during training. At
inference time, auxiliary modules are removed to recover the architecture to
the target network. However, if there is less constraint on computation budget
and the performance is crucial, the ensemble model with all the auxiliary
modules can be deployed.

Existing researches design architectures with auxiliary modules in a heuristic
way. We propose a unified perspective here. DML[32] can be interpreted as
adding counterparts for every part of a network; ONE[16] and CL-ILR[23] add
counterparts only for later part in a network. TSA is a general framework,
rather than any specific method. The overall architecture is determined with
the configuration: which part of a network to duplicate, and the number of the
duplication. It is flexible enough to be translated into different
architecture suitable for specific scenario. Our TSA provides a general
perspective to get better understanding of online knowledge distillation, and
may inspire new effective training methods.

Based on our framework, we propose two different settings of TSA. Fig. 2(a)
represents a balanced tree setting, Fig. 2(b) represents an unbalanced one.
Experiments show that the balanced tree setting has stronger regularization
effect than the unbalanced one, thus yielding comparable or better
performance. So we adopt the balanced tree as default setting of our TSA.

TSA-M-H denotes a balanced tree of depth H, and internal node of the tree has
M children. Thus this tree forms $M^{H-1}$ branches. Fig. 2(a) shows a case of
TSA-2-3. We also explore trees with more depth and more children in Section
IV-A, which requires more training cost but further boosts the performance. We
adopt TSA-2-3 as our default setting for TSA.

(a) Balanced tree

(b) Unbalanced tree

Figure 2: Two different settings of TSA. Left: balanced tree. Right:
unbalanced tree.

###  III-B Formulation

#### Softmax Function

Given N samples $X=\\{x_{i}\\}_{i=1}^{N}$ from $T$ classes, the corresponding
label set is denoted as $Y=\\{y_{i}\\}_{i=1}^{N},y_{i}\in\\{1,2,\cdots,T\\}$.
We translate any original network into a tree structure by adding auxiliary
duplicate modules. Classifier on every branch is denoted as $\Theta_{k}$,
where $k\in\\{1,2,\cdots,K\\}$. Classifier $\Theta_{k}$ produce class
probabilities by applying the softmax:

$p_{i}=\frac{exp(z_{i}/T)}{\sum_{j}exp(z_{j}/T)},$ (1)

where the logit $z$ is the input to the final softmax, and $p_{i}$ is the
$i^{th}$ class probability of classifier $\Theta_{k}$. T is temperature that
is normally set to 1 to represent the cross-entropy. Higher value for T
produces a softer probability distribution over class for distillation. [12]

#### Joint Loss Function

Classifier $\Theta_{k}$ is trained with two loss terms. The first is a
conventional cross-entropy loss to match the ground-truth labels:

$L_{C_{k}}=-\sum_{i,t}\delta_{i,t}\log{p_{i,t}},$ (2)

where $\delta_{i,t}=0$ if $y_{i}=t$, otherwise $\delta_{i,t}=1$. This loss
trains the network to predict correct labels for training datasets. The second
loss is the Kullback Leibler (KL) Divergence to quantify the match of
prediction $p_{k}$ to its peers.

$L_{D_{k}}=\frac{1}{K-1}\sum_{j\neq{k}}KL(p_{k}||p_{j})$ (3)

We perform distillation for every branch respectively, and this equation is in
a symmetric form, although KL Divergence itself is not symmetric. The KL
Divergence is calculated as below:

$KL(p_{k}||p_{j})=\sum_{j\neq{k}}\sum_{i,t}p_{k}^{t}(x_{i})\log{\frac{p_{k}^{t}(x_{i})}{p_{j}^{t}(x_{i})}}$
(4)

This loss enables knowledge distillation from peers to improve generalization
performance on test sets. It is important to distil from each peer
respectively, rather than distil from an average ensemble one. This provides
enough variety and dispenses with extra effort on designing delicate
mechanisms such as attention. We then obtain the overall loss for TSA as:

$L=\sum_{k}{[(1-\alpha)*L_{C_{k}}+\alpha*T^{2}*L_{D_{k}}]},$ (5)

where $\alpha$ is a hyperparameter to control the contribution of cross-
entropy loss and distillation loss.

###  III-C Theoretical Insights

Let $h^{l}(x)\in R^{d}$ denote the output from the $l$-th layer of a neural
network with input $x$. Then the output logit from the network is
$q(y|x)=softmax(linear(h^{L}(...(h^{1}(x)))))$. We add more parallel later
layers with different initialization with TSA. Let $h^{l}_{i}(x)$ denote the
$i$-th peer, at layer $L$ , $i\in\\{1,2,...,K\\}$, which means the network has
total K branches after adding auxiliary blocks.

The TSA enhanced training can be formulated as the constrained optimization
problem:

$argmin_{\xi}(1/n*\sum_{i=1}^{n}E[-log(p(y_{i}|x_{i}))]),$ $s.t.\ \
(1/n)*\sum_{i=1}^{n}E_{\Theta_{k},\Theta_{t}}[D_{KL}(p_{k}(y_{i}|x_{i})||p_{t}(y_{i}|x_{i}))]=0,$

where $\Theta_{k},\Theta_{t}$ denote two different branch, and $\xi$ denotes
the parameters of the network. The constraint from KL-divergence is equivalent
to constraining output from different branches to be equal. This reduces the
freedom of the parameters and the variance of individual solutions [19],
forming a wider minimum from the view of optimization landscape [31, 32].

Since every branch share the same earlier layers in our method, for the shared
parameters, they already satisfy the constraint in equation, which limit the
KL-divergence loss to only take effect in optimization of the later layers.

Note that the development of deep learning theory is still at its infancy
stage. And why knowledge distillation works is still in dispute [20, 1]. We
make some conjecture for the reason why the tree-structure boosts the
performance of onine knowledge distillation based on our discussion above:
earlier layers are extracting more general features, while layers close to the
output are more task-specific. So only adding more branches for later layers
improves the generalization to the target task, and leads to a broader
optimization minimum. Different branches construct different views of the
inputs, which can be the source of the knowledge. The hierarchical structure
implies that the knowledge transfers from general to task-specific with the
growth of the layers. We believe this is an important problem and leave more
detailed analysis to our future work.

##  IV Experiments

TABLE I: Top-1 Accuracy (%) on CIFAR-100 compared with other multi-branch methods. Our TSA adopts the TSA-2-3 version as Fig. 2(a). “-E”: ensemble result. The results reported for other methods are reproduced with the same setting. All the methods are with 4 branches for fair comparison. We report accuracy for single branch (without “-E”) and 4-branch ensemble result. Our method outperforms other representative online knowledge distillation methods.  Method | ResNet-32 | VGG-16 | ResNet-110 | MobileNetV3 | WRN-28-10
---|---|---|---|---|---
Baseline | 70.78 | 73.81 | 75.88 | 74.51 | 78.49
DML [32] | 74.01 | 75.44 | 76.33 | 72.56 | 80.28
ONE [16] | 73.84 | 74.50 | 77.72 | 76.11 | 81.67
OKDDip [6] | 73.99 | 74.53 | 78.60 | 75.73 | 80.88
TSA | 74.57 | 76.58 | 79.75 | 78.93 | 82.13
ONE-E | 75.08 | 74.51 | 79.85 | 76.23 | 82.23
OKDDip-E | 75.74 | 74.44 | 79.62 | 77.47 | 81.82
TSA-E | 76.69 | 78.28 | 81.96 | 79.62 | 83.03
Figure 3: Training curve of top-1 Accuracy (%) for ResNet-18 on ImageNet. We compare the performance of the original structure and the tree-structured model during training and testing. TABLE II: Top-1 Accuracy (%) on CIFAR-100 compared with other deeply supervised methods. ”Single”: accuracy of a single classifier. ”*”: reported by [31]. Our method outperforms other methods by a large margin. U-TSA: unbalanced TSA showed in Fig. (2(b)). Model | Single | Ensemble
---|---|---
DSN | Self-distill | U-TSA | TSA | DSN | Self-distill | U-TSA | TSA
VGG-19 | - | 68.03* | 73.62 | 74.03 | - | 68.54* | 74.83 | 75.94
ResNet-18 | 78.38* | 78.64* | 80.76 | 81.43 | 79.27* | 79.67* | 82.13 | 82.43

###  IV-A Image Classification

#### Datasets

CIFAR-100 dataset [14] consists of $32\times 32$ color images drawn from 100
classes split into 50000 train and 10000 test images. We apply standard data
augmentation (translation and mirrorings) on this dataset. ImageNet-1K 2012
[7] provides 1.2 million images for training, and 50k for validation. We
report accuracy of ImageNet on the validation set, which is the standard
process. We also include the experimental results on CIFAR-10 in a subsection.

#### Implementation Details

On CIFAR-100, we conduct all experiments on two NVIDIA GeForce GTX 1080 Ti
GPUs. The initial learning rate is set to 0.1 and mini-batch size to 128. For
ResNet and VGG, we adopt the same settings as [16] for fair comparisons.
Learning rate drops by 0.1 at 50% and 75% training of total 300 training
epochs. For MobileNetV3, we remove the first two pooling layers following [8]
and train for 200 epochs with a weight decay of 0.0002. Learning rate decays
by a factor of 0.1 at epochs 100, 150, and 180. For WideResNet, we follow [32]
to train for 200 epochs and learning rate drops by 0.1 every 60 epochs. On
ImageNet, experiments are conducted on four NVIDIA GeForce GTX 3090 GPUs. We
adopt the official code from PyTorch.
222https://github.com/pytorch/examples/tree/master/imagenet Initial learning
rate is 0.1 and decay by 0.1 every 30 epochs for total of 100 epochs. We adopt
the balanced tree setting as the default setting for TSA. We report the
results with average 3 runs.

#### Comparison between the Tree Settings

We compare the balanced tree setting and the unbalanced tree setting. We
denote the unbalanced tree as ”U-TSA”. Table II shows that TSA with balanced
tree yields better performance than the unbalanced tree on CIFAR-100, however,
on a larger dataset (ImageNet), these two settings have comparable results.
(Shown in Table III.) This observation implies that the balanced tree has more
regularizing effect due to the symmetric architecture. Large dataset
alleviates the problem of overfitting, hence similar performance for these two
settings. Without extra clarification, we adopt the balanced tree setting as
the default setting below.

#### Comparison with Vanilla Training

Results are shown in Table I. Note that in our method, we just keep the
hyperparameters the same as the baseline and already get satisfying
performance. Further tuning the hyperparameters may lead to further
improvements. (See Fig. 4.) We evaluate our method with different networks,
namely VGG-16 [22], ResNet-32, ResNet-110 [10], MobileNetV3 [13], and
WRN-28-10 [29]. We use a large version for MobileNetV3.

We focus on the accuracy boost of each method for target networks and ensemble
networks. TSA gains an average of 3.52% accuracy improvement over vanilla
training. Improvements are consistent among non-residual network (VGG-16),
very deep network (ResNet-110) and wide network (WRN-28-10). It is worth
mentioning that on MobileNetV3, we achieve top-1 accuracy of 78.93%, which is
1.23% above the best number ever reported for this architecture.

We observe that our method enhances more performance on models with complex
architecture. ResNet-110 is deeper, WRN-28-10 is wider, and MobileNetV3
incorporates Squeeze-and-Excitation architecture which is more difficult to
optimize. TSA enables these more complex architectures to converge to better
minima. The same phenomenon is observed in Table III. ResNet-34 with TSA
yields more significant improvement than ResNet-18 on ImageNet.

Fig. 3 shows the training and testing accuracy curve of ResNet18 with TSA and
a vanilla one. We observe that the model yields higher test accuracy but lower
training accuracy. This shows that our TSA acts as a regularizer, and
knowledge distilling from peers still takes effect in the large dataset
without extra knowledge.

TABLE III: Top-1 Accuracy (%) on ImageNet. “Single”: result for a single branch target network. “Ensemble”: ensemble result for 4 branches. We simply average the outputs from these 4 branches as the ensemble. Model | Single | Ensemble
---|---|---
Vanilla | U-TSA | TSA | U-TSA | TSA
ResNet18 | 70.14 | 70.80 | 70.74 | 71.91 | 72.13
ResNet34 | 73.24 | 74.93 | 75.03 | 76.22 | 76.47

#### Comparison with Multi-branch Methods

We compare our TSA method with several representative multi-branch training
methods, including DML [32], ONE [16] and OKDDip [6]. Table I reveals that our
method outperforms other representative online knowledge distillation methods
consistently. For fair comparison, we reproduce other methods with the same
experimental setting and report the number for average 3 runs. Methods with
”-E” means ensemble result. For ensemble results, all the methods are reported
with 4-branch ensemble. Our TSA-E only simply averages the outputs from all
the classifiers, but still outperforms other methods by a significant margin,
which utilize complex components such as diversity and attention to get the
ensemble model. This phenomenon implies that though we perform knowledge
distillation between peers, some variety still exists in each branch.

Figure 4: Top-1 Accuracy (%) for ResNet-32 on CIFAR-100 with different weight
decay. Our method is steadily above the baseline.

#### Comparison with Deeply Supervised Methods

We compare our TSA with DSN [18] and self-distillation [31] for networks
VGG-19 [22] and ResNet-18 [10]. We adopt the same setting as [31] for a fair
comparison. Results are shown in Table II. Our TSA outperforms others by a
large margin. It is worth mentioning that ResNet-18 achieves an 81.43%
accuracy with TSA, which even has higher accuracy than the vanilla residual
network with over thousands of layers [11]. Results of ResNet-18 (wider than
ResNet-32) again show the favorable quality of our TSA, that TSA is more
powerful when the model is larger or deeper.

#### Comparison to Ensemble of Baseline Network

Table IV shows an example of comparison with ensemble results for vanilla
network without auxiliary training. Note that TSA aims at training a single
model to be more accurate and generalizable to the test data. That’s why only
single branch is left at test time. This resembles distilling knowledge from
an ensemble model into a single one. So the idea is not to surpass an ensemble
model, but to surpass the original model with the same parameter size.
However, we still provide the comparison on CIFAR-100 in Table IV for better
understanding of our method.

For ResNet-32, our method with single branch already outperforms 2-net
ensemble of baseline model, and for MobileNetV3, it yileds similar performance
with 4-net ensemble. Our TSA ensemble method yields best performance while
having less parameters than vanilla 4-net ensemble due to the sharing of early
layers.

TABLE IV: Top-1 accuracy of ResNet-32 on CIFAR-100 Method | ResNet-32 | MobileNetV3
---|---|---
Vanilla single net | 70.78 | 74.51
2-net ensemble | 73.42 | 77.34
3-net ensemble | 75.06 | 78.51
4-net ensemble | 75.69 | 78.97
TSA single branch | 74.12 | 78.93
TSA 4-branch ensemble | 76.69 | 79.62

#### Hyperparameter Sensitivity

We train ResNet-32 with different weight decay values ranging from 0.0002 to
0.0006. Fig. 4 shows that with different hyperparameters, the accuracy of
ResNet-32 trained by TSA is steadily higher than the baseline in a relatively
fixed range. That is to say, there is no need to pay great effort to search
for the appropriate hyperparameters when applying our method. We also observe
that the results reported in Table I can be further improved, with more effort
to find the best hyperparameter setting. In this case, with weight decay
0.0003, the accuracy 74.57% is higher than that with the default setting.

#### Component Analysis

Table VI shows component analysis results for different configuration for our
TSA. TSA-M-H denotes training a model with an M-branch balanced tree of depth
H. With distillation, the target model sees significant improvements. For a
single target network, knowledge distillation facilitates the models to
improve 1.98% on average, compared with model without distillation.
Specifically, TSA-2-4 performs best which suggests that TSA with more layers
and peers distills fine-grained knowledge into each block. However, simple
addition of branches gains little accuracy profit for ”TSA-3-3”. Meanwhile,
TSA without distillation performs better than baseline reported in Table I,
which implies that training all the sub-networks together yields more
generalization. For the ensemble networks, without constraints of
distillation, more classifiers means higher accuracy.

#### CIFAR-10 Results for TSA

Table V shows experiment results on CIFAR-10. For CIFAR-10 dataset, we follow
the same experimental setting as CIFAR-100. We report comparison with former
state-of-the-art method OKDDDip [6]. Our method gains steady improvement upon
baseline, while OKDDip suffers from unstability and sometimes sees performance
decrease. The same problem is also observed for other auxiliary training
methods in our experiments on CIFAR-10.

TABLE V: Top-1 accuracy on CIFAR-10 dataset. Model | Baseline | OKDDip | TSA | TSA-E
---|---|---|---|---
ResNet-18 | 95.40 | - | 95.83 | 96.33
ResNet-32 | 93.66 | 93.48 | 94.47 | 95.08
MobileNetV3 | 92.40 | 91.79 | 94.39 | 94.63
ResNet-110 | 94.41 | 95.04 | 95.20 | 95.62
TABLE VI: Top-1 Accuracy (%) for ResNet-32 on CIFAR-100. “Single”: accuracy of a single target network trained by TSA. “w/ distil” means that distillation is performed for outputs from different branch (See Equation 3), and “w/o distil” vice versa. Configuration | TSA-2-3 | TSA-3-3 | TSA-2-4
---|---|---|---
Single w/o distil | 72.24 | 72.50 | 72.37
Ensemble w/o distil | 77.14 | 78.70 | 78.38
Single w/ distil | 74.12 | 74.17 | 74.65
Ensemble w/ distil | 76.69 | 77.46 | 77.78

###  IV-B Neural Machine Translation

#### Datasets

We use 4 widely used dataset for translation task, including IWSLT’14 De-En
[5], IWSLT’17 {De, Fr}-En [4] and WMT’17 En-De [24]. We use the first three
datasets for small-scale translation tasks. And the larger WMT’17 dataset
consists of about 4.5 million sentence pairs from WMT’14 [25], with additional
newstest14333http://nlp.stanford.edu/projects/nmt data for test. We split the
dataset into a shared source-target vocabulary of about 40000 tokens.

#### Implementation Details

We train both original Transformer model and tree-structured Transformer model
on one machine with 4 NVIDIA 3090 GPUs. The hyperparameter settings for both
models are identical, using an initial learning rate of 0.0005 and 0.0007 for
IWSLT series dataset and WMT’17 dataset, respectively. Each training batch
contains a set of sentence pairs with approximately 25,000 source and 25,000
target tokens. The models for IWSLT series dataset are trained for 30 epochs,
while each model for WMT’17 dataset is trained for a total of 80 epochs. In
terms of the model structure, each transformer encoder contains 6 identical
encoder layers, so do the decoders. Our focus is on the validity of TSA in
Transformer, but not on pushing the state-of-the-art results, so we simply
adopt a 2-layer tree to speed up the training. We use half-precision floating-
point numbers (FP16) during training.

Figure 5: BLEU for Transformer on WMT’17. We report the performance of the
original structure and tree-structured models in the last 40 training epochs.
In training, TSA Transformer consistently outperforms original Transformer.

#### Comparison with Original Transformer

To show that TSA likewise boosts the performance of models for natural
language processing tasks, we conduct comparative experiments on machine
translation. Considering that Transformer is ubiquitous in natural language
processing, and is extensively applied in computer vision recently, we compare
the performance of the original Transformer with our tree-structured
Transformer. We report the BLEU on the IWSLT series datasets and the results
are shown in Table VII. We observe that on these three small-scale datasets,
TSA obtains a stable gain of about 0.9 BLEU on average, illustrating the
effectiveness of TSA. Further, to demonstrate that TSA stabilizes the training
process, we report the BLEU in the last 40 epochs on the WMT’17 dataset. As
evident from Fig. 5, The BLEU curve of TSA shows a smooth and continuous
increase, compared to the sharp fluctuations of the original transformer.
During the training process, TSA Transformer performs steadily higher than the
original Transformer, illustrating the robustness of our training method. It
is promising that the performance will further improve if we train a tree with
more layers. The experiments on Transformer confirm that our TSA is able to
generalize from computer vision to natural language tasks.

TABLE VII: BLEU for translation tasks. “14”: IWSLT’14 translation dataset; “17”: IWSLT’17 translation dataset. We do not report results with other online knowledge distillation methods since none of previous methods have implemented application in Transformer.  Method | 14 De-En | 17 De-En | 17 Fr-En
---|---|---|---
Baseline | 34.4 | 27.6 | 36.6
TSA | 35.4 | 28.5 | 37.1

###  IV-C Training Cost

Table VIII shows the parameter size during training and Table IX shows
training time for various networks. Our method slightly costs more than ONE
and OKDDip for training. However, at deployment stage, since auxiliary
branches are removed, the parameter size and inference time are all the same
as baseline model. online knowledge distillation aims at training a better
model with less deployment cost rather than training cost. For example, a
vanilla ResNet-18 gets 78.18% accuracy on CIFAR-100 while ResNet-101 79.29%.
With TSL, we train the ResNet-18 to achieve 81.43% accuracy which is beyond
vanilla ResNet-101, with far less parameters.

TABLE VIII: Parameter size during training for different online knowledge distillation method. Model | DML | ONE | OKDDip | TSA
---|---|---|---|---
VGG-16 | 61.19M | 38.27M | 38.34M | 52.84M
MobileNetV3 | 11.21M | 10.68M | 10.91M | 10.83M
ResNet-32 | 1.89M | 1.55M | 1.55M | 1.64M
ResNet-110 | 6.92M | 3.85M | 3.87M | 6.00M
TABLE IX: Training time (seconds per epoch) on one Nvidia 2080 GPU on CIFAR-100 with batchsize is 128. Model | DML | ONE | OKDDip | TSA
---|---|---|---|---
VGG-16 | 39 | 20 | 21 | 27
MobileNetV3 | 94 | 54 | 56 | 61
ResNet-32 | 33 | 23 | 23 | 28
ResNet-110 | 134 | 54 | 54 | 59

##  V Discussion

In this work, we show that through careful design of the overall architecture
of the online knowledge distillation, our TSA achieves state-of-the-art
performance with the vanilla online distillation loss function. We introduce a
unified framework for architecture design of online knowledge distillation and
propose two different settings of TSA and demonstrates the superiority of our
method over existing methods. Experiments on both image classification tasks
and translation task certify the effectiveness of TSA. We are the first to
demonstrate the effectiveness of online knowledge distillation for neural
machine translation task. Our method is simple and effective, and it is
promising that introducing advanced training objective [16, 6] will further
improve the performance of TSA. We leave that to our future work.

## References

  * [1] Zeyuan Allen-Zhu and Yuanzhi Li.  Towards understanding ensemble, knowledge distillation and self-distillation in deep learning.  arXiv preprint arXiv:2012.09816, 2020.
  * [2] Rohan Anil, Gabriel Pereyra, Alexandre Passos, Robert Ormandi, George E Dahl, and Geoffrey E Hinton.  Large scale distributed neural network training through online distillation.  In International Conference on Learning Representations, 2018.
  * [3] Jimmy Ba and Rich Caruana.  Do deep nets really need to be deep?  Advances in Neural Information Processing Systems, 27, 2014.
  * [4] Mauro Cettolo, Marcello Federico, Luisa Bentivogli, Niehues Jan, Stüker Sebastian, Sudoh Katsuitho, Yoshino Koichiro, and Federmann Christian.  Overview of the iwslt 2017 evaluation campaign.  In International Workshop on Spoken Language Translation, pages 2–14, 2017.
  * [5] Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico.  Report on the 11th iwslt evaluation campaign, iwslt 2014.  In Proceedings of the International Workshop on Spoken Language Translation, Hanoi, Vietnam, volume 57, 2014.
  * [6] Defang Chen, Jian-Ping Mei, Can Wang, Yan Feng, and Chun Chen.  Online knowledge distillation with diverse peers.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3430–3437, 2020.
  * [7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [8] Daniel Haase and Manuel Amthor.  Rethinking depthwise separable convolutions: How intra-kernel correlations lead to improved mobilenets.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14600–14609, 2020.
  * [9] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W Tsang, and Masashi Sugiyama.  Co-teaching: robust training of deep neural networks with extremely noisy labels.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8536–8546, 2018.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [12] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  stat, 1050:9, 2015.
  * [13] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al.  Searching for mobilenetv3.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1314–1324, 2019.
  * [14] Alex Krizhevsky et al.  Learning multiple layers of features from tiny images.  2009\.
  * [15] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [16] Xu Lan, Xiatian Zhu, and Shaogang Gong.  Knowledge distillation by on-the-fly native ensemble.  In NeurIPS, 2018.
  * [17] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [18] Chen-Yu Lee, Saining Xie, Patrick Gallagher, Zhengyou Zhang, and Zhuowen Tu.  Deeply-supervised nets.  In Artificial intelligence and statistics, pages 562–570. PMLR, 2015.
  * [19] Xiaobo Liang, Lijun Wu, Juntao Li, Yue Wang, Qi Meng, Tao Qin, Wei Chen, Min Zhang, and Tie-Yan Liu.  R-drop: Regularized dropout for neural networks.  arXiv preprint arXiv:2106.14448, 2021.
  * [20] Mary Phuong and Christoph Lampert.  Towards understanding knowledge distillation.  In International Conference on Machine Learning, pages 5142–5151. PMLR, 2019.
  * [21] Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio.  Fitnets: Hints for thin deep nets.  arXiv preprint arXiv:1412.6550, 2014.
  * [22] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [23] Guocong Song and Wei Chai.  Collaborative learning for deep neural networks.  Advances in Neural Information Processing Systems, 31:1832–1841, 2018.
  * [24] Yi Tay, Mostafa Dehghani, Vamsi Aribandi, Jai Gupta, Philip Pham, Zhen Qin, Dara Bahri, Da-Cheng Juan, and Donald Metzler.  Omninet: Omnidirectional representations from transformers.  2021\.
  * [25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6000–6010, 2017.
  * [26] Junho Yim, Donggyu Joo, Jihoon Bae, and Junmo Kim.  A gift from knowledge distillation: Fast optimization, network minimization and transfer learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4133–4141, 2017.
  * [27] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How transferable are features in deep neural networks?  In Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 2, pages 3320–3328, 2014.
  * [28] Sergey Zagoruyko and Nikos Komodakis.  Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer.  arXiv preprint arXiv:1612.03928, 2016.
  * [29] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
  * [30] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In European conference on computer vision, pages 818–833. Springer, 2014.
  * [31] Linfeng Zhang, Jiebo Song, Anni Gao, Jingwei Chen, Chenglong Bao, and Kaisheng Ma.  Be your own teacher: Improve the performance of convolutional neural networks via self distillation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3713–3722, 2019.
  * [32] Ying Zhang, Tao Xiang, Timothy M. Hospedales, and Huchuan Lu.  Deep Mutual Learning.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4320–4328, Salt Lake City, UT, June 2018. IEEE.


* [17] Rajba T.: On a generalization of a theorem of Levin and Stečkin and inequalities of the Hermite–Hadamard type. Math. Inequal. Appl., 20(2), 363–375 (2017).
  * [18] Raşa, I.: 2. Problem, p. 164. In: Report of Meeting Conference on Ulam’s Type Stability, Rytro, Poland, June 2–6, 2014, Ann. Univ. Paedagog. Crac. Stud. Math. 13, 139–169 (2014). DOI: 10.2478/aupcsm-2014-0011.
  * [19] Shaked M., Shanthikumar J.G.: Stochastic Orders. Springer. (2007).