# Minimum trace norm of real symmetric and Hermitian matrices with zero
diagonal

Mostafa Einollahzadeh

###### Abstract

In this paper, we obtain tight lower bounds for the trace norm $\|\cdot\|_{1}$
of some matrices with diagonal zero, in terms of the entry-wise $l_{1}$-norm
(denoted by $\|\cdot\|_{(1)}$). It is shown that on the space of nonzero real
symmetric matrices $A$ of order $n$ with diagonal zero, the miniumum value of
the quantity $\frac{\|A\|_{1}}{\|A\|_{(1)}}$ is equal to $\frac{2}{n}$. The
answer for the similar problem in the space of Hermitian matrices, is also
obtained to be equal to $\tan(\frac{\pi}{2n})$. As equivalent form of these
results, it is shown that, for every real symmetric matrix $A$ of order $n$
with off-diagonal entries of absolute values at most $1$, always there exists
some diagonal matrix $D$ which is at distance $\leq\frac{n}{2}$ of $A$ in the
spectral norm. The similar problem for the case of Hermitian matrices, has
answer $\cot(\frac{\pi}{2n})$.

AMS Classification:  15A42, 05C50

Keywords:  Trace norm, Matrix norm inequality, Graph energy, Nearest diagonal
matrix

##  1 Introduction

The trace norm of a matrix (denoted by $\|\cdot\|_{1}$) is defined to be the
sum of its singular values, and the spectral norm (denoted by
$\|\cdot\|_{\infty}$)is defined to be the maximum singular value. Specially in
the case of Hermitian matrices or real symmetric matrices, which we consider
in this paper, the singular values are equal to absolute values of the
eigenvalues, which can be used in the definition of above norms. The trace
norm is also known by “energy” in some references, mostly those related to
algebraic graph theory or its applications in chemistry (cf. [GF17] for a
survey).

The main idea of this paper comes from a conjecture by Haemers in [Hae12]
(proved in[AEKN20]), on “the minimum energy of Seidel matrix of simple
graphs”, which can be restated in our terminology as follows:

######  Conjecture.

Let $A$ be an arbitrary symmetric matrix of order $n$, with diagonal entries
equal to zero and off-diagonal entries in $\\{\pm 1\\}$. Then the minimum
value of $\|A\|_{1}$ is equal to $\|J_{n}-I_{n}\|_{1}=2n-2$, for the all ones
matrix $J_{n}$ and the identity matrix $I_{n}$, both of order $n$.

Numerical computations for small values of $n$, suggest that the matrix
$J_{n}-I_{n}$ has the minimum trace norm in the set of all diagonal zero
matrices of order $n$, for which the sum of absolute values of the entries is
equal to $n(n-1)$. So in fact, the above conjecture on the discrete set of
matrices with $\\{\pm 1\\}$ off-diagonal entries, can be generalized to give a
lower bound for the trace norm of every diagonal zero matrix with a prescribed
value for the $l_{1}$-norm of its entries. This is one of the main results of
this paper:

######  Theorem 1.

Let $A=[a_{ij}]$ be a real symmetric matrix of order $n$ with zero entries on
the main diagonal. Then

$\|A\|_{1}\geq\frac{2}{n}\sum_{i,j}|a_{ij}|,$

and the bound is sharp for all $n$.

The similar problem can be imposed for other spaces of matrices. We also
obtained the best result for the space of Hermitian matrices:

######  Theorem 2.

Let $A=[a_{ij}]$ be a Hermitian matrix of order $n$ with zero entries on the
main diagonal. Then

$\|A\|_{1}\geq\tan(\frac{\pi}{2n})\sum_{i,j}|a_{ij}|,$

and the bound is sharp for all $n$.

By considering the standard Frobenius inner product on the space of real
symmetric or Hermitian matrices, we obtained equivalent “dual” results of
above theorems. The dual results are related to the minimum distance in the
spectral norm of a matrix to the space of diagonal matrices.

We denote space of all real diagonal matrices of order $n$, by
$\mathcal{D}_{n}$. Then the first “dual” theorem in case of real symmetric
matrices, can be stated as follows:

######  Theorem 3.

Let $A=[a_{ij}]$ be a real symmetric matrix of order $n>1$. Then

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}\;\leq\;\frac{n}{2}\max_{i\neq
j}|a_{ij}|,$

and the bound is sharp for all $n>1$.

The equality case in above theorem, is obtained by the matrix $A=J_{n}$,
because $\|J_{n}-\frac{n}{2}I_{n}\|_{\infty}=\frac{n}{2}$ and
$\frac{n}{2}I_{n}$ is the nearest diagonal matrix to $J_{n}$ in the spectral
norm. It’s interesting that the worst case in this respect, is the simplest
matrix $J_{n}$.

It’s worse noting that, we have no effective method for finding a diagonal
matrix at spectral distance $\frac{n}{2}$ from a given matrix with entries in
$[-1,1]$, as we know its existence by above theorem. This would be an
interesting problem in its own right.

The last theorem in this paper, is the Hermitian version of Theorem 3.

######  Theorem 4.

Let $A=[a_{ij}]$ be a Hermitian matrix of order $n>1$. Then

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}\;\leq\;\cot(\frac{\pi}{2n})\max_{i\neq
j}|a_{ij}|,$

and the bound is sharp for all $n>1$.

The paper is organized as follows: Section 1 is devoted to the basic
definitions and known results, which are used throughout. In sections 2 and 3,
we have presented the proofs and necessary lemmas of the Theorems 1 and 2,
respectively. The section 4, is also devoted to the dual versions, Theorem 3
and 4.

##  2 Notation and preliminaries

In the first part of this section we review some of very basic concepts and
results from the theory of matrix analysis for the reader’s convenience and
fixing notations. The detailed discussion and proofs can be found in any
standard textbook on this subject, such as [Bha13], [HJ12] and [Zha13].

We denote the conjugate transpose of a general complex matrix $A$ by $A^{*}$.
For two complex vectors $\mathbf{u}$ and $\mathbf{v}$ of the same dimension,
their usual Euclidean inner product is denoted by $\langle
u,v\rangle:=\mathbf{u}^{*}\mathbf{v}$ and the corresponding norm by
$|\mathbf{u}|:=\sqrt{\langle\mathbf{u},\mathbf{u}\rangle}$.

The space of real and complex $m\times n$ matrices, is denoted by $M_{m\times
n}(\mathbb{R})$ and $M_{m\times n}(\mathbb{C})$, respectively. The space of
real symmetric matrices of order $n$, is denoted by $\mathcal{S}_{n}$ and the
space of Hermitian matrices of order $n$, is denoted by $\mathcal{H}_{n}$. The
space of real diagonal matrices of order $n$, is also denoted by
$\mathcal{D}_{n}$.

Let $A\in\mathcal{H}_{n}$ has eigenvalues $\lambda_{1},\dots,\lambda_{n}$, the
trace norm (energy, nuclear norm, …) of $A$ is defined by
$\|A\|_{1}=\sum_{i=1}^{n}|\lambda_{i}|$ and the spectral norm of $A$ is
defined by $\|A\|_{\infty}=\max_{i}|\lambda_{i}|$. 111These are two special
cases of the Schatten $p$-norms defined by the $l_{p}$-norm of the singular
values of a general matrix, which is the reason for choosing the present
notation. Two other entry-wise $l_{1}$-norm and max norm of $A$, are also
defined by formulas
$\|A\|_{(1)}=\sum_{i,j}|A_{ij}|,\|A\|_{(\infty)}=\max_{i,j}|A_{ij}|$. We also
denote the vector $(A_{11},A_{22},\dots,A_{nn})$ of diagonal entries of $A$ by
$\mathrm{diag}(A)$.

Now let

$A=\lambda_{1}\mathbf{x}_{1}\mathbf{x}^{*}_{1}+\dots+\lambda_{n}\mathbf{x}_{1}\mathbf{x}^{*}_{n},$

be the spectral decomposition of $A$ for an orthonormal basis
$\mathbf{x}_{1},\dots,\mathbf{x}_{n}$ of eigenvectors and corresponding
eigenvalues $\lambda_{1},\dots,\lambda_{n}$. Suppose for some $k$,

$\lambda_{1},\dots,\lambda_{k}\geq 0,\quad\lambda_{k+1},\dots,\lambda_{n}<0.$

