# Bounding the row sum arithmetic mean by Perron roots of row-permuted
matrices

Gernot Michael Engel<EMAIL_ADDRESS>Sergeĭ Sergeev
<EMAIL_ADDRESS>Transversal Networks Corp., 2753 Marshall Parkway,
Madison, WI 53713, USA  University of Birmingham, School of Mathematics,
Edgbaston B15 2TT, UK

###### Abstract

${\mathbb{R}}_{+}^{n\times n}$ denotes the set of $n\times n$ non-negative
matrices. For $A\in{\mathbb{R}}_{+}^{n\times n}$ let $\Omega(A)$ be the set of
all matrices that can be formed by permuting the elements within each row of
$A$. Formally:

$\Omega(A)=\\{B\in{\mathbb{R}}_{+}^{n\times n}:\forall i\;\exists\text{ a
permutation }\phi_{i}\;\text{s.t.}\ b_{i,j}=a_{i,\phi_{i}(j)}\;\forall j\\}.$

For $B\in\Omega(A)$ let $\rho(B)$ denote the spectral radius or largest non
negative eigenvalue of $B$. We show that the arithmetic mean of the row sums
of $A$ is bounded by the maximum and minimum spectral radius of the matrices
in $\Omega(A)$ Formally, we are showing that

$\min_{B\in\Omega(A)}\rho(B)\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\max_{B\in\Omega(A)}\rho(B).$

For positive $A$ we also obtain necessary and sufficient conditions for one of
these inequalities (or, equivalently, both of them) to become an equality. We
also give criteria which an irreducible matrix $C$ should satisfy to have
$\rho(C)=\min_{B\in\Omega(A)}\rho(B)$ or
$\rho(C)=\max_{B\in\Omega(A)}\rho(B)$. These criteria are used to derive
algorithms for finding such $C$ when all the entries of $A$ are positive .

###### keywords:

Perron root, row sums, rearrangement inequality AMS Classification: 15A18

##  1 Introduction

In what follows, ${\mathbb{R}}_{+}^{n}$ denotes the set of non-negative
vectors with length $n$ and ${\mathbb{R}}_{+}^{n\times n}$ denotes the set of
non-negative $n\times n$ matrices. For $x\in{\mathbb{R}}_{+}^{n}$ or,
respectively, $A\in{\mathbb{R}}_{+}^{n\times n}$ we write $x>0$ or,
respectively, $A>0$, if all entries of vector $x$ or matrix $A$ are positive.
We will work with the following matrix set, which can be defined for any
matrix $A$.

###### Definition 1.1

For $A\in{\mathbb{R}}^{n\times n}_{+}$, the matrix set $\Omega(A)$ consists of
the row-permuted matrices, whose entries in each row are a permutation of
entries in the corresponding row of $A$. Formally:

$\Omega(A)=\\{B\in{\mathbb{R}}_{+}^{n\times n}:\forall i\;\exists\text{a
permutation }\phi_{i}\;\text{s.t.}\ b_{i,j}=a_{i,\phi_{i}(j)}\;\forall j\\}.$
(1)

We will use the following standard notation for the Perron roots of matrices.

###### Definition 1.2

The Perron root (i.e. the largest non negative eigenvalue, or spectral radius)
of a matrix $B\in\Omega(A)$ will be denoted by $\rho(B)$.

For $A\in{\mathbb{R}}_{+}^{n\times n}$ the following row sum inequality

$\min_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\rho(A)\leq\max_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}$

was first observed by Frobenius. The geometric means of the row sums as bounds
for $\rho(A)$ were explored by Al’pin [1] and Elsner and van Driessche [2],
and further generalised by Engel et al. [5]. In this paper we are interested
in establishing a different connection between Perron roots and row sums.
Namely, we show that the arithmetic mean of the row sums satisfies

$\min_{B\in\Omega(A)}\rho(B)\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\max_{B\in\Omega(A)}\rho(B).$
(2)

For $A>0$ we obtain necessary and sufficient conditions for any of these
inequalities to turn into equalities. For $A\in{\mathbb{R}}_{+}^{n\times n}$
we also give necessary and sufficient criteria for an irreducible matrix
$C\in\Omega(A)$ to have $\rho(C)=\min_{B\in\Omega(A)}\rho(B)$ or
$\rho(C)=\max_{B\in\Omega(A)}\rho(B)$.

To obtain these results we make use, in particular, of the following well-
known facts. These facts, which we are going to use throughout the paper, are
closely related to the famous Collatz-Wielandt inequality and are summarized
in the following proposition:

######  Proposition 1.3 (e.g., [3], Theorem 1.11)

For $A\in{\mathbb{R}}_{+}^{n\times n}$ and constants $\alpha>0,\beta>0$ and
nonzero vector $x\in{\mathbb{R}}_{+}^{n}$ we have:

  * (i)

$\alpha x\leq Ax$ implies $\alpha\leq\rho(A)$,

  * (ii)

$Ax\leq\beta x$ with $x>0$ implies $\rho(A)\leq\beta$.

In addition, if $A$ is irreducible then the following implications hold:

  * (iii)

if $\alpha x\leq Ax$ and $\exists i$ such that $\alpha
x_{i}<\sum_{j=1}^{n}a_{i,j}x_{j}$ then $\rho(A)>\alpha$,

  * (iv)

if $Ax\leq\beta x$ and $i$ such that $\sum_{j=1}^{n}a_{i,j}x_{j}<\beta x_{i}$
then $\rho(A)<\beta$.

The next result, which we will use to derive the criteria for
$\rho(C)=\max_{B\in\Omega(A)}\rho(B)$ and
$\rho(C)=\min_{B\in\Omega(A)}\rho(B)$, is known as the rearrangement
inequality.

######  Proposition 1.4 (e.g., [6], page 261)

Let $x,y\in{\mathbb{R}}_{+}^{n}$ be such that $x_{1}\leq x_{2}\leq\ldots\leq
x_{n}$ and $y_{1}\leq y_{2}\leq\ldots\leq y_{n}$, and let
$\phi\colon\\{1,\ldots,n\\}\to\\{1,\ldots,n\\}$ be an arbitrary permutation.
Then the following inequalities hold:

$\sum_{i=1}^{n}x_{i}y_{n+1-i}\leq\sum_{i=1}^{n}x_{i}y_{\phi(i)}\leq\sum_{i=1}^{n}x_{i}y_{i}.$

##  2 Preliminary lemmas

The following lemma, related to the rearrangement inequality, establishes that
the maximum Perron root is achieved on a matrix with all positive entries for
which the correlation between the order of the components of its Perron
eigenvector and each of its row vectors is maximized. The minimum Perron root
is achieved when the correlation between the order of the components of its
Perron eigenvector and each of its row vectors is minimized.

###### Lemma 2.1

Let $A\in{\mathbb{R}}_{+}^{n\times n}$ be irreducible. Then the following
implications hold:

  * (i)

if $\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ and $x$ is a Perron eigenvector of
$A$ then for $1\leq i,j,k\leq n$:

$x_{k}<x_{j}\text{ implies }a_{i,k}\leq a_{i,j},$

  * (ii)

if $\rho(A)=\min_{B\in\Omega(A)}\rho(B)$ and $x$ is a Perron eigenvector of
$A$ then for $1\leq i,j,k\leq n$:

$x_{k}<x_{j}\text{ implies }a_{i,k}\geq a_{i,j}.$

Proof: (i): Assume that $A\in{\mathbb{R}}_{+}^{n\times n}$ is irreducible and
$\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ . Then $\exists x>0$ such that
$Ax=\rho(A)x$. By contradiction, assume that there exist $i,j,k$ such that
$x_{j}>x_{k}$ but $a_{i,j}<a_{i,k}$. Let $B$ be the matrix formed by swapping
the two entries $a_{i,j}$ and $a_{i,k}$ so that $b_{i,j}=a_{i,k}$ and
$b_{i,k}=a_{i,j},$ with all other entries of $B$ equal to the entries of $A$.
Then $B$ is in $\Omega(A)$. We have
$\rho(A)x_{i}=\sum_{j=1}^{n}a_{i,j}x_{j}<\sum_{j=1}^{n}b_{i,j}x_{j}$ and
$\sum_{j=1}^{n}a_{s,j}x_{j}=\sum_{j=1}^{n}b_{s,j}x_{j}$ for $s\neq i$. Thus by
Proposition 1.3 part (iii), $\rho(B)>\rho(A)$. Since this contradicts that
$\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ it follows that for $1\leq i,j,k\leq n\
x_{k}<x_{j}$ implies $a_{i,k}\leq a_{i,j}$ and (i) is established.

(ii): The proof is similar to the previous part, with the difference that here
we assume that $\rho(A)=\min_{B\in\Omega(A)}\rho(B)$. Upon assuming by
contradiction that there exist $i,j,k$ such that $x_{j}>x_{k}$ but
$a_{i,j}>a_{i,k}$ we define matrix $B$ by swapping the entries $a_{i,j}$ and
$a_{i,k}$ so that $b_{i,j}=a_{i,k}$ and $b_{i,k}=a_{i,j},$ with all other
entries of $B$ equal to the entries of $A$. Observing that
$\rho(A)x_{i}=\sum_{j=1}^{n}a_{i,j}x_{j}>\sum_{j=1}^{n}b_{i,j}x_{j}$ and
$\sum_{j=1}^{n}a_{s,j}x_{j}=\sum_{j=1}^{n}b_{s,j}x_{j}$ for $s\neq i$, we use
Proposition 1.3 part (iv) to obtain $\rho(B)<\rho(A)$, a contradiction
establishing part (ii). $\square$

Proof of the next lemma follows the reasoning used in the proof of
Tchebychef’s inequality [6] page 43.

###### Lemma 2.2

Let $A\in{\mathbb{R}}_{+}^{n\times n}$ have a Perron eigenvector
$x\in{\mathbb{R}}_{+}^{n}$ satisfying $\sum_{i=1}^{n}x_{i}=1$. Then the
following properties hold:

  * (i)

if $\forall i,j,k\ x_{k}<x_{j}$ implies $a_{i,k}\leq a_{i,j}$ then

$\forall i\
\frac{\sum_{j=1}^{n}a_{i,j}}{n}\leq\sum_{j=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i},$

  * (ii)

if $\forall i,j,k\ x_{k}<x_{j}$ implies $a_{i,k}\geq a_{i,j}$ then

$\forall i\
\frac{\sum_{j=1}^{n}a_{i,j}}{n}\geq\sum_{j=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i},$

  * (iii)

if $\forall i,j,k\ x_{k}<x_{j}$ implies $a_{i,k}\leq a_{i,j}$ or $\forall
i,j,k\ x_{k}<x_{j}$ implies $a_{i,k}\geq a_{i,j}$, then the following are
equivalent:

    * (a)

