Maximum-energy conjecture for integral weighted trees

Full proof of the weighted-tree maximum-energy conjecture

We resolve the maximum-energy conjecture of R. A. Brualdi, J.-Y. Shao, S.-C. Gong, C.-Q. Xu, and G.-H. Xu, On the extremal energy of integral weighted graphs, Linear and Multilinear Algebra 60 (2012), 1255–1264, doi:10.1080/03081087.2011.624094. In fact, integrality is unnecessary: the same unique maximizer holds for arbitrary real edge weights bounded below by one.

Let $T$ be an $n$-vertex tree with real edge weights $w_e\geq1$, and suppose

$$n\geq5,\qquad \sum_{e\in E(T)}w_e=m>n-1,\qquad d=m-n+1>0,\qquad q=1+d=m-n+2. \tag{1}$$

Write $A(T,w)$ for its weighted adjacency matrix. Since this matrix is real symmetric, its energy is its nuclear norm:

$$\mathcal E(T,w)=\sum_{i=1}^{n}|\lambda_i(A(T,w))|=\|A(T,w)\|_*. \tag{2}$$

For each edge $e$, let $A_e$ be the adjacency matrix with weight $q$ on $e$ and weight one on every other edge. Setting $p_e=(w_e-1)/d$ gives the exact convex decomposition

$$p_e\geq0,\qquad \sum_ep_e=1,\qquad A(T,w)=\sum_ep_eA_e, \qquad \mathcal E(T,w)\leq\sum_ep_e\|A_e\|_*. \tag{3}$$

We first identify the largest energy among these concentrated-weight trees. Let $M_k(F)$ denote the number of $k$-edge matchings of an unweighted forest $F$ on $N$ vertices. Deleting a leaf $v$ and its neighbor $u$ gives

$$M_k(F)=M_k(F-v)+M_{k-1}(F-\{u,v\}), \qquad M_k(F)\leq\binom{N-k}{k}=M_k(P_N). \tag{4}$$

The inequality follows by induction and Pascal’s identity; isolated vertices are deleted separately. For a tree with a unique edge $e=uv$ of weight $q$, its weighted matching coefficients are

$$b_k(T,e)=M_k(T)+(q^2-1)M_{k-1}(T-\{u,v\}). \tag{5}$$

Consequently, if $P_n^*$ denotes the path whose unique weight-$q$ edge is pendent, then (4) yields, for every $k$,

$$b_k(T,e) \leq\binom{n-k}{k}+(q^2-1)\binom{n-k-1}{k-1} =b_k(P_n^*). \tag{6}$$

The Coulson integral for a weighted tree is

$$\mathcal E(T,e) =\frac{2}{\pi}\int_0^{\infty} \frac{1}{x^2}\log\left(\sum_{k\geq0}b_k(T,e)x^{2k}\right)\,dx. \tag{7}$$

Thus (6) implies $\mathcal E(T,e)\leq\mathcal E(P_n^*)$, strictly whenever any coefficient inequality is strict. In fact,

$$M_2(T)=\binom{n-1}{2}-\sum_{v\in V(T)}\binom{\deg_T(v)}2 \leq\binom{n-2}{2}, \tag{8}$$

with equality precisely when every vertex has degree at most two, that is, precisely when $T=P_n$. If $T=P_n$ but $e$ is not pendent, then $T-\{u,v\}$ has $n-4$ edges instead of the $n-3$ edges of $P_{n-2}$, making (6) strict at $k=2$. Therefore

$$\mathcal E(T,e)=\mathcal E(P_n^*) \quad\Longleftrightarrow\quad T=P_n\ \text{and }e\text{ is pendent}. \tag{9}$$

Combining (3) and (9) proves the claimed sharp upper bound. Moreover, equality in (3) forces $T=P_n$, all interior edges to have weight one, and the total excess $d$ to be supported on its two pendent edges. It remains to exclude a nontrivial split of this excess.