The positive part and the negative part of $A$, are defined by:

$A^{+}:=\sum_{i\leq k}\lambda_{i}\mathbf{x}_{i}\mathbf{x}^{*}_{i},\quad
A^{-}:=-\left(\sum_{i>k}\lambda_{i}\mathbf{x}_{i}\mathbf{x}^{*}_{i}\right).$

It can be easily seen that $A^{+},A^{-}$ are well-defined positive semi-
definite matrices and $A=A^{+}-A^{-}$.

We also use the Frobenius inner product on the spaces $M_{m\times
n}(\mathbb{C})$. For two matrices $A,B\in M_{m\times n}(\mathbb{C})$, their
(Frobenius) inner product is defined by:

$\langle A,B\rangle:=\mathrm{tr}(A^{*}B)=\sum_{i,j}\overline{A_{ij}}B_{ij}.$

It can be simply checked that, this gives a real inner product on
$\mathcal{H}_{n}$.

We need two basic properties of the Frobenius inner product:

  * •

For every unitary matrix $U$ and square matrices $A$ and $B$, all of the same
order,

$\langle A,B\rangle=\langle U^{*}AU,U^{*}BU\rangle.$

  * •

The inner product of two positive semi-definite matrices of the same order, is
nonnegative.

######  Lemma 1.

Let $A$ and $B$, be two positive semi-definite matrices of order $n$. Then the
matrix $C$ defined by,

$C_{ij}=\overline{A_{ij}}B_{ij},$

is also positive semi-definite.

###### Proof.

Let $\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{C}^{n}$ be an arbitrary vector.
Define $X$ to be the diagonal matrix with diagonal entries $x_{1},\dots,x_{n}$
in the same order. Then we have

$\displaystyle\mathbf{x}^{*}C\mathbf{x}$
$\displaystyle=\sum_{i,j}\overline{x_{i}}\overline{A_{ij}}x_{j}B_{ij}=\sum_{i,j}\overline{(XAX^{*})_{ij}}B_{ij}=\left\langle
X^{*}AX,B\right\rangle.$

Now since $X^{*}AX$ and $B$ are both positive semi-definite, $\left\langle
X^{*}AX,B\right\rangle\geq 0$ and so $\mathbf{x}^{T}C\mathbf{x}\geq 0$.

∎

In the second part of this section, we review the “duality transformation” on
convex sets. For more information on this subject, the reader can consult
[Mat13] (for the duality transformation in general ) and [Zha13] (for dual
norms).

Let $(V,\langle\cdot,\cdot\rangle)$ be a real inner product space of finite
dimension. For every subset $X$ of $V$, we define the dual (or polar) of $X$
by,

$X^{*}=\\{y\in V:\langle y,x\rangle\leq 1,\forall x\in X\\}.$

We denote the convex hull and closure of a set $X$, by $\mathrm{conv}(X)$ and
$\mathrm{cl}(X)$, respectively. In the next lemma, we list some of basic
properties of the duality transform that we need in this paper.

######  Lemma 2.

Let $V$ be a finite dimensional real inner product space, and $X,Y$ be subsets
of $V$.

  1. 1.

$X^{*}$ is a closed convex set and contains $0$.

  2. 2.

If $X\subset Y$, then $Y^{*}\subset X^{*}$.

  3. 3.

$X^{*}=\mathrm{conv}(X)^{*}=\mathrm{cl}(X)^{*}$.

  4. 4.

$(X\cup Y)^{*}$= $X^{*}\cap Y^{*}$.

  5. 5.

Let $W$ be a linear subspace of $V$. Then $W^{*}=W^{\perp}$, for the
orthogonal complement $W^{\perp}$ of $W$.

  6. 6.

If $X$ is closed convex and contains $0$, then $(X^{*})^{*}=X$.

  7. 7.

If $X$ and $Y$ are closed convex and contain $0$, and
$Z=\mathrm{cl}(\mathrm{conv}(X^{*}\cup Y^{*}))$, then

$(X\cap Y)^{*}=Z.$

###### Proof.

The statements 1-5, are immediate consequences of the definition, and 6 is
standard (cf. [Mat13], section 5.1).

For 7, first by assumption we have $X=(X^{*})^{*}$ and $Y=(Y^{*})^{*}$ and by
double use of 3, we have,

$Z^{*}=(X^{*}\cup Y^{*})^{*}=(X^{*})^{*}\cap(Y^{*})^{*}=X\cap Y.$

Now $Z$ is closed convex and contains $0$ and so is equal to its second dual,
which gives,

$(X\cap Y)^{*}=(Z^{*})^{*}=Z.$

∎

For every norm $\|\cdot\|$ on $V$, its dual norm $\|\cdot\|^{\prime}$ is
defined by

$\|v\|^{\prime}=\max\\{\langle v,w\rangle,\|w\|\leq 1\\}.$

Equivalently, the unit ball of $\|\cdot\|$ and $\|\cdot\|^{\prime}$ are dual
to each other.

In the spaces $\mathcal{H}_{n}$ and $\mathcal{S}_{n}$ with Frobenius inner
product (which is the only inner product we consider in this paper), the dual
norms of $\|\cdot\|_{1}$ and $\|\cdot\|_{(1)}$, are $\|\cdot\|_{\infty}$ and
$\|\cdot\|_{(\infty)}$ respectively (cf. [Zha13], section 4.3).

##  3 Real symmetric matrices

In this section we proof Theorem 1 using two lemmas.

######  Lemma 3.

Let $d>0$ and $a,b\in\mathbb{R}$ with $|a|,|b|\leq d$. Then

$|a-b|\leq\left(d-\frac{ab}{d}\right).$

###### Proof.

We have

$\left(d-\frac{ab}{d}\right)-(a-b)=\frac{1}{d}(d+b)(d-a)\geq 0,$

so $(d-\frac{ab}{d})\geq(a-b)$, and similarly $(d-\frac{ab}{d})\geq(b-a)$. ∎

######  Proposition 1.

Let $A,B$ be two real positive semi-definite matrices of order $n$, with

$\mathrm{diag}(A)=\mathrm{diag}(B)=(d_{1},\dots,d_{n}).$

Then

$\sum_{i,j}|A_{ij}-B_{ij}|\leq\left(\sum_{i=1}^{n}\sqrt{d_{i}}\right)^{2}.$

###### Proof.

$A$ and $B$ are positive semi-definite, so all of their $2\times 2$ principal
minors are nonnegative, i.e. for all $i,j$ we have

$d_{i}d_{j}-(A_{ij})^{2}=A_{ii}A_{jj}-(A_{ij})^{2}\geq 0\Longrightarrow\
|A_{ij}|\leq\sqrt{d_{i}d_{j}}.$

similarly $|B_{ij}|\leq\sqrt{d_{i}d_{j}}$.

Define the vector $\mathbf{e}=(e_{1},\dots,e_{n})$ and the symmetric matrix
$C$ by the equations