$\frac{\sum_{j=1}^{n}a_{i,j}}{n}=\sum_{j=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}$ for
all $i$;

    * (b)

either $x_{i}=\frac{1}{n}$ for all $i$, or for each $i$ there is $c_{i}$ such
that $c_{i}=a_{i,j}$ for all $j$.

Proof: (i): The property that $\forall 1\leq i,j,k\leq n$ $x_{k}<x_{j}$
implies $a_{i,k}\leq a_{i,j}$ is equivalent to
$(a_{i,j}-a_{i,k})(x_{j}-x_{k})\geq 0$. From this we obtain

$\begin{split}\forall i\
2nx_{i}\rho(A)&=\sum_{j=1}^{n}\sum_{k=1}^{n}(a_{i,j}x_{j}+a_{i,k}x_{k})\geq\sum_{j=1}^{n}\sum_{k=1}^{n}(a_{i,j}x_{k}+a_{i,k}x_{j})\\\
&\geq
2\left(\sum_{j=1}^{n}a_{i,j}\right)\left(\sum_{j=1}^{n}x_{j}\right)=2\sum_{j=1}^{n}a_{i,j}.\end{split}$

This implies

$\forall i\
\frac{\sum_{i=1}^{n}a_{i,j}}{n}\leq\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}$

establishing part (i).

(ii): The proof of this part is similar to the proof of part (i). Here we
first observe that the property that $\forall 1\leq i,j,k\leq n$ $x_{k}<x_{j}$
implies $a_{i,k}\geq a_{i,j}$ is equivalent to
$(a_{i,j}-a_{i,k})(x_{j}-x_{k})\leq 0$. Using this inequality in the same way
as in the proof of part (i) the opposite inequality is used, we obtain

$\forall i\
\frac{\sum_{i=1}^{n}a_{i,j}}{n}\geq\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A).$

establishing part (ii).

(iii): To establish (3) (a) implies (b) assume
$\frac{\sum_{i=1}^{n}a_{i,j}}{n}=\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}$ and
that either $\forall 1\leq i,j,k\leq n\ x_{k}<x_{j}$ implies $a_{i,k}\leq
a_{i,j}$ or $\forall 1\leq i,j,k\leq n\ x_{k}<x_{j}$ implies $a_{i,k}\geq
a_{i,j}.$

In the first case for any $i,j,k$ we have that
$(a_{i,j}-a_{i,k})(x_{j}-x_{k})\geq 0$ and in the second case we have that
$(a_{i,j}-a_{i,k})(x_{j}-x_{k})\leq 0$. In the first case, if there exists $i$
such that $(a_{i,j}-a_{i,k})(x_{j}-x_{k})>0$ for some $j$ and $k$ then
$\frac{\sum_{i=1}^{n}a_{i,j}}{n}<\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}.$
Similarly in the second case if there exists $i$ such that
$(a_{i,j}-a_{i,k})(x_{j}-x_{k})<0$, then
$\frac{\sum_{i=1}^{n}a_{i,j}}{n}>\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}.$
Since none of these strict inequalities holds, we have

$\forall i,j,k\ (a_{i,j}-a_{i,k})(x_{j}-x_{k})=0.$ (3)

For any $i=1,\ldots,n$ let $t(i)$ and $d(i)$ be defined (non-uniquely) by

$a_{i,t(i)}=\min_{j}a_{i,j},\quad a_{i,d(i)}=\max_{j}a_{i,j}$ (4)

and suppose that $x_{i}=x_{k}$ does not hold for all $i\neq k$. Our aim is to
show that then the coefficients in every row of $A$ are equal to each other.
Since either $\forall i,j,k$ $x_{k}<x_{j}$ implies $a_{i,k}\leq a_{i,j}$ or
$\forall i,j,k$ $x_{k}<x_{j}$ implies $a_{i,k}\geq a_{i,j}$, we can let $t(i)$
and $d(i)$ be defined in such a way that not only equalities (4) hold but also
in the first case $x_{t(i)}=\min_{j}x_{j}$ and $x_{d(i)}=\max_{j}x_{j}$ and in
the second case $x_{t(i)}=\max_{j}x_{j}$ and $x_{d(i)}=\min_{j}x_{j}$. In both
cases (3) entails that $(a_{i,t(i)}-a_{i,d(i)})(x_{t(i)}-x_{d(i)})=0$ and
hence $a_{i,t(i)}=a_{i,d(i)}$. By (4) we obtain that all all entries in the
$i$th row of $A$ are equal to each other, establishing the implication
(a)$\Rightarrow$(b).

To prove that (b) implies (a), first observe that obviously if
$x_{j}=\frac{1}{n}$ then
$\frac{\sum_{i=1}^{n}a_{i,j}}{n}=\sum_{i=1}^{n}a_{i,j}x_{j}=\rho(A)x_{i}.$ If
instead for each $i$ there is $c_{i}$ such that $a_{i,j}=c_{i}$ for all $j$,
then the unique Perron eigenvector $x$ with $\sum_{j=1}^{n}x_{j}=1$ has
coordinates $x_{i}=c_{i}/\sum_{j=1}c_{j}$ for all $i$ and the Perron root is
$\rho(A)=\sum_{j=1}^{n}c_{j}$. Indeed, we have

$\sum_{j=1}^{n}a_{i,j}x_{j}=c_{i}\sum_{i=1}^{n}x_{j}=c_{i}=\sum_{j=1}^{n}c_{j}\cdot\frac{c_{i}}{\sum_{j=1}^{n}c_{j}}=\rho(A)x_{i}.$

In this case
$\frac{\sum_{i=1}^{n}a_{i,j}}{n}=c_{i}=\sum_{j=1}^{n}a_{i,j}x_{j},$
establishing (a). $\square$

##  3 Main results

We begin this section by establishing the inequality between the arithmetic
mean of the rows and the largest and smallest Perron roots of matrices in
$\Omega(A)$.

###### Theorem 3.1

For any $A\in{\mathbb{R}}_{+}^{n\times n}$

$\min_{B\in\Omega(A)}\rho(B)\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\max_{B\in\Omega(A)}\rho(B).$
(5)

Proof: We first assume that $A>0$ and establish
$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\max_{B\in\Omega(A)}\rho(B)$
for such $A$. Select $C\in\Omega(A)$ such that
$\rho(C)=\max_{B\in\Omega(A)}\rho(B)$. Let $x>0$ be a Perron eigenvector of
$C$ such that $\sum_{i=1}^{n}x_{i}=1$. By Lemma 2.1 part (i) we have that for
$1\leq i,j,k\leq n\ x_{k}<x_{j}$ implies $c_{i,k}\leq c_{i,j}$. Then by Lemma
2.2 part (i) we have $\forall i\
\frac{1}{nx_{i}}\sum_{j=1}^{n}c_{i,j}\leq\sum_{j=1}^{n}c_{i,j}\frac{x_{j}}{x_{i}}=\max_{B\in\Omega(A)}\rho(B)$
and since $\sum_{j=1}^{n}c_{i,j}=\sum_{j=1}^{n}a_{ij}$ for all $i$, we obtain

$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\leq\sum_{i=1}^{n}\max_{B\in\Omega(A)}\rho(B)x_{i}=\max_{B\in\Omega(A)}\rho(B).$

Still assuming $A>0$, we can establish
$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\geq\min_{B\in\Omega(A)}\rho(B)$
in a similar way. For this we select $C\in\Omega(A)$ such that
$\rho(C)=\min_{B\in\Omega(A)}\rho(B)$ and let $x>0$ be a Perron eigenvector of
$C$ such that $\sum_{i=1}^{n}x_{i}=1$. Combining Lemma 2.1 part (ii) with
Lemma 2.2 part (ii) we obtain $\forall i\
\frac{1}{nx_{i}}\sum_{j=1}^{n}c_{i,j}\geq\sum_{j=1}^{n}c_{i,j}\frac{x_{j}}{x_{i}}$
and hence

$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\geq\sum_{i=1}^{n}\min_{B\in\Omega(A)}\rho(B)x_{i}=\min_{B\in\Omega(A)}\rho(B).$

Now for arbitrary $A\in{\mathbb{R}}_{+}^{n\times n}$ and $\epsilon>0$ we
define $A^{\epsilon}=(a^{\epsilon}_{i,j})=(a_{i,j}+\epsilon)$. Then since
$0<A^{\epsilon}$ we have that
$\min_{B\in\Omega(A^{\epsilon})}\rho(B)\leq\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}(a_{i,j}+\epsilon)\leq\max_{B\in\Omega(A^{\epsilon})}\rho(B).$
Thus by continuity of the Perron root and letting $\epsilon$ go to zero we
obtain the desired inequality for $A$. $\square$

We now establish the conditions when any of the inequalities in Theorem 3.1
becomes an equality.

###### Theorem 3.2

For $0<A\in{\mathbb{R}}_{+}^{n\times n}$ the following are equivalent:

  * (i)

$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}=\max_{B\in\Omega(A)}\rho(B)$.

  * (ii)

Either the flat vector $x=(x_{i})$ where $\forall i\ x_{i}=1$ is a Perron
eigenvector of $A$ or there exists a non singular diagonal matrix $\exists\
D\geq 0$ such that $DA$ is a flat matrix (i.e. $\forall i,j\ d_{i}a_{i,j}=1$
).

  * (iii)

$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}=\min_{B\in\Omega(A)}\rho(B)$.

Proof: We first establish (i)$\Rightarrow$(ii). By (i),
$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}=\max_{B\in\Omega(A)}\rho(B).$
Since the set $\Omega(A)$ is finite, there exist $C\in\Omega(A)$ and
$y\in{\mathbb{R}}_{+}^{n\times n}$ with $\sum_{i=1}^{n}y_{i}=1$ such that
$Cy=(\max_{B\in\Omega(A)}\rho(B))y$. Thus

$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i,j}y_{j}=\left(\max_{B\in\Omega(A)}\rho(B)\right)\left(\sum_{i=1}^{n}y_{i}\right)=\max_{B\in\Omega(A)}\rho(B)=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\frac{1}{n}.$

By Lemma 2.1 part (i) $\forall i,j,k\colon 1\leq i,j,k\leq n$ we have that
$y_{k}<y_{j}$ implies $c_{i,k}\leq c_{i,j}$. Then by Lemma 2.2 part (i)

$\forall i\
\frac{1}{n}\sum_{j=1}^{n}c_{i,j}\leq\sum_{j=1}^{n}c_{i,j}y_{j}=\max_{B\in\Omega(A)}\rho(B)y_{i}.$

Since $\forall i\
\frac{1}{n}\sum_{j=1}^{n}a_{i,j}=\frac{1}{n}\sum_{j=1}^{n}c_{i,j}$ we can
rewrite this as