Let $B$ denote the bipartite adjacency block of a positively weighted path. It has full column rank, and

$$\mathcal E(P_n,w)=2\|B\|_*. \tag{10}$$

For every full-column-rank real matrix $B$, its nuclear norm has the unique orthogonal-column maximizer

$$\|B\|_* =\max_{Q^{\mathsf T}Q=I}\operatorname{tr}(Q^{\mathsf T}B), \qquad U(B)=B(B^{\mathsf T}B)^{-1/2}. \tag{11}$$

Let $B_L$ and $B_R$ put the entire excess $d$ on the left or right pendent edge. If any nontrivial convex combination attains their common nuclear norm, then its maximizer in (11) also maximizes both endpoint matrices. Uniqueness therefore implies

$$U(B_L)=U(B_R)=U\left(\frac{B_L+B_R}{2}\right). \tag{12}$$

Suppose first that $n=2r+1$. The blocks $B_L,B_R$ have size $(r+1)\times r$. A vector $z$ spanning the left kernel of a path block satisfies

$$w_{2j-1}z_j+w_{2j}z_{j+1}=0 \qquad(1\leq j\leq r). \tag{13}$$

In particular, the ratio $z_2/z_1$ equals $-q$ for $B_L$ and $-1$ for $B_R$. Their column spaces are therefore different, whereas (12) would give the same column space for both. Hence a nontrivial split cannot maximize the energy.

Now suppose $n=2r\geq6$. The blocks are invertible $r\times r$ lower-bidiagonal matrices. At the midpoint put

$$B=\frac{B_L+B_R}{2},\qquad G=B^{\mathsf T}B,\qquad B_L-B_R=d(E_{11}-E_{rr}). \tag{14}$$

If (12) held, then $U^{\mathsf T}B_L$ and $U^{\mathsf T}B_R$ would both be symmetric positive definite. Therefore $U^{\mathsf T}(E_{11}-E_{rr})$ would be symmetric. Since $r\geq3$, comparison of its $(2,1)$ and $(1,2)$ entries forces

$$U_{1,2}=0. \tag{15}$$

However, the first row of $B$ has its only nonzero entry $B_{1,1}=1+d/2>0$, so

$$U_{1,2}=B_{1,1}(G^{-1/2})_{1,2}. \tag{16}$$

The matrix $G$ is positive definite tridiagonal with strictly positive off-diagonal entries. For every $t>0$, the tridiagonal cofactor formula gives

$$[(G+tI)^{-1}]_{1,2} =-G_{1,2}\, \frac{\det((G+tI)_{\{3,\ldots,r\}})}{\det(G+tI)}<0. \tag{17}$$

The inverse-square-root integral consequently shows

$$(G^{-1/2})_{1,2} =\frac1\pi\int_0^{\infty} t^{-1/2}[(G+tI)^{-1}]_{1,2}\,dt<0, \tag{18}$$

contradicting (15). Thus no nontrivial split is extremal for even $n\geq6$ either.

We have proved the stronger real-weight theorem

$$\boxed{\displaystyle \mathcal E(T,w)\leq\mathcal E\big(P_n;(m-n+2,1,\ldots,1)\big), \qquad n\geq5,\quad w_e\geq1, } \tag{19}$$

with equality if and only if $T$ is a path and its unique edge of weight $m-n+2$ is pendent, up to reflection. Restricting to positive integral weights proves the original conjecture for every $n\geq5$ and $m\geq n$.

The restriction $n\geq5$ is sharp for uniqueness. When $n=4$, a path with consecutive weights $a,b,c$ has

$$\mathcal E(P_4;a,b,c)=2\sqrt{(a+c)^2+b^2}. \tag{20}$$

Thus every split of the excess between the two pendent edges, with $b=1$, attains the same maximum; this is precisely the exceptional equality phenomenon ruled out by (15) when $n\geq6$.