$e_{i}=\left\\{\begin{array}[]{ll}\frac{1}{\sqrt{d_{i}}}&d_{i}>0\\\
0&d_{i}=0\end{array}\right.,\quad C_{ij}=A_{ij}B_{ij}.$

For every $i\neq j$, if $d_{i}d_{j}=0$, $A_{ij}=B_{ij}=C_{ij}=0,$ and if
$d_{i}d_{j}>0$, $|A_{ij}|,|B_{ij}|\leq\sqrt{d_{i}d_{j}}$. So by Lemma 3, for
all $i,j$,

$|A_{ij}-B_{ij}|\leq\left(\sqrt{d_{i}d_{j}}-e_{i}e_{j}C_{ij}\right).$ (1)

.

Summing up the above inequalities, we obtain

$\displaystyle\sum_{i,j}|A_{ij}-B_{ij}|$
$\displaystyle\leq\left(\sum_{i}\sqrt{d_{i}}\right)^{2}-\sum_{i,j}e_{i}e_{j}C_{ij}$
$\displaystyle=\left(\sum_{i}\sqrt{d_{i}}\right)^{2}-\mathbf{e}^{T}C\mathbf{e}.$
(2)

By Lemma 1, $C$ is also positive semi-definite, hence

$\mathbf{e}^{T}C\mathbf{e}\geq 0,$ (3)

and this completes the proof. ∎

###### Proof of Theorem 1.

We have $A=A^{+}-A^{-}$ and $\mathrm{diag}(A)=0$, so for a vector
$(d_{1},\dots,d_{n})\in\mathbb{R}^{n}$,

$\mathrm{diag}(A^{+})=\mathrm{diag}(A^{-})=(d_{1},\dots,d_{n}).$

Let $\lambda_{1},\dots,\lambda_{k}\geq 0$ be all of the nonnegative
eigenvalues, and $\lambda_{k+1},\dots,\lambda_{n}$ all of the negative
eigenvalues of $A$. Therefore

$\|A\|_{1}=\sum_{i\leq
k}\lambda_{i}-\sum_{i>k}\lambda_{i}=\mathrm{tr}(A^{+})+\mathrm{tr}(A^{-})=2\sum_{i}d_{i}.$
(4)

Now by Proposition 1,

$\sum_{i,j}|A_{ij}|=\sum_{i,j}|A^{+}_{ij}-A^{-}_{ij}|\leq\left(\sum_{i}\sqrt{d_{i}}\right)^{2}\leq
n\sum_{i}d_{i}=\frac{n}{2}\|A\|_{1}.$ (5)

For an equality case, consider the matrix $A=J_{n}-I_{n}$, for the all one
matrix $J_{n}$ and the identity matrix $I_{n}$, both of order $n>1$. The
eigenvalues of $A$ are $n-1$ and $-1$ with multiplicity $n-1$. Hence
$\frac{\|A\|_{1}}{\|A\|_{(1)}}=\frac{2(n-1)}{n(n-1)}=\frac{2}{n}$. ∎

######  Remark 1.

For more general example of matrices $A$, which give equality in Theorem 1,
consider the matrix,

$A=\mathbbm{1}\mathbbm{1}^{*}-B,$

for $\mathbbm{1}=(1,1,\dots,1)\in\mathbb{R}^{n}$ and arbitrary positive semi-
definite matrix $B\in\mathcal{S}_{n}$, with condition

$B\mathbbm{1}=0,\quad\mathrm{diag}(B)=(1,1,\dots,1).$

Then $\langle\mathbbm{1}\mathbbm{1}^{*},B\rangle=0$, and
$A^{+}=\mathbbm{1}\mathbbm{1}^{*},A^{-}=B$. So we have,
$\mathrm{diag}(A)=0,\|A\|_{1}=2\mathrm{tr}(A^{+})=2n$ and because
$|B_{ij}|\leq 1$ for all $i,j$ (by $B\geq 0$),

$\|A\|_{(1)}=\sum_{i,j}|1-B_{ij}|=n^{2}-\sum_{i,j}B_{ij}=n^{2}.$

Therefore $\frac{\|A\|_{1}}{\|A\|_{(1)}}=\frac{2}{n}$.

Also it can be easily seen that, for every $d\in\mathbb{R}$ and every diagonal
matrix $D$ with diagonal entries in $\\{\pm 1\\}$, the matrix $dDAD$ is also
an example of equality in Theorem 1. It seems that, these are all of the
equality cases, although we don’t have a proof.

##  4 Hermitian matrices

In the previous section, we saw that the minimum of
$\frac{\|A\|_{1}}{\|A\|_{(1)}}$ over all nonzero real symmetric matrices $A$
of order $n$ with zero entries on the diagonal, is equal to $\frac{2}{n}$. In
this section we will give a proof of Theorem 2, which gives the answer of the
similar problem for Hermitian matrices. It turns out that for a constant
$\gamma_{n}$ which defined bellow, the answer is equal to
$\frac{1}{\gamma_{n}}\cdot\frac{2}{n}$.

We define:

$\gamma_{n}:=\frac{2}{n}\sum_{k=0}^{n-1}\sin(\frac{k\pi}{n}).$ (6)

For $n\geq 2$, there is a simpler formula for $\gamma_{n}$:

$\displaystyle\gamma_{n}$
$\displaystyle=\frac{2}{n}\,\mathrm{Im}\left(\sum_{k=0}^{n-1}\exp(\mathrm{i}\frac{k\pi}{n})\right)=\frac{2}{n}\,\mathrm{Im}\left(\frac{1-\exp(\mathrm{i}\pi)}{1-\exp(\frac{\mathrm{i}\pi}{n})}\right)$
$\displaystyle=\frac{4}{n}\cdot\frac{\sin(\frac{\pi}{n})}{2-2\cos(\frac{\pi}{n})}=\frac{2}{n}\cdot\frac{2\sin(\frac{\pi}{2n})\cos(\frac{\pi}{2n})}{2\sin^{2}(\frac{\pi}{2n})}$
$\displaystyle=\frac{2}{n\tan(\frac{\pi}{2n})}.$ (7)

and because $\frac{\tan(x)}{x}$ is increasing in the interval
$[0,\frac{\pi}{2})$ and $\lim_{x\to 0}\frac{\tan(x)}{x}=1$,

$\gamma_{1}=0\leq\gamma_{2}=1\leq\gamma_{3}\leq\dots,\quad\lim_{n\to\infty}\gamma_{n}=\frac{4}{\pi}.$
(8)

######  Lemma 4.

Let $d>0$ and $a,b\in\mathbb{C}$ with $|a|,|b|\leq d$. Then

$|a-b|\leq\left|d-\frac{\overline{a}b}{d}\right|.$

###### Proof.

We have

$\displaystyle\left|d-\frac{\overline{a}b}{d}\right|^{2}-|a-b|^{2}$
$\displaystyle=\left(d^{2}+\frac{|a|^{2}|b|^{2}}{d^{2}}-\overline{a}b-a\overline{b}\right)-\left(|a|^{2}+|b|^{2}-\overline{a}b-a\overline{b}\right)$
$\displaystyle=\frac{1}{d^{2}}(d^{2}-|a|^{2})(d^{2}-|b|^{2})\geq 0.$

Hence $|a-b|^{2}\leq\left|d-\frac{\overline{a}b}{d}\right|^{2}$, as required.
∎

Hereafter we use the notation $\mathbb{S}^{1}=\\{z\in\mathbb{C}:|z|=1\\}$.

######  Lemma 5.

Let $d_{1},\dots,d_{n}\geq 0$ and
$\omega_{1},\dots,\omega_{n}\in\mathbb{S}^{1}$. Then

$\sum_{i,j}d_{i}d_{j}|\omega_{i}-\omega_{j}|\,\leq\,\gamma_{n}\left(\sum_{i}d_{i}\right)^{2},$

and equality holds if $\\{\omega_{1},\dots,\omega_{n}\\}$ is the set of $n$-th
roots of unity and $d_{1}=d_{2}=\dots=d_{n}$.

Since the proof is rather long, we postpone it until section 6.

######  Corollary 1.

For every vector $\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{C}^{n}$,

$\sum_{i,j}\left||x_{i}x_{j}|-x_{i}\overline{x_{j}}\right|\leq\gamma_{n}\left(\sum_{i}|x_{i}|\right)^{2}.$

###### Proof.

Apply the previous lemma to $d_{i}=|x_{i}|$ and $x_{i}=d_{i}\omega_{i}$ for
$\omega_{i}\in\mathbb{S}^{1}$. Then we have

$\displaystyle\sum_{i,j}\left||x_{i}x_{j}|-x_{i}\overline{x_{j}}\right|$
$\displaystyle=\sum_{i,j}\left|d_{i}d_{j}-d_{i}d_{j}\omega_{i}\overline{\omega_{j}}\right|$
$\displaystyle=\sum_{i,j}d_{i}d_{j}\left|\omega_{i}-\omega_{j}\right|$
$\displaystyle\leq\gamma_{n}\left(\sum_{i}d_{i}\right)^{2}=\gamma_{n}\left(\sum_{i}|x_{i}|\right)^{2}.$

∎

######  Proposition 2.

Let $A,B$ be two Hermitian semi-definite matrices of order $n$, with

$\mathrm{diag}(A)=\mathrm{diag}(B)=(d_{1},\dots,d_{n}).$

Then

$\sum_{i,j}|A_{ij}-B_{ij}|\leq\gamma_{n}\left(\sum_{i=1}^{n}\sqrt{d_{i}}\right)^{2}.$

###### Proof.

Define the vector $\mathbf{e}\in\mathbb{C}^{n}$ and the Hermitian matrix $C$
by the equations,

$e_{i}=\left\\{\begin{array}[]{ll}\frac{1}{\sqrt{d_{i}}}&d_{i}>0\\\
0&d_{i}=0\end{array}\right.,\quad C_{ij}=e_{i}e_{j}\overline{A_{ij}}B_{ij}.$

Then $\mathrm{diag}(C)=(d_{1},\dots,d_{n})$ and by semi-positivity of $A$ and
$B$, for all $i,j$,

$|A_{ij}|,|B_{ij}|\leq\sqrt{d_{i}d_{j}},$

and if $d_{i}d_{j}=0$, $A_{ij}=B_{ij}=C_{ij}=0$. Hence by Lemma 4,

$\sum_{i,j}|A_{ij}-B_{ij}|\leq\sum_{i,j}|\sqrt{d_{i}d_{j}}-C_{ij}|.$ (9)

Let $X$ be the diagonal matrix with $e_{1},\dots,e_{n}$ on its diagonal. Then

$C=X^{*}\,[\overline{A_{ij}}B_{ij}]_{i,j}\,X,$

and by Lemma 1, $[\overline{A_{ij}}B_{ij}]_{i,j}$ and also $C$ are positive
semi-definite. Hence for some vectors
$\mathbf{x}_{1},\dots,\mathbf{x}_{k}\in\mathbb{C}^{n}$, we can write,

$C=\mathbf{x}_{1}\mathbf{x}_{1}^{*}+\cdots+\mathbf{x}_{k}\mathbf{x}_{k}^{*}.$

For every $i\leq k$, define $\mathbf{y}_{i}\in\mathbb{R}_{\geq 0}^{n}$ by,

$(\mathbf{y}_{i})_{j}=|(\mathbf{x}_{i})_{j}|,\quad 1\leq j\leq n.$

Now if we define

$D=\mathbf{y}_{1}\mathbf{y}_{1}^{*}+\cdots+\mathbf{y}_{k}\mathbf{y}_{k}^{*},$

we have $\mathrm{diag}(D)=\mathrm{diag}(C)=(d_{1},\dots,d_{n})$ and $D$ is
also positive semi-definite. So for all $i,j$,
$|D_{ij}|\leq\sqrt{d_{i}d_{j}}$, and by triangle inequality

$\sum_{i,j}|\sqrt{d_{i}d_{j}}-C_{ij}|\leq\sum_{i,j}\left(\sqrt{d_{i}d_{j}}-D_{ij}+|D_{ij}-C_{ij}|\right).$
(10)

By the definition of $C$ and $D$ and applying Corollary 1 to vectors
$\mathbf{x}_{1},\dots,\mathbf{x}_{k}$, we also have

$\displaystyle\sum_{i,j}|D_{ij}-C_{ij}|$
$\displaystyle\leq\sum_{s=1}^{k}\sum_{i,j}|(\mathbf{y}_{s})_{i}(\mathbf{y}_{s})_{j}-(\mathbf{x}_{s})_{i}\overline{(\mathbf{x}_{s})_{j}}|$
$\displaystyle=\sum_{s=1}^{k}\sum_{i,j}||(\mathbf{x}_{s})_{i}(\mathbf{x}_{s})_{j}|-(\mathbf{x}_{s})_{i}\overline{(\mathbf{x}_{s})_{j}}|$
$\displaystyle\leq\gamma_{n}\sum_{s=1}^{k}\left(\sum_{i}(\mathbf{y}_{s})_{i}\right)^{2}$
$\displaystyle=\gamma_{n}\sum_{i,j}D_{ij}.$ (11)

Finally combining inequalities (9), (10) and (4), and the fact that
$\gamma_{n}\geq 1$ for $n\geq 2$, we have

$\displaystyle\sum_{i,j}|A_{ij}-B_{ij}|$
$\displaystyle\leq\sum_{i,j}(\sqrt{d_{i}d_{j}}-D_{ij})+\gamma_{n}\sum_{i,j}D_{ij}$
$\displaystyle\leq\gamma_{n}\sum_{i,j}(\sqrt{d_{i}d_{j}}-D_{ij})+\gamma_{n}\sum_{i,j}D_{ij}$
$\displaystyle=\gamma_{n}\left(\sum_{i}\sqrt{d_{i}}\right)^{2}.$

∎

###### Proof of Theorem 2.

The proof is completely similar to the proof of Theorem 1. If
$\mathrm{diag}(A^{+})=(d_{1},\dots,d_{n})$, we have

$\|A\|_{1}=\mathrm{tr}(A^{+})+\mathrm{tr}(A^{-})=2\sum_{i}d_{i},$ (12)

and by applying Proposition 2 to $A^{+}$ and $A^{-}$,

$\displaystyle\sum_{i,j}|A_{ij}|$
$\displaystyle=\sum_{i,j}|A^{+}_{ij}-A^{-}_{ij}|\,\leq\gamma_{n}\left(\sum_{i=1}^{n}\sqrt{d_{i}}\right)^{2}$
$\displaystyle\leq
n\gamma_{n}\sum_{i}d_{i}\,=\frac{n\gamma_{n}}{2}\|A\|_{1}\,=\cot(\frac{\pi}{2n})\|A\|_{1}.$
(13)

For an equality case, let $A$ given by
$\mathbbm{1}\mathbbm{1}^{*}-\boldsymbol{\alpha}\boldsymbol{\alpha}^{*}$ for
the same notations defined in (26). It can be easily checked that $A$ is a
Hermitian matrix with diagonal zero, and because

$\
\langle\mathbbm{1},\boldsymbol{\alpha}\rangle=0,\quad|\mathbbm{1}|^{2}=|\boldsymbol{\alpha}|^{2}=n,$

it has two nonzero eigenvalues $n,-n$, and $\|A\|_{1}=2n$. On the other hand,
the equality statement of Lemma 5, gives,

$\displaystyle\sum_{i,j}|A_{ij}|=\sum_{i,j}|1-\alpha_{i}\overline{\alpha_{j}}|=\sum_{i,j}|\alpha_{i}-{\alpha_{j}}|=n^{2}\gamma_{n}.$

Hence
$\frac{\|A\|_{1}}{\|A\|_{(1)}}=\frac{2n}{n^{2}\gamma_{n}}=\tan(\frac{\pi}{2n})$,
which gives our desired equality case for (4).

∎

######  Remark 2.

By the relations in (8), the sequence
$\gamma_{n}=\frac{2}{n\tan(\frac{\pi}{2n})}$ converges from below to
$\frac{4}{\pi}$. So by Theorem 2, for every nonzero Hermitian matrix $A$ of
order $n$ with zero diagonal, we have
$\|A\|_{1}\geq\frac{2}{n\gamma_{n}}\|A\|_{(1)}$ and so

$\|A\|_{1}>\;\frac{\pi}{2}\cdot\frac{1}{n}\|A\|_{(1)},$ (14)

and $\frac{\pi}{2}$ is the best constant (independent of $n$) for which the
above inequality holds for all $n$.

##  5 The dual version

In this section we prove Theorems 3 and 4. The main idea is to view the
inequality statements in Theorems 1 and 2, as statements about the inclusion
of certain convex sets. Then apply the duality transformation on this sets to
obtain reverse inclusion relations between the resulting dual sets, and
finally interpret these inclusions as a matrix norm inequality.

For every subscript $*$, we denote the closed unit ball of the norm
$\|\cdot\|_{*}$, by $\mathcal{B}_{*}$. Here $\|\cdot\|_{*}$ can be any of the
norms $\|\cdot\|_{1},\|\cdot\|_{\infty},\|\cdot\|_{(1)},\|\cdot\|_{(\infty)}$
on the underlying spaces $\mathcal{S}_{n}$ or $\mathcal{H}_{n}$, and the
underlying space is known from the context. All of these balls are bounded
closed sets, and are consequently compact.

######  Lemma 6.

Let $V$ be a finite dimensional real inner product space and $X$ be a compact
convex subset of $V$ which contains $0$. Then for every linear subspace $L$ of
$V$,

$\mathrm{cl}(\mathrm{conv}(X\cup L))=X+L.$

###### Proof.

By the compactness of $X$, it can be easily seen that $X+L$ is closed. It is
also convex, and so it contains $\mathrm{cl}(\mathrm{conv}(X\cup L))$. Next we
show that every point of $X+L$ is a limit point of $\mathrm{conv}(X\cup L)$,
which completes the proof.

Let $x+v$ (for $x\in X$ and $v\in L$) be an arbitrary point in $X+L$. Then we
have

$x+v=\lim_{t\to 1^{-}}tx+(1-t)\left(\frac{v}{1-t}\right).$

Clearly $tx+(1-t)\left(\frac{v}{1-t}\right)\in\mathrm{conv}(X\cup L)$ for
$0\leq t<1$, and so $x+v$ is a limit point of $\mathrm{conv}(X\cup L)$. ∎

###### Proof of Theorem 3.

First note that the orthogonal complement of $\mathcal{D}_{n}$ is equal to the
set of matrices with diagonal zero. Now let $A$ be an arbitrary real symmetric
matrix in $\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}$. Then $\|A\|_{1}\leq 1$
and $A$ has zero entries on the diagonal. So by Theorem 1,
$\|A\|_{(1)}\leq\frac{n}{2}$, or equivalently,
$A\in\frac{n}{2}\mathcal{B}_{(1)}$. Therefore the inequality statement of
Theorem 1 implies the inclusion,

$\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\subset\frac{n}{2}\mathcal{B}_{(1)}.$
(15)

By taking dual of both sides, we obtain

$\frac{2}{n}\mathcal{B}_{(1)}^{*}\subset\left(\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\right)^{*}.$
(16)

Now note that the norms $\|\cdot\|_{1}$ and $\|\cdot\|_{\infty}$, are dual to
each other, and so by definition,

$\mathcal{B}_{1}^{*}=\mathcal{B}_{\infty}.$

Similarly for the dual norms $\|\cdot\|_{(1)}$ and $\|\cdot\|_{(\infty)}$, we
have

$\mathcal{B}_{(1)}^{*}=\mathcal{B}_{(\infty)}.$

The ball $\mathcal{B}_{1}$ is closed convex and contains zero, so by Lemma 2,

$\left(\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\right)^{*}=\mathrm{cl}(\mathrm{conv}(\mathcal{B}_{1}^{*}\cup(\mathcal{D}_{n}^{\perp})^{*}))=\mathrm{cl}(\mathrm{conv}(\mathcal{B}_{\infty}\cup\mathcal{D}_{n})).$

Using the previous lemma for $X=\mathcal{B}_{\infty}$ and $L=\mathcal{D}_{n}$,
we have

$\mathrm{cl}(\mathrm{conv}(\mathcal{B}_{\infty}\cup\mathcal{D}_{n}))=\mathcal{B}_{\infty}+\mathcal{D}_{n}.$

Substituting the above relations in the inclusion (16),and multiplication of
the both sides by $\frac{n}{2}$ gives,

$\mathcal{B}_{(\infty)}\;\subset\;\frac{n}{2}\mathcal{B}_{\infty}+\mathcal{D}_{n}.$
(17)

This inclusion can also be easily converted to an equivalent matrix norm
inequality. Let $A=[a_{ij}]\in\mathcal{S}_{n}-\mathcal{D}_{n}$, and
$M=\max_{i\neq j}|a_{ij}|$. Define the matrix $B$ as below,

$B_{ij}=\left\\{\begin{array}[]{ll}0&i=j\\\ \frac{a_{ij}}{M}&i\neq
j.\end{array}\right.$

Then for every $i\neq j$, $|B_{ij}|\leq 1$, and so
$B\in\mathcal{B}_{(\infty)}$. Also $A=MB+D_{1}$, for a diagonal matrix
$D_{1}$. Now by (17), $B=C+D_{2}$ for some $C\in\mathcal{S}_{n}$ with
$\|C\|_{\infty}\leq\frac{n}{2}$ and a diagonal matrix $D_{2}$. Therefore,

$\|A-(D_{1}+MD_{2})\|_{\infty}=\|MC\|_{\infty}\leq\frac{n}{2}\max_{i\neq
j}|a_{ij}|,$

and hence,

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}\leq\frac{n}{2}\max_{i\neq
j}|a_{ij}|.$ (18)

In the case of diagonal matrices $A$, the above inequality is trivial, and so
it is valid for every $A\in\mathcal{S}_{n}$.

For the sharpness of the inequality, note that all of above arguments are
reversible for any constant in the place of $\frac{n}{2}$. Therefore if the
inequality (18) remains valid for some other constant smaller than
$\frac{n}{2}$, this is also the case for Theorem 1, which we know is
impossible. ∎

######  Remark 3.

By the equality

$\left(\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\right)^{*}=\mathcal{B}_{\infty}+\mathcal{D}_{n},$

in above proof, for every matrix $A=[a_{ij}]\in\mathcal{S}_{n}$,

$\displaystyle\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}$
$\displaystyle=\min\\{r\geq 0:A\in r\mathcal{B}_{\infty}+\mathcal{D}_{n}\\}$
$\displaystyle=\min\\{r\geq 0:A\in
r\left(\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\right)^{*}\\}$
$\displaystyle=\max_{B\in\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}}\langle
A,B\rangle.$