$\forall i\
\frac{1}{n}\sum_{j=1}^{n}a_{i,j}\leq\max_{B\in\Omega(A)}\rho(B)y_{i}.$

As by (i) we have

$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}=\max_{B\in\Omega(A)}\rho(B)=\max_{B\in\Omega(A)}\rho(B)\sum_{i=1}^{n}y_{i},$

if there exists $i$ such that
$\frac{1}{n}\sum_{j=1}^{n}a_{i,j}<\max_{B\in\Omega(A)}\rho(B)y_{i}$ then there
would have to exist $k$ such that
$\frac{1}{n}\sum_{j=1}^{n}a_{k,j}>\max_{B\in\Omega(A)}\rho(B)y_{k}$, which is
a contradiction, hence

$\forall
i\max_{B\in\Omega(A)}\rho(B)y_{i}=\frac{1}{n}\sum_{j=1}^{n}a_{i,j}=\sum_{j=1}^{n}c_{i,j}y_{j}=\frac{1}{n}\sum_{j=1}^{n}c_{i,j}.$

Applying Lemma 2.2 part (iii), we obtain that either $\forall i\ y_{i}=1/n$ or
$\forall i,j,k\ c_{i,j}=c_{i,k}$. If $\forall i\ y_{i}=1/n$ then $\forall i\
\frac{1}{n}\sum_{j=1}^{n}a_{i,j}=\max_{B\in\Omega(A)}\rho(B)\frac{1}{n}$, from
which it follows that flat vector $x=(x_{i})$ where $\forall i\ x_{i}=1$ is a
Perron eigenvector of $A.$ If $\forall i,j,k\ c_{i,j}=c_{i,k}$ then $\forall
i,j,k\ a_{i,j}=c_{i,j}=c_{i,k}=a_{i,k}.$ Let $D$ be the diagonal matrix where
$\forall i\ d_{i,i}=\frac{1}{a_{i,i}}$ and the rest of the entries of $D$ are
$0$. Thus $DA$ is the flat matrix such that $\forall i,j\ d_{i}a_{i,j}=1.$

We now show (ii)$\Rightarrow$(i),(iii). Assume first that the flat vector
$x=(x_{i})$ where $\forall i\ x_{i}=1$ is a Perron eigenvector of $A$. This is
equivalent to all row sums of $A$ being equal to each other. If this property
holds for $A$ then it also holds for all $B\in\Omega(A)$, so the flat vector
is a Perron eigenvector of any such $B$ with the same Perron root (equal to
any of the row sums). Thus we have both (i) and (iii), i.e.,

$\max_{B\in\Omega(A)}\rho(B)=\min_{B\in\Omega(A)}\rho(B)=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}.$
(6)

Now assume that there exists a non-singular diagonal matrix $D\geq 0$ such
that $DA$ is a flat matrix. In this case the entries in each row of $A$ are
equal to each other, implying that $\Omega(A)=\\{A\\}$. As the left hand side
and the right hand side of (5) are equal to each other, we obtain (6).

Finally, the proof of (iii)$\Rightarrow$ (ii) is similar to the proof of
(i)$\Rightarrow$(ii) and will be described more briefly. By (ii),
$\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}=\min_{B\in\Omega(A)}\rho(B).$
Since the set $\Omega(A)$ is finite, there exist $C\in\Omega(A)$ and
$y\in{\mathbb{R}}_{+}^{n\times n}$ with $\sum_{i=1}^{n}y_{i}=1$ such that
$Cy=(\min_{B\in\Omega(A)}\rho(B))y$. Thus

$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i,j}y_{j}=\left(\min_{B\in\Omega(A)}\rho(B)\right)\left(\sum_{i=1}^{n}y_{i}\right)=\min_{B\in\Omega(A)}\rho(B)=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\frac{1}{n}.$

Next, combining Lemma 2.1 part (ii) and Lemma 2.2 part (ii) and using that for
each $i$ the sum of the $i$th row of $A$ equals the sum of the $i$th row of
$C$, we obtain

$\forall i\
\frac{1}{n}\sum_{j=1}^{n}a_{i,j}\geq\min_{B\in\Omega(A)}\rho(B)y_{i}.$

Using condition (iii), however, we see that the strict inequality cannot hold
for any $i$ and therefore we have

$\forall
i\min_{B\in\Omega(A)}\rho(B)y_{i}=\frac{1}{n}\sum_{j=1}^{n}a_{i,j}=\sum_{j=1}^{n}c_{i,j}y_{j}=\frac{1}{n}\sum_{j=1}^{n}c_{i,j}.$

Condition (ii) then follows by applying Lemma 2.2 part (iii) (see the end of
the proof of (i)$\Rightarrow$(ii) written above.) $\square$

The following result applies the rearrangement inequality (Proposition 1.4) to
yield a sufficient condition for establishing when
$\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ and
$\rho(A)=\min_{B\in\Omega(A)}\rho(B)$.

###### Theorem 3.3

Let $A\in{\mathbb{R}}_{+}^{n\times n}$ and $0\leq x\in{\mathbb{R}}_{+}^{n}$ be
a Perron eigenvector of $A$. Then

$\left(\forall\ i,j,k\ 1\leq i,j,k\leq n:x_{k}<x_{j}\;\Rightarrow\;a_{i,k}\leq
a_{i,j}\right)\Longrightarrow\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ (7)
$\left(\forall\ i,j,k\ 1\leq i,j,k\leq n:x_{k}<x_{j}\;\Rightarrow\;a_{i,k}\geq
a_{i,j}\right)\Longrightarrow\rho(A)=\min_{B\in\Omega(A)}\rho(B)$ (8)

Proof: Consider the condition on the left hand side of (7). Observe that we
can assume without loss of generality that $a_{i,k}\leq a_{i,j}\Leftrightarrow
a_{l,k}\leq a_{l,j}$ for any two rows $i$ and $l$ of $A$. Indeed, if
$x_{k}<x_{j}$ then this is the case (by the condition), and if $x_{k}=x_{j}$
then the entries $a_{i,k}$ and $a_{i,j}$ or $a_{l,k}$ and $a_{l,j}$ can be
swapped without changing $Ax$, so that the modified matrix belongs to
$\Omega(A)$ and has the same Perron eigenvector $x$ and the same Perron root
$\rho(A)$. Then we can also assume without loss of generality that
simultaneously $x_{1}\leq x_{2}\leq\ldots\leq x_{n}$ and $a_{i,1}\leq
a_{i,2}\leq\ldots\leq a_{i,n}$ for all $i$. If we consider any matrix
$B\in\Omega(A)$, then the rearrangement inequality implies that $Bx\leq
Ax=\rho(A)x$ and hence $\rho(B)\leq\rho(A)$.

Similarly, to prove the sufficiency of the condition on the right hand side of
(10), we can assume without loss of generality that $a_{i,k}\geq
a_{i,j}\Leftrightarrow a_{l,k}\geq a_{l,j}$ for any two rows $i$ and $l$ of
$A$. Indeed, if $x_{k}<x_{j}$ then this is the case (by the condition), and if
$x_{k}=x_{j}$ then the corresponding non-aligning entries in any row can be
swapped to obtain the alignment. Then we can also assume without loss of
generality that simultaneously $x_{1}\leq x_{2}\leq\ldots\leq x_{n}$ and
$a_{i,1}\geq a_{i,2}\geq\ldots\geq a_{i,n}$ for all $i$. If we consider any
matrix $B\in\Omega(A)$, then the rearrangement inequality implies that $Bx\geq
Ax=\rho(A)x$ and hence $\rho(B)\geq\rho(A)$. $\square$

The following result applies Lemma 2.1 to show that for irreducible matrices
conditions (7) and (8) of Theorem 3.3 are necessary and sufficient for
$\rho(A)=\max_{B\in\Omega(A)}\rho(B)$ or
$\rho(A)=\min_{B\in\Omega(A)}\rho(B)$.

###### Theorem 3.4

Let $A\in{\mathbb{R}}_{+}^{n\times n}$ be irreducible and
$0<x\in{\mathbb{R}}_{+}^{n}$ be a Perron eigenvector of $A$. Then

$\rho(A)=\max_{B\in\Omega(A)}\rho(B)\Longleftrightarrow\ \left(\forall\ i,j,k\
1\leq i,j,k\leq n:x_{k}<x_{j}\;\Rightarrow\;a_{i,k}\leq a_{i,j}\right)$ (9)
$\rho(A)=\min_{B\in\Omega(A)}\rho(B)\Longleftrightarrow\ \left(\forall\ i,j,k\
1\leq i,j,k\leq n:x_{k}<x_{j}\;\Rightarrow\;a_{i,k}\geq a_{i,j}\right)$ (10)

Proof: By Lemma 2.1, the conditions on the right hand sides of (9) and(10) are
necessary. The fact that they they are sufficient follows immediately from
Theorem 3.3. $\square$

##  4 Solving $\max_{B\in\Omega(A)}\rho(B)$ and $\min_{B\in\Omega(A)}\rho(B)$

Below we give two simple iterative procedures for solving
$\max_{B\in\Omega(A)}\rho(B)$ and $\min_{B\in\Omega(A)}\rho(B)$. Note that the
computation of the minimum and maximum spectral radius over sets more general
than $\Omega(A)$ was investigated by Protasov [7] where similar iterative
procedures were suggested.

Before presenting the iterative procedures we first establish the following
lemmas.

###### Lemma 4.1

Let $A\in{\mathbb{R}}_{+}^{n\times n}$ and $P$ be a permutation matrix. Then
$\rho(PA)=\rho(AP)$.

Proof: It is easy to see that any eigenvalue of $PA$ is an eigenvalue of $AP$
and the other way around:

$\begin{split}PAx=\alpha x&\Rightarrow AP(P^{-1}x)=\alpha(P^{-1}x),\\\
APy=\beta y&\Rightarrow PA(Py)=\beta(Py).\end{split}$

$\square$

###### Lemma 4.2

For $A\in{\mathbb{R}}_{+}^{n\times n}\text{ and all permutation matrices }P$

$\max_{B\in\Omega(A)}\rho(B)=\max_{B\in\Omega(PA)}\rho(B)$

and

$\min_{B\in\Omega(A)}\rho(B)=\min_{B\in\Omega(PA)}\rho(B).$

Proof: Take arbitrary $B\in\Omega(PA)$. Then $B=PC$, where $C\in\Omega(A)$,
and by Lemma 4.1 $\rho(B)=\rho(CP)$, where $CP\in\Omega(A)$. This observation
implies that

$\max_{B\in\Omega(A)}\rho(B)\geq\max_{B\in\Omega(PA)}\rho(B),\quad\min_{B\in\Omega(A)}\rho(B)\leq\min_{B\in\Omega(PA)}\rho(B).$

The reverse inequalities follow from a similar argument where we start with
$B=\Omega(A)$ and represent $B=P^{-1}C$ with $C\in\Omega(PA)$. $\square$

###### Definition 4.3

A $n\times n$ matrix $A$ is said to be fully indecomposable if $PAQ$ is
irreducible for all permutation matrices $P$ and $Q$.

Algorithm 1 Solving $\max_{B\in\Omega(A)}\rho(B)$

0: $A\in{\mathbb{R}}_{+}^{n\times n}$ with $A$ fully indecomposable.

1: Define matrix $C_{0}\in\Omega(A)$ by placing the entries in each row of $A$
in ascending order.

2: Find a permutation matrix $Q\in{\mathbb{R}}_{+}^{n\times n}$ such that the
Euclidean norms of the rows of $QC$ are in ascending order.

3: $P\in{\mathbb{R}}_{+}^{n\times n}$ is the zero matrix, $C:=QC_{0}$.

4: while $P$ is not the identity matrix do

5: Find a Perron eigenvector $x\in{\mathbb{R}}_{+}^{n}$ of $C$

6: if the entries of $x$ are not in ascending order then

7: Find a permutation matrix $P\in{\mathbb{R}}_{+}^{n\times n}$ so that
entries of $Px$ are in ascending order.

8: else

9: Set $P$ to be the identity matrix.

10: end if

11: $C:=PC$, $Q:=PQ$.

12: end while

12: $C_{0}Q,$ $\rho(C_{0}Q)=\max_{B\in\Omega(A)}\rho(B)$

Algorithm 2 Solving $\min_{B\in\Omega(A)}\rho(B)$

0: $A\in{\mathbb{R}}_{+}^{n\times n}$ with $A$ fully indecomposable.

1: Define matrix $C_{0}\in\Omega(A)$ by placing the entries in each row of $A$
in descending order.

2: Find a permutation matrix $Q\in{\mathbb{R}}_{+}^{n\times n}$ such that the
Euclidean norms of the row sums of $QC$ are in descending order.

3: $P\in{\mathbb{R}}_{+}^{n\times n}$ is the zero matrix, $C:=QC_{0}$.

4: while $P$ is not the identity matrix do

5: Find a Perron eigenvector $x\in{\mathbb{R}}_{+}^{n}$ of $C$

6: if the entries of $x$ are not in descending order then

7: Find a permutation matrix $P\in{\mathbb{R}}_{+}^{n\times n}$ so that
entries of $Px$ are in descending order.

8: else

9: Set $P$ to be the identity matrix.

10: end if

11: $C:=PC$, $Q:=PQ$.

12: end while

12: $C_{0}Q$, $\rho(C_{0}Q)=\min_{B\in\Omega(A)}\rho(B)$

We now argue that Algorithm 1 is valid. Observe that if in step 6 vector $x$
is not in ascending order and hence $P$ is not the identity matrix, then
$C(Px)\geq Cx=\rho(C)x$ with at least one strict inequality, since all rows of
$C$ as well as $Px$ are aligned together in ascending order, but this is not
true about all rows of $C$ and vector $x$. Then we obtain
$(PC)Px\geq\rho(C)Px$ with at least one strict inequality, and by Proposition
1.3 part (iii) $\rho(C)<\rho(PC)$. If $P$ is the identity matrix then
$\forall\ i,j,k\ 1\leq i,j,k\leq n:x_{k}<x_{j}\;\Rightarrow\;c_{i,k}\leq
c_{i,j}$ and by Theorem 3.4 $\rho(C)=\max_{B\in\Omega(C)}\rho(B).$ By Lemma
4.2 it follows that $\rho(C)=\max_{B\in\Omega(A)}\rho(B)$. The algorithm
terminates in a finite number of iterations since $\rho(C)$ is strictly
increasing so matrices $C$ do not repeat, and since the number of permutations
is finite. Lemma 4.1 also implies that for the final matrix $C$ we have
$\rho(C)=\rho(C_{0}Q)$, implying that $C_{0}Q$ solves the problem of
maximizing $\rho(B)$ over $\Omega(A)$ (while belonging to $\Omega(A)$).

Algorithm 2 is valid for the reasons similar to those explained above for
Algorithm 1. We now demonstrate the work of Algorithm 1 on the following small
example.

###### Example 4.4

Consider matrix

$A=\begin{pmatrix}2&5&2&2&5\\\ 6&6&2&3&1\\\ 7&3&5&5&3\\\ 3&3&4&6&8\\\
2&4&2&5&5\end{pmatrix}$

First we align all rows of this matrix in ascending order thus obtaining
$C_{0}$. The Euclidian norms of the row sums if $C$ are $11,$ $12,$ $18,$ $27$
and $31$. Thus initially $Q=I$ and $C=QC_{0}=C_{0}$ with its Perron vector
$x$:

$C=QC_{0}=\begin{pmatrix}2&2&2&5&5\\\ 1&2&3&6&6\\\ 3&3&5&5&7\\\ 3&3&4&6&8\\\
2&2&4&5&5\end{pmatrix},\quad x\approx\begin{pmatrix}0.3561\\\ 0.4098\\\
0.5091\\\ 0.5301\\\ 0.4063\end{pmatrix}$

The components of $x$ are not ascending and we have:

$P=\begin{pmatrix}1&0&0&0&0\\\ 0&0&0&0&1\\\ 0&1&0&0&0\\\ 0&0&1&0&0\\\
0&0&0&1&0\end{pmatrix}$

The next while loop proceeds, since $P\neq I$. We compute the next matrix $C$
and its Perron eigenvector $x$:

$\begin{split}C:=PQC_{0}=\begin{pmatrix}2&2&2&5&5\\\ 2&2&4&5&5\\\ 1&2&3&6&6\\\
3&3&5&5&7\\\ 3&3&4&6&8\end{pmatrix},\quad x\approx\begin{pmatrix}0.3595\\\
0.3987\\\ 0.4116\\\ 0.5055\\\ 0.5355\end{pmatrix}\end{split}$

Here, $x$ is in the ascending order. The algorithm ends and returns

$C_{0}PQ=\begin{pmatrix}2&2&5&5&2\\\ 1&3&6&6&2\\\ 3&5&5&7&3\\\ 3&4&6&8&3\\\
2&4&5&5&2\end{pmatrix},\quad\rho(C_{0}PQ)\approx 20.9863.$

###### Remark 4.5

We conducted a number of numerical experiments, in which we increased the
matrix dimension from 5 to 200. For each dimension we generated 50 random
instances of $A$ and counted the number of while loops that Algorithms 1 and 2
require before convergence. For the whole dimension range, the average number
of while loops stayed with the maximum number of loops not exceeding 3.
Finding a reasonable upper bound on the number of loops before convergence is
an open problem. Note that Cvetković and Protasov [4] establish that a similar
algorithm has local quadratic convergence (see [4], page 19).

## References

  * [1] Yu.A. Al’pin, Bounds for the Perron root of a non negative matrix involving properties of its graph, Math. Notes (Moscow), 58, 1995, p. 1121-1123.
  * [2] L. Elsner, P. van den Driessche, Bounds for the Perron root using max eigenvalues, Linear Algebra Appl. 428, 2005, p. 2000-2005.
  * [3] A. Berman, R.J. Plemmons. Nonnegative Matrices in Mathematical Sciences, Academic Press, New York et al.,1979.
  * [4] A. Cvetković and V.Yu. Protasov, The Greedy Strategy for Optimizing the Perron eigenvalue, Mathematical Programming 193, 2022, p. 1-31.
  * [5] G.M. Engel, H. Schneider and S. Sergeev. On sets of eigenvalues of matrices with prescribed row sums and prescribed graph. Linear Algebra Appl. 455, 2014, p. 187-209.
  * [6] G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities , 2nd edition, Cambridge University Press, 1953.
  * [7] V.Yu. Protasov, Spectral simple method, Mathematical Programming, Ser. A 156, 2016, p. 485-511.


# Glassy phases of the Gaussian Core Model

Vittoria Sposini  Faculty of Physics, University of Vienna, Boltzmanngasse 5,
1090 Vienna, Austria  Christos N. Likos  Faculty of Physics, University of
Vienna, Boltzmanngasse 5, 1090 Vienna, Austria  Manuel Camargo  Facultad de
Ciencias & CICBA, Universidad Antonio Nariño–Campus Farallones, Km 18 via
Cali-Jamundí, 760030 Cali, Colombia

###### Abstract

We present results from molecular dynamics simulations exploring the
supercooled dynamics of the Gaussian Core Model in the low- and intermediate-
density regimes. In particular, we discuss the transition from the low-density
hard-sphere-like glassy dynamics to the high-density one. The dynamics at low
densities is well described by the _caging_ mechanism, giving rise to
intermittent dynamics. At high densities, the particles undergo a more
continuous motion in which the concept of cage loses its meaning. We elaborate
on the idea that these different supercooled dynamics are in fact the
precursors of two different glass states.

Soft colloids encompass a large variety of nano- or mesoscopic aggregates
undergoing thermal motion in a solvent. In most cases, these are polymer-based
assemblies of various architectures and connectivities, such as linear chains,
stars and rings, dendrimers, block-copolymer micelles, but also cross-linked
nano- or microgels, which feature a high degree of flexibility and
deformability [1]. The degree of softness is conveniently expressed by the
ratio $E_{\mathrm{el}}/k_{\rm B}T$ of their elastic deformation energy upon
small overlaps or indentations, $E_{\mathrm{el}}$, over the thermal energy
$k_{\rm B}T$, which can span several orders of magnitude [1, 2]. Their
suspensions exhibit structural and dynamical anomalies [3, 4, 5, 6], which
accompany rich types of thermodynamic behavior, such as reentrant melting [7,
8, 9, 10, 11], and clustering [12, 13]. The deformability of these soft
colloids manifests itself under flow as particle elongation, tumbling and
shear-thinning [14, 15, 16, 17, 18]. Akin to hard colloids in the supercooled
regime, soft colloids exhibit a sharp increase of the equilibrium relaxation
time and heterogeneous dynamics [1, 19, 20, 21]. However, at very high
concentrations, soft colloids can reach a particular aging regime
characterized by an intermittent release of internal stresses which coincides
with the onset of an anomalous decrease in local order [22]. Colloidal
softness has been also related to the microscopic origin leading to the
validity of the Stokes-Einstein relation for degrees of metastability for
which it normally breaks down in the case of hard colloidal and molecular
systems [23].