Therefore if $A^{\prime}$ be the matrix obtained from $A$ by just changing the
diagonal entries to zero, we have

$\displaystyle\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}$
$\displaystyle=\max_{B\in\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}}\langle
A,B\rangle$
$\displaystyle\leq\max_{B\in\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}}\|A^{\prime}\|_{(\infty)}\|B\|_{(1)}$
(19)
$\displaystyle\leq\frac{n}{2}\|A^{\prime}\|_{(\infty)}=\frac{n}{2}\max_{i\neq
j}|a_{ij}|.$ (20)

(The second inequality is by Theorem 1, which gives
$\|B\|_{(1)}\leq\frac{n}{2}$ for every
$B\in\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}$.)

Now if $A=[a_{ij}]$, be an equality case in Theorem 3, i.e.

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}=\frac{n}{2}\max_{i\neq
j}|a_{ij}|,$ (21)

we must have equality in both (19) and (20). So there must be some
$B\in\mathcal{D}_{n}^{\perp}$, such that

$\|B\|_{(1)}=\frac{n}{2}\|B\|_{1},$

and

$\langle A,B\rangle=\|A^{\prime}\|_{(\infty)}\|B\|_{(1)},$

which means that if $M=\max_{i,j}|A^{\prime}_{ij}|$, for every $i,j$ with
$B_{ij}\neq 0$, $A^{\prime}_{ij}=\pm{M}\mathrm{sgn}(B_{ij})$.