From a theoretical point of view, the effective interaction $v(r)$ between a
pair of such colloids does not grow fast as $r\to 0$, so that the integral
$\int_{0}^{\infty}v(r){\rm d}^{3}r$ is finite. In some cases, these are
effective interactions between the centers of mass of open, fractal, fully
penetrable objects, for which $v(r)$ remains finite (free of divergence) even
if the separation $r$ vanishes. Denoting with $\hat{v}(k)$ the Fourier
transform of $v(r)$, such effective interactions are referred to as $Q^{+}$
potentials if $\hat{v}(k)$ is positive definite and as $Q^{\pm}$ potential if
$\hat{v}(k)$ attains both positive and negative values, typically in an
oscillatory fashion [24]. Systems belonging to the $Q^{+}$ class undergo a
reentrant fluid-crystal-fluid transition at low temperature and high density
and they possess a maximum freezing temperature, beyond which no
crystallization is possible whereas systems of the $Q^{\pm}$ class bond
together forming cluster crystals, where each lattice site is occupied by
several overlapping particles [24, 13]

Within the realm of $Q^{+}$ potentials a prominent role is played by the
Gaussian Core Model (GCM) introduced by Stillinger in the 70’s [7]. The GCM is
one of the simplest models for the description of systems such as polymer or
dendrimer solutions [25, 26] and it entails an inter-particle Gaussian-shaped
potential

$v(r)=\epsilon\exp[-(r/\sigma)^{2}],$ (1)

where $\epsilon$ and $\sigma$ are the energy and length scales. We define a
reduced density $\rho\to\rho\sigma^{3}$ and a reduced temperature $T\to
k_{B}T/\epsilon$, where $\rho=N/V$ is the number density, $k_{B}$ is
Boltzmann’s constant, and $T$ the absolute temperature. We measure lengths in
units of $\sigma$ and times in units of $\sigma\sqrt{m/\epsilon}$, where $m$
is the mass of each particle. Whereas at low temperatures and low densities,
the equilibrium properties of the GCM can be described by an effective hard-
sphere mapping [7], at high densities a mean-field description sets in, giving
rise to re-entrant melting below a threshold upper freezing temperature
$T_{u}=8.74\times 10^{-3}$, above which it remains fluid at all densities [7,
27, 28]. The equilibrium phase diagram of the GCM, along with two predictions
for its vitrification line, arising from two different approximations, is
shown in Fig. 1. Another prominent member of the $Q^{+}$-class is the Hertzian
potential, $v(r)=\epsilon(1-r/a)^{5/2}\Theta(1-r/a)$, which models the
effective interaction between elastic spheres of diameter $a$ [8]. The general
features of the phase diagram of the Hertzian spheres are similar to those of
the GCM, however, it must be emphasized that the former has finite support, as
expressed by the Heaviside function $\Theta(1-r/a)$, whereas the GCM is
nonvanishing for arbitrarily large values of $r$.

At low densities, the GCM can be mapped onto an effective hard sphere
potential [7], and its crystallization properties can be understood in such a
context. The high-density part of the phase behavior of the GCM is more
challenging. Previous studies [29, 30] have shown that at high densities
nucleation is strongly suppressed and that Mode-Coupling Theory (MCT) provides
an accurate description of the structural arrest of the GCM into an amorphous,
glassy state. Moreover, it was found that the glass state at high densities
displays strong dynamic fluctuations and a nearly Gaussian distribution of
single particle displacements, features compatible with a geometric transition
[31]. Such transition refers to a change in the topology of the rugged free
energy landscape; in particular, below the transition temperature, the
potential energy barriers become much larger than the available thermal
energy, and the system is trapped close to local minima of the energy
landscape [32].

The low- and intermediate-density glassy regimes of the GCM remain largely
unexplored. Assuming that the low-density vitrification scenario follows the
hard-sphere paradigm, it is then particularly interesting to ask the question
as to how the vitrification scenario evolves towards the high-density regime
and whether dynamically distinct glassy states exist in different density
regimes of the GCM. A recent theoretical study [33] showed an unexpected
density dependence of the glassy behavior of GCM particles, see Fig. 1).
Similarly to the equilibrium crystallization behavior, the glass line shows a
re-entrance upon increasing the density. However, at moderate densities, the
characteristic order parameter at constant density displays sudden jumps when
increasing the temperature. This trend suggests a transition between two
different glasses, a continuous and a discretized one. In particular, the
emergence of a discretized glass has been associated with the formation of
_out-of-equilibrium_ local aggregates. Indeed, as mentioned above, the GCM is
a $Q^{+}$ potential for which no clusters form at equilibrium. In contrast,
for ultrasoft particles belonging to the $Q^{\pm}$ class for which cluster
formation is an equilibrium phenomenon, the emergence of cluster-glasses has
been recently reported [34, 35, 36, 37]. We note that in Fig. 1, the MCT-
vitrification line stops at $\rho\gtrsim 0.40$ and at about the same density
the RT-vitrification line shows non-monotonic behavior with density. The
reason for the former is a loss of the HNC solution for the one-component CGM,
which is however recovered at much higher densities, $\rho\gtrsim 1.00$. The
RT, being a two-component approach, does converge in this region and results
in the aforementioned non-monotonic behavior. Whereas it is an open question
whether this behavior is connected with the convergence problems of the HNC in
that region, the discretized glass predicted by the RT occurs already at lower
densities, and thus the question of whether a distinct arrested state exists
there is independent of the HNC-convergence issues.

Figure 1: Phase diagram of the GCM. The black solidification line and the red
glass line from the Replica Theory (RT) are taken from the literature, in
particular from Refs. [28] and [33], respectively. The blue glass line is
calculated from Mode Coupling Theory (MCT) as described in Materials and
Methods. The MCT line is recovered at densities $\rho\gtrsim 1.00$, where it
follows a monotonically decreasing trend with density [29, 30]; see main text.

The goal of this work is to characterize the transition from low- to high-
density glass from a dynamic point of view, focusing on the study of the
supercooled regime. Indeed, when approaching the glass transition the system
enters into a supercooled regime which represents in all respects a precursor
of the glass [38]. Thus, we expect to observe differences between the two
states already at the level of supercooled (glassy) dynamics. The supercooled
regime of canonical glass-formers is usually described in terms of the
_caging_ mechanism: each particle experiences trapping due to the neighboring
particles that effectively create a cage around it; eventually, the
fluctuations allow the particle to escape this local cage and move to the next
one. The lower the temperature the more difficult it will be for the particle
to escape from the cage. In these terms, the glass transition can be thought
of as a localization transition. The cage size is related to the average
inter-particle distance, which in turn depends on the density of the system.
Such a mechanism is accurate for systems characterized by a harshly repulsive
inter-particle potential, such as hard-sphere or Lennard-Jones systems [39,
40]. However, when dealing with bonded potentials, that is with potentials
that do not diverge when two particles are at full overlap, and in the
presence of long tails, this mechanism can break down. In particular, we show
that for the GCM at intermediate densities, the idea of slow dynamics based on
the concept of _caging_ must be revised.

## Results

Following the phase diagram in Fig. 1, we simulate the glassy dynamics of the
GCM at different densities. As mentioned above, at high densities the one-
component GCM vitrifies and thus, it is possible to approach the supercooled
regime directly, without running into crystallization issues. This is not the
case for low and intermediate densities, for which the one-component system
would crystallize upon cooling. Therefore, in our simulations, we follow a
random pinning procedure and freeze a fraction $f=10\%$ of the particles in
order to avoid crystallization and be able to approach the deep supercooled
regime. All results reported below are calculated taking into account the
mobile particles only and averaged over at least three different realizations
of the pinning disorder (see Materials and Methods for more details on the
simulation protocol).

Figure 2: (a) main plot: the mean squared displacement
$\langle\Delta\bm{r}^{2}(t)\rangle$ of the GCM as a function of time,
calculated at four different isodiffusive points, as indicated in the legend.
Inset: corresponding local exponent $\gamma(t)$ of the MSD as defined in (5).
(b) structure factors $S(q)$ calculated at the same isodiffusive points as
panel (a); in the horizontal axis, the wavenumbers $q$ of each structure
factor are rescaled over the value related to the corresponding first peak
($q_{\mathrm{peak}}$).

We focus our analysis on four different densities, _i.e._ ,
$\rho=0.10,0.15,0.40,1.00$, in order to characterize the transition between
low- and high-density glassy dynamics. For each density, we spanned over
different temperatures and selected those at which all four systems display
the same diffusivity at long times. The motivation behind this choice of
isodiffusivity points has different motivations: on the one hand, the
isodiffusivity is accompanied by close similarities of the static
correlations: not only do the iso-peak-height lines of the radial distribution
functions follow similar trends as the isodiffusivity ones [41, 42] but, but
upon proper length rescaling, the static structure factors along such lines
can be mapped onto a quasi-universal curve as well, as we will shortly
demonstrate. On the other, the isodiffusivity lines are precursors of the
vitrification line [19]. Accordingly, by choosing to simulate along such a
locus we are lying on an equidistant line from the neighboring dynamically
arrested states of the system. To this end, we calculated the mean-square
displacements (MSD) as

$\langle\Delta\bm{r}^{2}(t)\rangle=\frac{1}{N}\left\langle\sum_{i=1}^{N}(\bm{r}_{i}(t+t_{0})-\bm{r}_{i}(t_{0}))^{2}\right\rangle,$
(2)

where $N$ is the particle number and the brackets $\langle\cdots\rangle$
denote an average over all particles, with initial positions
$\bm{r}_{i}(t_{0})$ at time $t_{0}$ and $\bm{r}_{i}(t+t_{0})$ at a time
interval $t$ later. We also average over different initial times $t_{0}$.

The selected temperature values are reported in Fig. 2(a), in which the mean-
squared displacement (MSD) is plotted, clearly showing the same long-time
diffusivity for the four systems. We have also calculated the equal-time
static structure factor

$S(\bm{q})=\frac{1}{N}\left\langle\sum_{i=1}^{N}\sum_{j=1}^{N}\exp\left[{-{\mathrm{i}}\bm{q}\cdot\left(\bm{r}_{i}(t)-\bm{r}_{j}(t)\right)}\right]\right\rangle,$
(3)

which is shown in Fig. 2(b). After suitable rescaling due to the different
densities, the overall structural properties of the four systems are
comparable. Thermodynamic states along the isodiffusivity lines can be mapped
on each other as far as the static correlations are concerned; the
corresponding low- and high-density states lying on an isotherm can be termed
conjuguate pairs, in analogy to the $T=0$ pairs of states that are coupled by
exact duality relations [43]. This property, together with the same long-time
diffusivity, would suggest that a re-mapping of all systems is possible and
that also the particle dynamics of the associated systems can be collapsed
onto a single curve upon suitable rescalings. This, however, is not the case.

We consider next the intermediate scattering function (ISF), defined as

$F_{s}(q,t)=\frac{1}{N}\left\langle\sum_{j=1}^{N}\exp\left[-{\mathrm{i}}\bm{q}\cdot(\bm{r}_{j}(t+t_{0})-\bm{r}_{j}(t_{0}))\right]\right\rangle,$
(4)

which is reported in Fig. 3, revealing important differences in the relaxation
dynamics. In particular, at the two lower densities, a clear two-step
relaxation can be discerned, which becomes smoothed out at the intermediate
one and practically disappears at the highest of the four, indicating the lack
of a caging mechanism for the latter. Therefore, the ISF displays a faster
relaxation for high density, while for low and intermediate densities the two-
step behavior emerges, leading to an effectively slower relaxation. The
coherent part of the ISF displays a similar trend, with no indication of
decoupling between self and collective behaviour, at least in the regime
investigated within this work. There is, therefore, one single relaxation time
associated with both the incoherent and the coherent intermediate scattering
functions and not two separate ones, as is the case with other single-
component ultrasoft systems, such as semiflexible minirings [44].

The aforementioned differences between low- and intermediate densities can
already be noticed in Fig. 2(a) for the behavior of the MSD at times between
the ballistic and diffusive regimes. For the lower densities, a much stronger
caging effect, indicated by the development of a plateau in the MSD, emerges
than for the higher ones. It is worth mentioning that the lack of a plateau at
the higher density precisely compensates the fact that the ballistic motion is
faster for the lower densities, so that when the former can enter a plateau
while the motion at the higher density catches up. Consequently, all MSD’s
enter their diffusive regime at the same distance squared and at the same
time, following thereafter the same diffusive pattern. These differences
become quantitative by considering the local exponent $\gamma(t)$ of the MSD,
defined as

$\gamma(t)=\frac{{\mathrm{d}}\ln\langle\Delta\bm{r}^{2}(t)\rangle}{{\mathrm{d}}\ln
t},$ (5)

and shown in the inset of Fig. 2(a). Whereas the local exponents for the two
lowest densities show a clear transition from ballistic ($\gamma(t)=2$) to a
diffusive ($\gamma(t)=1$) regimes through an intermediate plateau
($\gamma(t)\cong 0$), both the ballistic regime and the clear intermediate
plateau disappear at the high-density part of the isodiffusivity line. This is
a clear indication that at short-to-intermediate scales, the two motions
differ, a prediction to be quantified and analyzed below by statistically
analyzing individual particle trajectories.

In Fig. 4 we report typical single-particle displacements, $\Delta
r_{i}(t)=\sqrt{|\bm{r}_{i}(t)-\bm{r}_{i}(t_{0})|^{2}}$. By looking at the left
panels of Fig. 4 it is clear that the dynamics shifts from an intermittent-
like behavior at low densities to a more continuous one at high densities. In
order to classify this transition we make use of an analysis recently
developed to unravel intermittent features in single-particle trajectories and
based on a Local Convex Hull (LCH) method [45].

Figure 3: The self-intermediate scattering function
$F_{s}(q_{\mathrm{peak}},t)$ for the four different iso-diffusive points,
evaluated at the corresponding wavenumber $q_{\mathrm{peak}}$ where the
structure factor of each system has its main peak.

The main idea behind this analysis is to use geometric properties of the
smallest convex shape (precisely the LCH) enclosing a small set of trajectory
points to estimate the space explored by each particle in a specific time
window (see Fig. 5). More specifically, our analysis focuses on the study of
the LCH volume $S_{V}(t)$ which, as mentioned in [45], with respect to other
geometric quantities such as the diameter, is more sensitive to changes in the
dimensionality and anisotropy of the particle motion. In Fig. 4, together with
the single-particle displacements, we report also the corresponding time
series $S_{V}(t)$ calculated from the LCH method as described in Materials and
Methods. We can observe that, if the particle motion has an intermittent-like
behaviour, $S_{V}(t)$ will display few and high peaks, while, if the particle
motion follows a more continuous trend, $S_{V}(t)$ will mostly oscillate
around its single-particle average value $\overline{S_{V}}$ with multiple
lower peaks. Such trend suggests that performing a statistical analysis of the
$S_{V}(t)$ peaks can help in classifying different dynamical behaviors. Then,
for each time series we find the peak locations and corresponding peak values
$S_{V}^{*}$. Moreover, we identify with $\Delta t_{\mathrm{SP}}$ the duration
of the so called _slow phases_ , that is the time $S_{V}(t)$ stays below the
threshold $\overline{S_{V}}$ before crossing it.

Figure 4: Typical single-particle displacements (left column) and
corresponding $S_{V}(t)$ time series from the LCH analysis (right column)
calculated as described in Materials and Methods. The black solid line
indicates the threshold dividing slow and fast phases and is calculated as the
average over the the whole time series $S_{V}(t)$, that is $\overline{S_{V}}$.

In Fig. 6 we report the probability distribution of $\Delta t_{\mathrm{SP}}$,
of the peak height evaluated from the threshold value (_e.g._
$S_{V}^{*}-\overline{S_{V}}$) and of the number of peaks. We can see
immediately that $p(\Delta t_{\mathrm{SP}})$ classifies the systems into two
different dynamics: the distribution presents a fatter tail for the two lower
density systems with respect to the higher-density systems. In addition, by
looking at $p(S_{V}^{*}-\overline{S_{V}})$ we observe that the peak height is
more likely to assume larger values for the lower density systems than for the
higher density ones. However, in this case, there is not a full rescale of the
high-density systems, suggesting that $\rho=0.40$ still belongs to a
transition phase between the two dynamical regimes. We emphasize that the
quantity $p(S_{V}^{*}-\overline{S_{V}})$ has been rescaled by the average
value $\langle\overline{S_{V}}\rangle$ in order to eliminate trivial
contributions stemming from the density-dependence of the volume explored by
each particle (see also Fig. 7).

Figure 5: Single-particle trajectory and corresponding LCHs calculated for two
sets of points centered in different time instants (red points). The volume of
the LCH in (a) is clearly smaller than the one in (b), suggesting that a jump
between two local cages can be identified as a peak in the time series of
$S_{V}(t)$ as it is visible in Fig. 4.