So all of solutions of (21), can be constructed as follows. Let
$B=[b_{ij}]\in\mathcal{S}_{n}$ be a nonzero matrix with diagonal zero, with
$\|B\|_{(1)}=\frac{n}{2}\|B\|_{1}$. For an arbitrary $M\geq 0$, let
$A=[a_{ij}]\in\mathcal{S}_{n}$ be the matrix for which,

$\forall i\neq j,\;|a_{ij}|\leq M,\quad\mathrm{and\;if}\;b_{ij}\neq
0\;\mathrm{then}\;a_{ij}=M\,\mathrm{sgn}(b_{ij}).$

The above construction can be applied to every introduced equality case of
Theorem 1 in Remark 1. For example if $n$ be even, we can define

$B=\mathbbm{1}\mathbbm{1}^{*}-\mathbf{v}\mathbf{v}^{*},\quad\mathbf{v}_{i}=\left\\{\begin{array}[]{ll}1&i\leq\frac{n}{2}\\\
-1&i>\frac{n}{2}\end{array}\right..$

Then for $B$, we have $\|B\|_{(1)}=\frac{n}{2}\|B\|_{1}$, and

$B=\left[\begin{matrix}0&2I_{\frac{n}{2}}\\\
2I_{\frac{n}{2}}&0\end{matrix}\right].$

So for every matrix $A$ of the form

$A=\left[\begin{matrix}*&I_{\frac{n}{2}}\\\
I_{\frac{n}{2}}&*\end{matrix}\right].$

the equality (21) holds, i.e.
$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}=\frac{n}{2}.$

###### Proof of Theorem 4.

The proof is completely similar to the proof of Theorem 3, and we omit the
details. One shows first that Theorem 2, implies the inclusion

$\mathcal{B}_{1}\cap\mathcal{D}_{n}^{\perp}\subset\cot(\frac{\pi}{2n})\mathcal{B}_{(1)},$
(22)

in the space $\mathcal{H}_{n}$. Applying the duality transformation, gives an
equivalent inclusion,

$\mathcal{B}_{(\infty)}\;\subset\;\cot(\frac{\pi}{2n})\mathcal{B}_{\infty}+\mathcal{D}_{n},$
(23)

which can be rewritten as the following inequality for every
$A=[a_{ij}]\in\mathcal{H}_{n}$,

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}\leq\cot(\frac{\pi}{2n})\max_{i\neq
j}|a_{ij}|.$ (24)

∎

######  Remark 4.

For finding the equality cases of Theorem 4, completely similar analysis to
Remark 3 can be made, and we only give the final answer here.

All of solutions of the equation,

$\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}=\cot(\frac{\pi}{2n})\max_{i\neq
j}|a_{ij}|,$ (25)

for $A\in\mathcal{H}_{n}$, can be constructed as follows. Let
$B=[b_{ij}]\in\mathcal{H}_{n}$ be a nonzero matrix with diagonal zero, and
$\|B\|_{1}=\tan(\frac{\pi}{2n})\|B\|_{(1)}$. For an arbitrary $M\geq 0$, let
$A=[a_{ij}]\in\mathcal{H}_{n}$ be the matrix for which,

$\forall i\neq j,\;|a_{ij}|\leq M,\;\mathrm{and\;if}\;b_{ij}\neq
0\;\mathrm{then}\;a_{ij}=M\,\frac{b_{ij}}{|b_{ij}|}.$

For example, if we consider
$B=\mathbbm{1}\mathbbm{1}^{*}-\boldsymbol{\alpha}\boldsymbol{\alpha}^{*}$ with
the same notation in the proof of Theorem 4, then we can obtain the following
solution $A=[a_{ij}]$ for (25),

$\forall i,\;a_{ii}=0,\quad\forall i\neq
j,\;a_{ij}=\frac{1-\zeta^{2(i-j)}}{|1-\zeta^{2(i-j)}|}=-\mathrm{i}\zeta^{i-j}\mathrm{sgn}(i-j),$

for $\zeta=\exp(\frac{\mathrm{i}\pi}{n})$.

Now if we define $E\in\mathcal{H}_{n}$ by,

$E_{ij}=\left\\{\begin{array}[]{ll}0&i=j\\\ \mathrm{sgn}(i-j)\mathrm{i}&i\neq
j\end{array}\right.,$

we have $A=-UEU^{*}$ for the diagonal matrix $U$ with diagonal entries
$(\zeta,\zeta^{2},\dots,\zeta^{n})$. Also $U$ is a unitary matrix and so,

$\displaystyle\cot(\frac{\pi}{2n})$
$\displaystyle=\min_{D\in\mathcal{D}_{n}}\|A-D\|_{\infty}=\min_{D\in\mathcal{D}_{n}}\|-UEU^{*}-D\|_{\infty}$
$\displaystyle=\min_{D\in\mathcal{D}_{n}}\|E+U^{*}DU\|_{\infty}=\min_{D\in\mathcal{D}_{n}}\|E-D\|_{\infty}.$

Therefore $E$ is also a simple solution for (25). By further computation,
$\|E\|_{\infty}=\cot(\frac{\pi}{2n})$ and so in fact the nearest diagonal
matrix to $E$ in the spectral norm is the zero matrix.

##  6 Proof of Lemma 5

###### Proof of Lemma 5..

Define $\mathcal{X}$ to be the set of all of pairs
$(\mathbf{d},\boldsymbol{\omega})$ with

$\mathbf{d}=(d_{1},\dots,d_{n})\in\mathbb{R}^{n}_{\geq
0},\;\sum_{i}d_{i}=1,\quad\boldsymbol{\omega}=(\omega_{1},\dots,\omega_{n})\in\mathbb{S}^{n},$

and define the function $F:\mathcal{X}\to\mathbb{R}$ by

$F(\mathbf{d},\boldsymbol{\omega})=\sum_{i,j}d_{i}d_{j}|\omega_{i}-\omega_{j}|.$

Also define

$\mathbbm{1}=(1,\dots,1),\quad\boldsymbol{\alpha}=(\alpha_{1},\dots,\alpha_{n}),\;\alpha_{k}=\exp(\mathrm{i}\frac{2(k-1)\pi}{n}),1\leq
k\leq n.$ (26)

Now $\mathcal{X}$ is a compact set and $F$ has a maximum value $M_{n}$ on $X$.
The statement of lemma is equivalent to showing that $M_{n}=\gamma_{n}$ and
$F(\frac{1}{n}\mathbbm{1},\boldsymbol{\alpha})=\gamma_{n}$.

The proof is done by induction on $n$. The case $n=1$ is trivial, and so we
can assume $n>1$ and $M_{n-1}=\gamma_{n-1}$.

We have,

$\displaystyle F(\frac{1}{n}\mathbbm{1},\boldsymbol{\alpha})$
$\displaystyle=\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}|1-\overline{\alpha_{i}}{\alpha_{j}}|$
$\displaystyle=\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}|1-\exp(\mathrm{i}\frac{2(j-i)\pi}{n})|$
$\displaystyle=\frac{1}{n^{2}}\times
n\sum_{k=0}^{n-1}|1-\exp(\mathrm{i}\frac{2k\pi}{n})|$
$\displaystyle=\frac{2}{n}\sum_{k=0}^{n-1}\sin(\frac{k\pi}{n})=\gamma_{n}.$

(By the identity
$|1-\exp(\mathrm{i}t)|=\sqrt{2-2\cos(t)}=\sqrt{4\sin^{2}(\frac{t}{2})}=2\sin(\frac{t}{2})$
for $t\in[0,2\pi]$.) Hence
$\gamma_{n}=F(\frac{1}{n}\mathbbm{1},\boldsymbol{\alpha})\leq M_{n}$ and
because $M_{n-1}=\gamma_{n-1}<\gamma_{n}$, $M_{n-1}<M_{n}$.

Now let

$(\tilde{\mathbf{d}}=(\tilde{d}_{1},\dots,\tilde{d}_{n}),\tilde{\boldsymbol{\omega}}=(\tilde{\omega}_{1},\dots,\tilde{\omega}_{n}))\in\mathcal{X},$

be a maximum point for $F$. By a rotation and rearrangement of
$\tilde{\omega}_{i}$’s and applying the same rearrangement to
$\tilde{d}_{i}$’s, we can assume that $\tilde{\omega}_{1}=1$ and for every
$1\leq k\leq n$,

$\tilde{\omega}_{k}=\exp(2\mathrm{i}\theta_{k}),\quad
0=\theta_{1}\leq\theta_{2}\leq\dots\leq\theta_{n}<\pi.$

By a sequence of steps, we prove that
$(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})=(\frac{1}{n}\mathbbm{1},\boldsymbol{\alpha})$,
and so $M_{n}=F(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})=\gamma_{n}$,
and we are done.

Step 1. $\tilde{\omega}_{i}$’s are pairwise distinct.

Suppose to the contrary, $\tilde{\omega}_{k}=\tilde{\omega}_{k+1}$ for some
$k$. Define the vectors
$\mathbf{d}^{\prime}=(d^{\prime}_{1},\dots,d^{\prime}_{n-1})$ and
$\boldsymbol{\omega}^{\prime}=(\omega^{\prime}_{1},\dots,\omega^{\prime}_{n-1})$
by,