Finally, the distribution of the number of peaks $p(\\#S_{V}^{*})$ complements
the information provided by $p(\Delta t_{\mathrm{SP}})$ suggesting an
intermittent-like motion when fewer peaks (and longer slow phases) are
detected and a more continuous one when a larger number of peaks (and shorter
slow phases) is observed. Indeed, $p(\\#S_{V}^{*})$ shows that the system with
the highest density is shifted towards larger values with respect to the two
systems with lower values, which follow a similar distribution centered around
smaller values; once again, the system with $\rho=0.40$ displays an
intermediate behavior confirming that at this density the system is in a
transition phase between the two dynamical regimes.

Figure 6: Probability distribution of (a) slow phase duration $\Delta
t_{\mathrm{SP}}$, (b) peak height $S_{v}^{*}$ with respect to the threshold
value $\overline{S_{V}}$ and (c) number of peaks. The distribution in (b) is
rescaled by the average value $\langle\overline{S_{V}}\rangle$ which clearly
depends on the density (see Fig. 7).

We further investigate the particle-to-particle variability of the threshold
value $\overline{S_{V}}$, which indicates the average volume explored by each
particle within the simulation time window. To do so, we extract the value
$\overline{S_{V}}$ for each (mobile) particle and then build the histogram, as
reported in Fig. 7. It can be seen that the distribution $p(\overline{S_{V}})$
looks quite narrow for the highest density, suggesting a more homogeneous
dynamics. Conversely, $p(\overline{S_{V}})$ for the lower density is much
broader, implying the presence of slow and fast particles in agreement with
the concept of dynamic heterogeneity typical of canonical supercooled liquids.
Of particular importance is the fact that in this case, the distribution has
contributions even at $\overline{S_{V}}=0$, suggesting that, within our time
window, there are particles that do not move at all (or only very little) from
their initial cage, for the lower densities, whereas this is not the case for
the higher densities, for which the distribution vanishes for small values of
$\overline{S_{V}}$.

Figure 7: Probability distribution of $\overline{S_{V}}$ obtained by
considering all the values extracted from each single-particle trajectory as
indicated in Materials and Methods.

Additional corroboration for the gradual disappearing of the standard cage-
escape mechanism of relaxation for the supercooled GCM-liquid at intermediate
densities is offered by considering the single-particle displacement
distribution $P(\Delta r,t)$ and the corresponding non-Gaussian parameter
$\alpha_{2}(t)=3\langle\Delta r^{4}(t)\rangle/5[\langle\Delta
r^{2}(t)\rangle]^{2}-1$, which is used to quantify the deviation of particles
displacements from a Gaussian distribution. Deviations of this quantity from
zero are usually attributed to the presence of dynamic heterogeneity in the
system but it has been shown, precisely in the context of the high-density
GCM, that small values of $\alpha_{2}(t)$ are compatible with strong dynamical
heterogeneities in the case of a mean-field, geometric glass transition [31].
In Fig. 9 we show the calculated non-Gaussian parameter for the four
isodiffusivity state points, finding that those of the low-density points
differ drastically from those of the high-density points. In particular, there
is a non-monotonic behavior of the curves and of their maximum values, which
occurs roughly at the end of the caging time for $\rho=0.10$ and $\rho=0.15$
and somewhat earlier for $\rho=0.40$ and $\rho=1.00$. Thus, $\alpha_{2}(t)$
follows the same trend in density as the iso-diffusivity line and other
quantities characterizing the system, see Fig. 1 and Refs. [4, 41, 46].
Single-particle motions tend thus to become more and more Gaussian as the
density grows, in agreement with the absence of a bimodal (cage/cage escape
jump) distribution of the self-van Hove function [31] and thus with the
gradual disappearance of the cage-hopping dynamics characteristic of the low-
density supercooled GCM fluid. In fact, we explicitly confirm the suppression
of hopping dynamics at intermediate and higher densities along our
isodiffusivity line in Fig. 8, demonstrating indeed that the standard caging
mechanism of dynamic slowing down in the supercooled liquid is valid only on
the low-density side of the vitrification line.

Figure 8: Evolution in time of the single-particle displacement distributions
for the four isodiffusivity state points: (a) $t=10^{2}$, (b) $t=10^{3}$, (c)
$t=10^{4}$, (d) $t=10^{5}$. In particular, we calculated the probability
distributions of the logarithm of single-particle displacements which allow us
to highlight the hopping motion, when present. Indeed, in panel (c) we can
clearly see the emergence of a bimodal distribution for all but the highest
density system. Figure 9: The non-Gaussian parameter $\alpha_{2}(t)$ of the
GCM-supercooled fluids at the four isodiffusivity state points considered.

Finally, in Fig. 10 we report the non-ergodicity factor calculated within the
MCT framework. As $T$ decreases, the low-density curves tend to behave
similarly; the same happens for the high-density graphs. However, comparing at
the same temperature, the non-ergodicity factors show notorious differences,
particularly for $q\to 0$, suggesting that as $\rho$ grows and the system is
getting more and more incompressible, the density modulations of very long
wavelengths ($q\to 0$) are more and more difficult to become arrested, leading
eventually to a different a scenario of dynamic arrest, which is much closer
to the ideal MCT-picture and it features long-wavelength mobility modulations
instead [29, 30, 31].

Figure 10: Non-ergodicity factor $\phi(q)$ obtained from MCT (see Materials
and Methods). We compare same temperatures at low density (orange curves) and
intermediate density (red curves).

## Discussion and Conclusions

The intermittent dynamics identified for the low-density GCM in the
supercooled regime confirms the picture provided by the hard-sphere re-
mapping, which appears to remain valid also for the glassy regime. Indeed, in
this regime, the GCM displays a glassy behavior that is in agreement with the
one of canonical HS-like glass formers. In particular, the dynamics is fully
described by the hopping between local cages leading to standard features such
as the emergence of the plateau in the MSD, dynamical heterogeneity, and non-
Gaussianity. All these features have been re-classified in this work by making
use of the LCH analysis. Upon increasing the density, the GCM undergoes a
transition towards a different glassy state. The intermittent-like behavior is
taken over by a more continuous more Gaussian dynamics. Our analysis shows how
the slowing down at high densities of the GCM cannot be explained using the
standard caging mechanism. As a matter of fact, the higher the density the
less confining the potential becomes due to the increasing contribution of
neighbouring particles to the energy landscape. The dynamics in this regime
approaches more and more a mean-field-like picture, as already anticipated in
[31]. With our single-particle analysis, we were able to fully capture the
transition between these 2 glassy states (HS-like at low densities and mean-
field-like at high densities) and to show how the intermediate density regime
is characterized by a smooth transition between the two dynamics. Whether this
transition in the supercooled fluid regime is the echo of an underlying glass-
glass transition between two arrested states, akin to the distinct glassy
states encountered, e.g., in colloid-polymer mixtures [47], is an open problem
and it will be the subject of further investigations.

## Materials and Methods

### Molecular Dynamics simulations

Molecular dynamics (MD) simulations were performed using the open-source
package LAMMPS [48] for a cubic box with periodic boundary conditions and
several combinations of density $\rho=N/V$ and temperature $T$, where $N$ and
$V$ are the total number of Gaussian particles and the volume of the box,
respectively. The equations of motion were integrated using the velocity
Verlet scheme [49], with a time step $\Delta t/\tau=0.01$, where
$\tau=\sqrt{m\sigma^{2}/\epsilon}$ and $m$ the mass unit for the particles.

Due to the propensity of the system to crystallize at low temperatures, it is
required to add some frustration degree into the system, which helps particles
to remain in a disordered phase as temperature decreases. In this work,
frustration is introduced through random pinning that avoids the inclusion of
randomness in the interaction potential or compositional disorder [50, 51].

The initial configuration of the system was generated in a multiple steps
process: at first, $N_{p}=\lfloor fN\rfloor$ particles were randomly placed in
the simulation box and an equilibration process took place at a relatively
high temperature ($T=0.01$). Then they were permanently pinned and the
remaining $N_{m}=N-N_{p}$ particles (the mobile ones) were randomly inserted
in the box preventing excessive overlapping with the previously inserted
particles. By setting the target temperature $T$, an equilibration run was
performed for the mobile particles in which the system was thermalized by
means of the Nose-Hoover thermostat. To consider the effect of the pinning
protocol, a second pinning method was also employed. In that case, the whole
system is equilibrated at a high temperature, then the fraction $f$ of
particles is permanently frozen and the system is lastly quenched to the
target temperature for the equilibration of the mobile particles to occur.

We worked with a total number of particles $N=3456$, or $5000$, and $f=0.05$
or $0.10$. The typical equilibration time for the mobile particles ranged from
$2\times 10^{6}$ to $10^{7}$ time steps. After reaching a steady state,
indicated by the absence of any drift in internal energy and pressure, a
production run was performed, which typically ranged from $10^{7}$ to $10^{8}$
time steps.

By providing that all average measurements for given density and temperature
are performed over both thermal fluctuations and different realizations of the
pinning disorder, it is expected that the thermodynamics of the mobile
particles remains unperturbed [50].

### Local convex hull analysis

To differentiate between different diffusive phases we analyse the single-
particle trajectories making use of the Local Convex Hull (LCH) method
developed in [45]. The convex hull of a finite set of points
$\\{\mathbf{x}_{1},\dots,\mathbf{x}_{n}\\}\subset\mathbb{R}^{d}$ is the
minimal convex shape that encloses all the points
$\mathbf{x}_{1},\dots,\mathbf{x}_{n}$. We consider the volume $Q_{V}(i)$ of
the LCH computed over $2\tau_{0}+1$ trajectory points centered around
$\mathbf{x}_{i}$. Then, we classify the point $\mathbf{x}_{i}$ by using all
the estimators to which it contributes (in total $2\tau_{0}+1$), that is by
introducing the discriminator:

$S_{V}(i)=\frac{1}{2\tau_{0}+1}\sum_{k=i-\tau_{0}}^{k=i+\tau_{0}}Q_{V}(k).$
(6)

The LCH method consists in: 1) mapping each trajectory into a one-dimensional
time series by computing the discriminator $S_{V}(n)$ for all points
$\mathbf{x}_{n}$; and 2) selecting a threshold $S_{V}$ such that the points
$\mathbf{x}_{i}$ with $S_{V}(i)>S_{V}$ are classified into the _fast_ phase
whereas the points $\mathbf{x}_{i}$ with $S_{V}(i)\leq S_{V}$ into the _slow_
phase. Following Ref. [45], we set the threshold $S_{V}$ to be the average
value of $S_{V}(n)$ over the single trajectory, namely

$S_{V}\equiv\overline{S_{V}}=\frac{1}{N-4\tau_{0}}\sum_{n=2\tau_{0}+1}^{n=N-2\tau_{0}}S_{V}(n).$
(7)

The parameter $\tau_{0}$ was chosen empirically by looking at the MSD curves
and selecting the time at which the system escapes from the plateau, generally
used as an estimate of the caging time. For our system in particular we have
$\tau_{0}=10^{3}$ (in simulation time units). To calculate the LCH, we used
the available algorithm in Python based on the Qhull library.

### Mode Coupling Theory

To quantify the liquid-to-glass transition of the GCM system, the non-
ergodicity factor $\phi(q)$ was evaluated, which is defined as the long-time
limit of the density autocorrelation function, i.e.,

$\phi(q)=\lim_{t\to\infty}F(q,t)=\lim_{t\to\infty}\frac{\langle\rho({\bf
q},t)\rho(-{\bf q},0)\rangle}{\langle\rho({\bf q},0)\rho(-{\bf q},0)\rangle},$
(8)

where $\rho({\bf q},t)=\sum_{j=1}^{N}\exp[{\mathrm{i}}{\bf q}\cdot{\bf
r}_{j}(t)]$ and the sum is performed over the coordinates ${\bf r}_{j}(t)$ of
all particles in the system.

In the case $\phi(q)\neq 0$, the system is considered non-ergodic and its
state is identified as glassy, whereas $\phi(q)=0$ corresponds to an ergodic
fluid. Given the structural data obtained by solving the Ornstein-Zernike
equation through the hypernetted-chain closure (HNC), the calculation of the
non-ergodicity factor is readily achieved within the framework of the Mode
Coupling Theory (MCT). According to it, $\phi(q)$ fulfills the self-consistent
equation [52]:

$\frac{\phi(q)}{1-\phi(q)}=\frac{1}{(2\pi)^{3}}\int{\rm
d}^{3}k\,\mathcal{V}(\mathbf{q},\mathbf{k})\phi(k)\phi(k^{\prime}),$ (9)

where $\mathbf{k}^{\prime}=\mathbf{q}-\mathbf{k}$ and the kernel
$\mathcal{V}(\mathbf{q},\mathbf{k})$ can be expressed entirely in terms of the
Fourier transform of direct correlation function $\hat{c}(k)$, i.e.,

$\mathcal{V}(\mathbf{q},\mathbf{k})=\frac{\rho
S(q)}{2q^{4}}\left[(\mathbf{q}\cdot\mathbf{k}^{\prime})\,\hat{c}(k^{\prime})+(\mathbf{q}\cdot\mathbf{k})\,\hat{c}(k)\right]^{2}S(k)S(k^{\prime}),$
(10)

and $S(k)=\left[1-\rho\,\hat{c}(k)\right]^{-1}$.

###### Acknowledgements.

We thank S. Prestipino for providing the data from Ref. [28] shown in Fig. 1
and E. Zaccarelli for helpful discussions. V.S. acknowledges support of the
European Commission through the Marie Skłodowska-Curie COFUND project REWIRE,
Grant Agreement No. 847693. M.C. thanks Universidad Antonio Nariño for
financial support through Project No 2022202.