$d^{\prime}_{i}=\left\\{\begin{array}[]{ll}\tilde{d}_{i}&i<k\\\
\tilde{d}_{k}+\tilde{d}_{k+1}&i=k\\\
\tilde{d}_{i+1}&i>k\end{array}\right.,\quad\omega^{\prime}_{i}=\left\\{\begin{array}[]{ll}\tilde{\omega}_{i}&i\leq
k\\\ \tilde{\omega}_{i+1}&i>k\end{array}\right..$

Then

$\displaystyle F(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})$
$\displaystyle=\sum_{i,j\neq
k,k+1}\tilde{d}_{i}\tilde{d}_{j}|\tilde{\omega}_{i}-\tilde{\omega}_{j}|+2\sum_{j}\tilde{d}_{k}\tilde{d}_{j}|\tilde{\omega}_{k}-\tilde{\omega}_{j}|$
$\displaystyle\quad+2\sum_{j}\tilde{d}_{k+1}\tilde{d}_{j}|\tilde{\omega}_{k+1}-\tilde{\omega}_{j}|$
$\displaystyle=\sum_{i,j\neq
k,k+1}\tilde{d}_{i}\tilde{d}_{j}|\tilde{\omega}_{i}-\tilde{\omega}_{j}|+2\sum_{j}(\tilde{d}_{k}+\tilde{d}_{k+1})\tilde{d}_{j}|\tilde{\omega}_{k}-\tilde{\omega}_{j}|$
$\displaystyle=F(\mathbf{d}^{\prime},\boldsymbol{\omega}^{\prime})\,\leq
M_{n-1}\,<M_{n},$

which is a contradiction.

Step 2. All of $\tilde{d}_{i}$’s are positive.

If say $d_{k}$=0, it can be easily seen that
$F(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})$ is equal to the value of
$F$ on the pair $(\mathbf{d}^{\prime},\boldsymbol{\omega}^{\prime})$ obtained
by deleting $\tilde{d}_{k}$ and $\tilde{\omega}_{k}$ from the coordinates of
$\tilde{\mathbf{d}}$ and $\tilde{\boldsymbol{\omega}}$. Again
$F(\mathbf{d}^{\prime},\boldsymbol{\omega}^{\prime})\leq M_{n-1}<M_{n}$, which
is impossible.

Step 3. $\tilde{d}_{1}=\tilde{d}_{2}=\dots=\tilde{d}_{n}$.

For a vector $\boldsymbol{\omega}=(\omega_{1},\dots,\omega_{n})$, define the
symmetric matrix $A=A(\boldsymbol{\omega})=[|\omega_{i}-\omega_{j}|]_{i,j}$.
Then we have

$F(\mathbf{d},\boldsymbol{\omega})=\mathbf{d}^{T}A\mathbf{d}.$

Because $\tilde{d}_{i}>0$ for every $1\leq i\leq n$, $\tilde{\mathbf{d}}$ is
an interior point of the set $\\{\mathbf{d}\in\mathbb{R}^{n}_{\geq
0}:\mathbbm{1}^{T}\mathbf{d}=0\\}$, and maximises the function
$F(\cdot,\tilde{\boldsymbol{\omega}})$ on this set. So by Lagrange multiplier
theorem, there is a real scalar $\lambda$ such that

$\nabla_{\mathbf{d}}F(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})=\lambda\mathbbm{1}.$

On the other hand,

$\nabla_{\mathbf{d}}F(\mathbf{d},\boldsymbol{\omega})=\nabla_{\mathbf{d}}(\mathbf{d}^{T}A\mathbf{d})=2A\mathbf{d}.$

Hence,

$A(\tilde{\boldsymbol{\omega}})\,\tilde{\mathbf{d}}=\frac{\lambda}{2}\mathbbm{1}.$
(27)

Now for every $i$, $\tilde{\omega}_{i}=\exp(2\mathrm{i}\theta_{i})$ and
$\tilde{\omega}_{i}$’s are pairwise distinct, so

$0=\theta_{1}<\dots<\theta_{n}<\pi.$

So in a sufficiently small neighborhood $\mathcal{B}$ of
$\boldsymbol{\theta}:=(\theta_{1},\dots,\theta_{n})$ in $\mathbb{R}^{n}$,
every $\boldsymbol{\sigma}=(\sigma_{1},\dots,\sigma_{n})\in B$ satisfies,

$\sigma_{1}<\sigma_{2}<\dots<\sigma_{n}<\pi,\quad\sigma_{n}-\sigma_{1}<\pi.$

Consider
$\boldsymbol{\omega}=(\omega_{1},\dots,\omega_{n})\in(\mathbb{S}^{1})^{n}$ as
a function of
$\boldsymbol{\sigma}=(\sigma_{1},\dots,\sigma_{n})\in\mathcal{B}$ by the
formula,

$\boldsymbol{\omega}(\boldsymbol{\sigma})=(\omega_{1},\dots,\omega_{n}),\quad\omega_{i}=\exp(2\mathrm{i}\sigma_{i}),\quad
1\leq i\leq n.$

Then for every $\boldsymbol{\sigma}\in\mathcal{B}$, and
$\boldsymbol{\omega}=\boldsymbol{\omega}(\boldsymbol{\sigma})$, there is a
simpler formula for $A(\boldsymbol{\omega})_{ij}$ in terms of $\sigma_{k}$’s,