## References

  * Vlassopoulos and Cloître [2014] D. Vlassopoulos and M. Cloître, Tunable rheology of dense soft deformable colloids, Curr. Opin. Colloid Interface Sci. 19, 561 (2014).
  * Riest  _et al._ [2015] J. Riest, L. Athanassopoulou, S. A. Egorov, C. N. Likos, and P. Ziherl, Elasticity of polymeric nanocolloidal particles, Sci. Rep. 5, 15854 (2015).
  * Watzlawek  _et al._ [1998] M. Watzlawek, H. Löwen, and C. N. Likos, The anomalous structure factor of dense star polymer solutions, J. Phys.: Condens. Matter 10, 8189 (1998).
  * Krekelberg  _et al._ [2009] W. P. Krekelberg, T. Kumar, J. Mittal, J. R. Errington, and T. M. Truskett, Amonalous structure and dynamics of the gaussian-core fluid, Phys. Rev. E 79, 031203 (2009).
  * Pond  _et al._ [2011a] M. J. Pond, J. R. Errington, and T. M. Truskett, Communication: Generalizing rosenfeld’s excess-entropy scaling to predict long- time diffusivity in dense fluids of brownian particles: From hard to ultrasoft interactions, J. Chem. Phys. 134, 081101 (2011a).
  * Pond  _et al._ [2011b] M. J. Pond, J. R. Errington, and T. M. Truskett, Mapping between long-time molecular and brownian dynamics, Soft Matter 7, 9859 (2011b).
  * Stillinger [1976] F. H. Stillinger, Phase transitions in the Gaussian core system, J. Chem. Phys. 65, 3968 (1976).
  * Pamies  _et al._ [2009] J. C. Pamies, A. Cacciuto, and D. Frenkel, Phase diagram of Hertzian spheres, J. Chem. Phys. 131, 044514 (2009).
  * Berthier  _et al._ [2010] L. Berthier, A. J. Moreno, and G. Szamel, Increasing the density melts ultrasoft colloidal glasses, Phys. Rev. E 82, 060501 (2010).
  * Gnan and Zaccarelli [2019] N. Gnan and E. Zaccarelli, The microscopic role of deformation in the dynamics of soft colloids, Nat. Phys. 15, 683 (2019).
  * Parisi  _et al._ [2023] D. Parisi, D. Truzzolillo, A. H. Slim, P. Dieudonné-George, S. Narayanan, J. C. Conrad, V. D. Deepak, M. Gauthier, D. V. J. C. Conrad, V. D. Deepak, M. Gauthier, and D. Vlassopoulos, Gelation and re-entrance in mixtures of soft colloids and linear polymers of equal size, Macromolecules 56, 1818 (2023).
  * Lenz  _et al._ [2012] D. Lenz, R. Blaak, C. N. Likos, and B. M. Mladek, Microscopically resolved simulations prove the existence of soft cluster crystals, Phys. Rev. Lett. 109, 228301 (2012).
  * Stiakakis  _et al._ [2021] E. Stiakakis, N. Jung, N. Adžić, T. Balandin, E. Kentzinger, U. Rücker, R. Biehl, J. Dhont, U. Jonas, and C. N. Likos, Self assembling cluster crystals from DNA based dendritic nanostructures, Nat. Commun. 12, 7167 (2021).
  * Smith  _et al._ [1999] D. E. Smith, H. P. Babcock, and S. Chu, Single-polymer dynamics in steady shear flow, Science 283, 1724 (1999).
  * LeDuc  _et al._ [1999] P. LeDuc, C. Haber, G. Bao, and D. Wirtz, Dynamics of individual flexible polymers in a shear flow, Nature 399, 564 (1999).
  * Gerashchenko and Steinberg [2006] S. Gerashchenko and V. Steinberg, Statistics of tumbling of a single polymer molecule in shear flow, Phys. Rev. Lett. 96, 038304 (2006).
  * Ripoll  _et al._ [2006] M. Ripoll, R. Winkler, and G. Gompper, Star polymers in shear flow, Phys. Rev. Lett. 96, 188302 (2006).
  * Huang  _et al._ [2010] C. C. Huang, R. G. Winkler, G. Sutmann, and G. Gompper, Semidilute polymer solutions at equilibrium and under shear flow, Macromolecules 43, 10107 (2010), arXiv:1103.3573 .
  * Foffi  _et al._ [2003] G. Foffi, F. Sciortino, P. Tartaglia, E. Zaccarelli, F. L. Verso, L. Reatto, K. Dawson, and C. N. Likos, Structural arrest in dense star polymer solutions, Phys. Rev. Lett. 90, 238301 (2003).
  * Mayer  _et al._ [2008] C. Mayer, E. Zaccarelli, E. Stiakakis, C. N. Likos, F. Sciortino, A. Munam, M. Gauthier, N. Hadjichristidis, H. Iatrou, P. Tartaglia, H. Löwen, and D. Vlassopoulos, Asymmetric caging in soft colloidal mixtures, Nat. Mater. 7, 780 (2008).
  * Mattson  _et al._ [2009] J. Mattson, H. M. Wyss, A. Fernandez-Nieves, K. Miyazaki, Z. Hu, D. R. Reichman, and D. A. Weitz, Soft colloids make strong glasses, Nature 462, 83 (2009).
  * Philippe  _et al._ [2018] A.-M. Philippe, D. Trzzzolillo, J. Galvan-Myoshi, P. Dieudonné-George, V. Trappe, L. Berthier, and L. Cipelletti, Glass transition of soft colloids, Phys. Rev. E 97, 040601(R) (2018).
  * Gupta  _et al._ [2015] S. Gupta, J. Stellbrink, E. Zaccarelli, C. N. Likos, M. Camargo, P. Holmqvist, J. Allgaier, L. Willner, and D. Richter, Validity of the stokes-einstein relation in soft colloids up to the glass transition, Phys. Rev. Lett. 115, 128302 (2015).
  * Likos  _et al._ [2001] C. N. Likos, A. Lang, M. Watzlawek, and H. Löwen, Criterion for determining clustering versus reentrant melting behavior for bounded interaction potentials, Phys. Rev. E 63, 031206 (2001).
  * Louis  _et al._ [2000] A. A. Louis, P. G. Bolhuis, J. P. Hansen, and E. J. Meijer, Can polymer coils be modeled as ”soft colloids”?, Phys. Rev. Lett. 85, 2522 (2000).
  * Götze  _et al._ [2004] I. O. Götze, H. M. Harreis, and C. N. Likos, Tunable effective interactions between dendritic macromolecules, J. Chem. Phys. 120, 7761 (2004).
  * Lang  _et al._ [2000] A. Lang, C. N. Likos, M. Watzlawek, and H. Löwen, Fluid and solid phases of the Gaussian core model, J. Phys.: Condens. Matter 12, 5087 (2000).
  * Prestipino  _et al._ [2005] S. Prestipino, F. Saija, and P. V. Giaquinta, Phase diagram of the Gaussian-core model, Phys. Rev. E 71, 050102(R) (2005).
  * Ikeda and Miyazaki [2011a] A. Ikeda and K. Miyazaki, Glass transition of the monodisperse Gaussian core model, Phys. Rev. Lett. 106, 015701 (2011a).
  * Ikeda and Miyazaki [2011b] A. Ikeda and K. Miyazaki, Slow dynamics of the high density Gaussian core model, J. Chem. Phys. 135, 054901 (2011b).
  * Coslovich  _et al._ [2016] D. Coslovich, A. Ikeda, and K. Miyazaki, Mean-field dynamic criticality and geometric transition in the Gaussian core model, Phys. Rev. E 93, 042602 (2016).
  * Grigera  _et al._ [2002] T. S. Grigera, A. Cavagna, I. Giardina, and G. Parisi, Geometric approach to the dynamic glass transition, Phys. Rev. Lett. 88, 055502 (2002).
  * Bomont  _et al._ [2022] J.-M. Bomont, C. N. Likos, and J.-P. Hansen, Glass quantization of the Gaussian core model, Phys. Rev. E 105, 024607 (2022).
  * Coslovich  _et al._ [2012] D. Coslovich, M. Bernabei, and A. J. Moreno, Cluster glasses of ultrasoft particles, J. Chem. Phys. 137, 184904 (2012).
  * Coslovich and Ikeda [2013] D. Coslovich and A. Ikeda, Cluster and reentrant anomalies of nearly Gaussian core particles, Soft Matter 9, 6786 (2013).
  * Miyazaki  _et al._ [2016] R. Miyazaki, T. Kawasaki, and K. Miyazaki, Cluster glass transition of ultrasoft-potential fluids at high density, Phys. Rev. Lett. 117, 165701 (2016).
  * Miyazaki  _et al._ [2019] R. Miyazaki, T. Kawasaki, and K. Miyazaki, Slow dynamics coupled with cluster formation in ultrasoft-potential glasses, J. Chem. Phys. 150, 074503 (2019).
  * Berthier and Biroli [2011] L. Berthier and G. Biroli, Theoretical perspective on the glass transition and amorphous materials, Rev. Mod. Phys. 83, 587 (2011).
  * Chaudhuri  _et al._ [2007] P. Chaudhuri, L. Berthier, and W. Kob, Universal nature of particle displacements close to glass and jamming transitions, Phys. Rev. Lett. 99, 060604 (2007).
  * Pastore  _et al._ [2015] R. Pastore, M. P. Ciamarra, G. Pesce, and A. Sasso, Connecting short and long time dynamics in hard-sphere-like colloidal glasses, Soft Matter 11, 622 (2015).
  * Mausbach and May [2006] P. Mausbach and H.-O. May, Static and dynamic anomaies in the gaussian core model liquid, Fluid Phase Equilib. 249, 17 (2006).
  * Wensink  _et al._ [2008] H. H. Wensink, H. Löwen, M. Rex, C. N. Likos, and S. van Teeffelen, Long-time self-diffusion for Brownian Gaussian-core particles, Comp. Phys. Commun. 179, 77 (2008).
  * Stillinger [1979] F. H. Stillinger, Duality relations for the Gaussian core model, Phys. Rev. B 20, 299 (1979).
  * Slimani  _et al._ [2014] M. Z. Slimani, P. Bacova, M. Bernabei, A. Narros, C. N. Likos, and A. J. Moreno, Cluster glasses of semiflexible ring polymers, ACS Macro Lett. 3, 611 (2014).
  * Lanoiselée and Grebenkov [2017] Y. Lanoiselée and D. S. Grebenkov, Unraveling intermittent features in single-particle trajectories by a local convex hull method, Phys. Rev. E 96, 022144 (2017).
  * Mausbach and May [2009] P. Mausbach and H.-O. May, Transport anomalies in the gaussian core model fluid, Z. Phys. Chem. 223, 1035 (2009).
  * Dawson  _et al._ [2000] K. Dawson, G. Foffi, M. Fuchs, W. Götze, F. Sciortino, M. Sperl, P. Tartaglia, T. Voigtmann, and E. Zaccarelli, Higher-order glass-transition singularities in colloidal systems with attractive interactions, Phys. Rev. E 63, 011401 (2000).
  * Thompson  _et al._ [2022] A. P. Thompson, H. M. Aktulga, R. Berger, D. S. Bolintineanu, W. M. Brown, P. S. Crozier, P. J. in’t Veld, A. Kohlmeyer, S. G. Moore, T. D. Nguyen, _et al._ , Lammps-a flexible simulation tool for particle-based materials modeling at the atomic, meso, and continuum scales, Comp. Phys. Commun. 271, 108171 (2022).
  * Frenkel and Smit [2000] D. Frenkel and B. Smit,  _Molecular Simulation: From Algorithms to Applications_ (Academic Press, New York, 2000).
  * Berthier and Kob [2012] L. Berthier and W. Kob, Static point-to-set correlations in glass-forming liquids, Phys. Rev. E 85, 011102 (2012).
  * Karmakar and Parisi [2013] S. Karmakar and G. Parisi, Random pinning glass model, Proc. Nat. Acad. Sci. U.S.A. 110, 2752 (2013).
  * Hansen and McDonald [2013] J.-P. Hansen and I. R. McDonald,  _Theory of Simple Liquids with Applications to Soft Matter_ , 4th ed. (Academic Press, Amsterdam, 2013).