$\displaystyle A(\boldsymbol{\omega})_{ij}=|\omega_{i}-\omega_{j}|$
$\displaystyle=|\exp(2\mathrm{i}\sigma_{i})-\exp(2\mathrm{i}\sigma_{j})|$
$\displaystyle=\sqrt{2-2\cos(2(\sigma_{i}-\sigma_{j}))}$
$\displaystyle=2\sin(|\sigma_{i}-\sigma_{j}|)=\left\\{\begin{array}[]{ll}2\sin(\sigma_{i}-\sigma_{j})&i\geq
j\\\ 2\sin(\sigma_{j}-\sigma_{i})&i<j\end{array}\right..$ (30)

Now $\tilde{\boldsymbol{\omega}}=\boldsymbol{\omega}(\boldsymbol{\theta})$,
and hence $\boldsymbol{\theta}$ is a maximum for the function
$F(\tilde{\mathbf{d}},\boldsymbol{\omega}(\cdot))$ on the set $\mathcal{B}$.
Thus derivation with respect to any of variables $\sigma_{i}$ for $1\leq i\leq
n$, gives,

$\displaystyle
0=\frac{\partial}{\partial\sigma_{i}}F(\tilde{\mathbf{d}},\tilde{\boldsymbol{\omega}})$
$\displaystyle=2\sum_{j=1}^{n}\tilde{d}_{i}\tilde{d}_{j}\frac{\partial}{\partial\sigma_{i}}A_{ij}(\tilde{\boldsymbol{\omega}})$
$\displaystyle=4\tilde{d}_{i}\left(\sum_{j<i}\tilde{d}_{j}\cos(\theta_{i}-\theta_{j})-\sum_{j>i}\tilde{d}_{j}\cos(\theta_{i}-\theta_{j})\right),$

and because $\tilde{d}_{i}>0$ for all $i$,

$\sum_{j<i}\tilde{d}_{j}\cos(\theta_{i}-\theta_{j})-\sum_{j>i}\tilde{d}_{j}\cos(\theta_{i}-\theta_{j})=0,\quad
1\leq i\leq n.$ (31)

Now define the anti-symmetric matrix $E$ as follows,

$E=[e_{ij}],\quad e_{ij}=\left\\{\begin{array}[]{ll}0&i=j\\\ -1&i<j\\\
1&i>j\end{array}\right..$

So we can rewrite the equations (27) and (31) as bellow,

$\displaystyle\sum_{j=1}^{n}e_{ij}\tilde{d}_{j}\sin(\theta_{i}-\theta_{j})=\frac{\lambda}{4},\quad
1\leq i\leq n,$ (32)
$\displaystyle\sum_{j=i}^{n}e_{ij}\tilde{d}_{j}\cos(\theta_{i}-\theta_{j})=0,\quad
1\leq i\leq n.$ (33)

Let’s define

$\phi_{i}=\exp(\mathrm{i}\theta_{i}),\quad 1\leq i\leq n.$

Then we have

$\phi_{i}\overline{\phi_{j}}=\exp(\mathrm{i}(\theta_{i}-\theta_{j}))=\cos(\theta_{i}-\theta_{j})+\mathrm{i}\sin(\theta_{i}-\theta_{j}).$

Hence the equations (32) and (33) are equivalent to one equation,

$\sum_{j=1}^{n}(\phi_{i}e_{ij}\overline{\phi_{j}})\,\tilde{d}_{j}=\frac{\mathrm{i}\lambda}{4},\quad
1\leq i\leq n.$ (34)

After a conjugation and multiplication of both sides of the above equation by
$\phi_{i}$ for every $i$, it becomes equivalent to the vector equation below,

$E\,[\phi_{1}\tilde{d}_{1}\,\dots\,\phi_{n}\tilde{d}_{n}]^{T}=-\frac{\mathrm{i}\lambda}{4}\,[\phi_{1}\,\dots\,\phi_{n}]^{T}.$
(35)

We claim (35) implies $\tilde{d}_{1}=\tilde{d}_{2}=\dots=\tilde{d}_{n}$. Let
$1\leq k<n$. By (35), for every $i$,

$\sum_{j=1}^{n}e_{ij}\tilde{d}_{j}\phi_{j}=-\frac{\mathrm{i}\lambda}{4}\phi_{i}.$

Subtraction of the above equation for $i=k$ from the the equation for $i=k+1$,
gives

$\tilde{d}_{k}\phi_{k}+\tilde{d}_{k+1}\phi_{k+1}=-\frac{\mathrm{i}\lambda}{4}(\phi_{k+1}-\phi_{k}).$

Now the right hand side is perpendicular to $\phi_{k+1}-\phi_{k}$. But for the
Euclidean inner product of the left hand side with $\phi_{k+1}-\phi_{k}$ we
have,

$\displaystyle\mathrm{Re}\left((\tilde{d}_{k}\phi_{k}+\tilde{d}_{k+1}\phi_{k+1})\overline{(\phi_{k+1}-\phi_{k})}\right)$
$\displaystyle=\tilde{d}_{k+1}-\tilde{d}_{k}-\tilde{d}_{k+1}\cos(\theta_{k+1}-\theta_{k})$
$\displaystyle\quad+\tilde{d}_{k}\cos(\theta_{k}-\theta_{k+1})$
$\displaystyle=(\tilde{d}_{k+1}-\tilde{d}_{k})(1-\cos(\theta_{k+1}-\theta_{k})).$

But $0<\theta_{k+1}-\theta_{k}<\pi$, and so $\cos(\theta_{k+1}-\theta_{k})\neq
1$. Thus we have $\tilde{d}_{k+1}-\tilde{d}_{k}=0$, for all $k<n$ and by
$\sum_{i}\tilde{d}_{i}=1$, we conclude

$\mathbf{\tilde{d}}=\frac{1}{n}\mathbbm{1}.$

(End of Step 3.)

Now for $\mu=-\frac{n\lambda}{4}$, the equation (35) can be simplified to

$E\boldsymbol{\phi}=(\mathrm{i}\mu)\,\boldsymbol{\phi},\quad\boldsymbol{\phi}=(\phi_{1},\dots,\phi_{n}),$
(36)

which shows that $\boldsymbol{\phi}$ is an eigenvector of $E$.

Step 4. $\tilde{\boldsymbol{\omega}}=\boldsymbol{\alpha}$.

Let $\zeta$ be a root of the equation $z^{n}=-1$. Then for every $1\leq i\leq
n$, we have,

$\displaystyle\sum_{j=1}^{n}e_{ij}\zeta^{j-1}$ $\displaystyle=\sum_{1\leq
j<i}\zeta^{j-1}-\sum_{i<j\leq n}\zeta^{j-1}$ $\displaystyle=-\left(\sum_{1\leq
j<i}\zeta^{n+j-1}+\sum_{i<j\leq n}\zeta^{j-1}\right)$
$\displaystyle=-\zeta^{i-1}\left(\zeta+\cdots+\zeta^{n-1}\right)$
$\displaystyle=\zeta^{i-1}\left((-\zeta)\cdot\frac{1-\zeta^{n-1}}{1-\zeta}\right)$
$\displaystyle=\zeta^{i-1}\left((-\zeta)\cdot\frac{1+\frac{1}{\zeta}}{1-\zeta}\right)=\zeta^{i-1}\left(\frac{\zeta+1}{\zeta-1}\right).$

Hence

$E\,[1\;\zeta\;\dots\;\zeta^{n-1}]^{T}=\left(\frac{\zeta+1}{\zeta-1}\right)[1\;\zeta\;\dots\;\zeta^{n-1}]^{T},$

and $(1,\zeta,\dots,\zeta^{n-1})$ is an eigenvector of $E$ for the eigenvalue
$\frac{\zeta+1}{\zeta-1}$. Now the equation $z^{n}=-1$ has $n$ distinct roots,

$\zeta_{i}=\exp(\mathrm{i}\frac{(2i-1)\pi}{n}),\quad\mathrm{for}\;1\leq i\leq
n,$

and because of non-singularity of the Vandermonde matrix
$[\zeta_{i}^{j-1}]_{i,j}$, the vectors
$\mathbf{z}_{i}:=(1,\zeta_{i},\dots,\zeta_{i}^{n-1})$ constitute a basis of
eigenvectors of $E$. On the other hand the mapping $z\to\frac{z+1}{z-1}$ is
one to one, and so $E$ has $n$ distinct eigenvalues
$\frac{\zeta_{i}+1}{\zeta_{i}-1}$.

Now $\boldsymbol{\phi}=(\phi_{1},\dots,\phi_{n})$ is also an eigenvector of
$E$, so for some $i$, $\boldsymbol{\phi}$ is an scalar multiple of
$\mathbf{z}_{i}$, and because $\phi_{1}=\exp(\mathrm{i}\theta_{1})=1$, this
scalar forced to be equal to $1$. Thus $\boldsymbol{\phi}=\mathbf{z}_{i}$.

Now note that the arguments of the coordinates of $\boldsymbol{\phi}$ are
$0=\theta_{1}<\dots<\theta_{n}<\pi$. Also the argument of the $j$-th
coordinate of $\mathbf{z}_{i}$ is
$a_{j}:=(j-1)\left(\frac{(2i-1)\pi}{n}\right)$ for $1\leq j\leq n$. For $j=2$,
$0<a_{2}=\frac{(2i-1)\pi}{n}<2\pi$, so $0<a_{2}=\theta_{2}<\pi$ and for every
$1\leq j<n$,

$0<a_{j+1}-a_{j}=\frac{(2i-1)\pi}{n}<2\pi,\quad
a_{j+1}=\theta_{j+1}+2m\pi\;\mathrm{for}\;\mathrm{some}\;m\in\mathbb{Z}.$

So by induction it can be easily seen that $a_{j}=\theta_{j}$ (for all $1\leq
j\leq n$), which implies

$\displaystyle\forall 1\leq j\leq
n,\;(j-1)\left(\frac{(2i-1)\pi}{n}\right)<\pi$
$\displaystyle\;\Longrightarrow(n-1)\left(\frac{(2i-1)\pi}{n}\right)<\pi$
$\displaystyle\;\Longrightarrow 2i-1<\frac{n}{n-1}\leq 2$
$\displaystyle\;\Longrightarrow i=1.$

So, $\boldsymbol{\phi}=\mathbf{z}_{1}=(1,\zeta_{1},\dots,\zeta_{1}^{n-1})$.

Now for every $1\leq i\leq n$ we have,

$\tilde{\omega}_{i}=\exp(2\mathrm{i}\theta_{i})=\phi_{i}^{2}=\zeta_{1}^{2(i-1)}=\exp(\frac{2(i-1)\pi}{n})=\alpha_{i}.$

Thus $\tilde{\boldsymbol{\omega}}=\boldsymbol{\alpha}$ and the proof is
complete. ∎

Acknowledgements. This work is in part supported by a grant (No. 1400050046)
from School of Mathematics, Institute for Research in Fundamental Sciences
(IPM).

## References

  * [AEKN20] Saieed Akbari, Mostafa Einollahzadeh, Mohammad Mahdi Karkhaneei, and Mohammad Ali Nematollahi.  Proof of a conjecture on the seidel energy of graphs.  European Journal of Combinatorics, 86:103078, 2020.
  * [Bha13] Rajendra Bhatia.  Matrix analysis, volume 169.  Springer Science & Business Media, 2013.
  * [GF17] Ivan Gutman and Boris Furtula.  Survey of graph energies.  Mathematics Interdisciplinary Research, 2(2):85–129, 2017.
  * [Hae12] Willem H Haemers.  Seidel switching and graph energy.  Available at SSRN 2026916, 2012.
  * [HJ12] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [Mat13] Jiri Matousek.  Lectures on discrete geometry, volume 212.  Springer Science & Business Media, 2013.
  * [Zha13] Xingzhi Zhan.  Matrix theory, volume 147.  American Mathematical Soc., 2013.

Mostafa Einollahzadeh, Department of Mathematical Sciences, Isfahan University
of Technology, Isfahan, Iran

School of Mathematics, Institute for Research in Fundamental Sciences (IPM),
P.O. Box 19395-5746, Tehran, Iran

e-mail<EMAIL_ADDRESS>