# Convergence rate of the diagonal-valued Cauchy-transform for permutation invariant random matrices

Alexis Imbert

► To cite this version:

Alexis Imbert. Convergence rate of the diagonal-valued Cauchy-transform for permutation invariant random matrices. 2026. hal-05533012

HAL Id: hal-05533012

https://hal.science/hal-05533012v1

Preprint submitted on 2 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Convergence rate of the diagonal-valued
Cauchy-transform for permutation invariant random
matrices

Alexis Imbert *

March 2, 2026

Abstract

Let $A$ be a permutation invariant random matrix and $B$ another random matrix.
We give a quantitative bound on the difference between the diagonal of the resolvent
of $A+B$ and the diagonal of the resolvent of the free sum with amalgamation over
the diagonal of $A$ and $B$. Moreover, we improve the rate of convergence whenever the
matrices $A$ and $B$ are sparse and bounded in operator norm. Doing so, we explicitly
construct the free sum over the diagonal of $A$ and $B$ as an adjacency operator of a
weighted locally finite graph.

Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Statement of the main Theorem</td><td>4</td></tr><tr><td>2.1</td><td>Notions of diagonal-valued free probability</td><td>4</td></tr><tr><td>2.2</td><td>Main theorems and sketch of the proof</td><td>7</td></tr><tr><td>3</td><td>Explicit construction of the amalgamated free sum</td><td>8</td></tr><tr><td>4</td><td>Traffic notions and assumptions</td><td>12</td></tr><tr><td>4.1</td><td>Traffic notions</td><td>13</td></tr><tr><td>4.2</td><td>Assumption on the injective trace</td><td>16</td></tr><tr><td>4.3</td><td>Assumption on the Frobenius norm</td><td>19</td></tr></table>

<footnote>*Université de Bordeaux, Institut de Mathématiques de Bordeaux, 351 Cours de la Libération, 33400 Talence, France. Email: alexis.imbert@math.u-bordeaux.fr</footnote>
<table><tr><td>5 Proof of the main theorems</td><td>20</td></tr><tr><td>5.1 Preliminary results</td><td>20</td></tr><tr><td>5.2 Proof of Theorem 2.6</td><td>27</td></tr><tr><td>5.3 Proof of Theorem 2.7</td><td>29</td></tr><tr><td>A An asymptotic development</td><td>33</td></tr></table>

# 1 Introduction

Understanding the asymptotic spectrum of the sum of two random matrices is a classical problem in random matrix theory. From Voiculescu's pioneering work [21], we know that when one of the two matrices is invariant in law under conjugation by unitary matrices the two matrices are asymptotically free. In that scenario, provided the empirical spectral distribution (ESD) of the two matrices converge, the limiting measure of the sum is the free additive convolution of the marginal limiting measures. One of the main tool to prove this kind of convergence is the moment method which shows convergence of the Cauchy transform (or equivalently the normalized trace of the resolvent) toward some analytic function on the right domain. This proves in particular that the limit of the Cauchy transform is still the Cauchy transform of some measure that we can now characterize. Moreover, still in that scenario, provided some smoothness assumption on the limiting ESD and boundedness of the norm of the matrices, it has been shown that the convergence of the Cauchy transform of the sum toward its limit happens at speed $N^{-1}$ (where N is the size of the matrix). The first result was obtained by Chatterjee in [8] which was later improved by Kargin in [13] and [14]. These results show a convergence not only of the Cauchy transform but of the diagonal of the resolvent. In a series of following paper, Bao, Erdos and Schnelli [2, 3] proved that the optimal speed was $N^{-1}$ in the bulk of the limiting measure.

In this article, we are interested in a more general case: when one of the two matrices is invariant in law by conjugation by permutation matrices. In that scenario, provided that the matrices converge in traffic distribution and verify some factorization property Male [16] proved that the random matrices at stake are asymptotically traffic free. Moreover, it has been shown in [1] that permutation invariant random matrices are asymptotically free over the diagonal. The latter is a particular case of operator-valued freeness [17, 23, 19]. Therefore, the asymptotic joint traffic (resp. diagonal) distribution of the two matrices can be recovered just from their marginal traffic (resp. diagonal) distribution (see Definition 4.3 for more details). Then, if we are interested only in the asymptotic ESD of the sum, since the joint traffic and diagonal distribution encompass the joint *-distribution, it is enough to know the marginal asymptotic traffic or diagonal distributions. For a single permutation invariant random matrix, and in particular for adjacency matrix of random regular graphs, several work has been done in the recent years, see for instance [5, 4].

Let $X$ be a matrix of size $N$, and let $D$ be a diagonal matrix whose entries all have positive imaginary part. The diagonal-valued Cauchy-transform of $X$ is defined as
$G_X(D) := \Delta((D - X)^{-1})$ where for any matrix $M$, $\Delta(M) := (M_{i,j}\delta_{i,j})_{1\le i,j\le N}$. A more general definition is given in Section 2. One knows from the scalar case that it is customary to study the Cauchy transform of a measure to recover some information about it. The same goes for operator-valued Cauchy-transform (see [19, 23, 21]).

Provided $A$ and $B$ satisfy Assumptions 4.5 and 4.6 at speed $M$, Theorem 2.6 states that for $|z| > r$,

$$ \mathbb{E} \frac{1}{N} \| G_{A+B}(zI) - G_{a+b}(zI) \|_F^2 \le (r/|z|)^{2cM}, $$

where $r, c$ are some constant depending on the Assumptions on $A$ and $B$ and $a+b$ is the free sum over the diagonal of $A$ and $B$ explicitly constructed in Section 3. Note that $M$ is at most of order $\log N/\log \log N$ so that the rate of convergence is at most $N^{-\beta/\log \log N}$.

Assumption 4.5 controls the growth of traffic moments for graph monomials of size $M$ whereas Assumption 4.6 controls the Frobenius norm of the $M$-th power of $A$ and $B$ (or equivalently, their Schatten-$M$ norm), where $M$ goes to infinity with $N$ and is at most of order $\log N/\log \log N$.

Assumption 4.5 is satisfied for a wide range of matrix models such as the Wigner matrices, the heavy Wigner matrices that contain in particular the adjacency matrices of Erdos-Renyi graphs with parameter at least $d/N$ for some fixed $0 < d$ and sparse bounded matrices. Moreover, Assumption 4.5 is stable by entry-wise product, (see the last paragraph of Section 4.2). It can be thought in the following way, given a graph with at most $M$ vertices and edges, we control the number of injective maps sending this graph to the adjacency graph of the matrices $A$ and $B$.

However, Assumption 4.6 is more restrictive. Indeed, looking at adjacency matrices of Erdos-Renyi random graphs for instance, it applies only when the parameter $d$ also goes to infinity with $N$. Note however that it is more lenient than asking for the operator norm of the matrices to be uniformly bounded. Indeed, take again Erdos-Renyi graphs, when the parameter $d$ is of order smaller than $\log N$, it is shown in [7] that the operator norm of the adjacency matrix of Erdos-Renyi random graphs with such parameter goes to infinity with $N$. However, for $M$ small enough, that goes to infinity with $N$, Assumption 4.6 is verified for such a model. Similarly, for Heavy-Wigner matrices, if the (properly normalized) moment of order $k$ of the entries is not zero for $k \ge 3$ (see [24, 15]), Assumption 4.6 cannot be verified at any speed $M$, see Section 4.3. We therefore restrict ourselves with what we call diluted Wigner matrices, where the condition on the moments of the entries is stated in Equation (4.9).

Theorem 2.7 requires that the two matrices are uniformly sparse and bounded in operator norm, but controls the difference of the Cauchy-transform evaluated in any diagonal matrices and improves the rate of convergence to $N^{-\gamma}$ for some positive explicit constant $\gamma$. It can thus be applied to uniform $d$-regular graphs for $d$ bounded, continuing the work of [4] in the case of the addition of two such matrices. The case where matrices are both bounded in operator norm is easier to deal with because it allows us to control the rest of the series expansion of the resolvent. Note that it implies Assumption 4.6.

Both proofs rely on a moment method where Assumption 4.6, resp. the uniform bound in operator norm, allows us to control the rest in the series expansion of the resolvent for
Theorem 2.6, resp. Theorem 2.7.

**Organization of the paper** In Section 2, we introduce the necessary tools from operator-valued free probability so that we are able to state Theorem 2.6 and Theorem 2.7. In Section 3, we realize the free sum with amalgamation over the diagonal of A and B as an adjacency operator of a locally finite graph. Section 4 is dedicated to Assumptions 4.5 and 4.6 and to showing that many random matrix models verify those assumptions. In Section 5, we prove the two main theorems.

# 2 Statement of the main Theorem

In this section, we provide the necessary background in operator-valued free probability for us to be able to state our main theorems. We specifically give a construction of the free sum with amalgamation over the diagonal of two random matrices.

## 2.1 Notions of diagonal-valued free probability

We recall some basic notions of operator-valued free probability. One can look into [17, 19, 23] and the references therein for a more detailed introduction to operator-valued non commutative probabilities.

**Definition 2.1:** A $C^*$-operator-valued probability space is a triplet $(\mathcal{A}, \mathcal{B}, E)$ where $\mathcal{A}$ is a $C^*$-algebra, $\mathcal{B} \subset \mathcal{A}$ is a unital $C^*$-subalgebra of $\mathcal{A}$ and $E: \mathcal{A} \to \mathcal{B}$ is a completely positive, unital, linear map that satisfies the $\mathcal{B}$-bi-modularity condition: $E(b_1ab_2) = b_1E(a)b_2$ for all $b_1, b_2 \in \mathcal{B}$ and all $a \in \mathcal{A}$. The map $E$ is then called a conditional expectation.

We say that two elements $x, y \in \mathcal{A}$ are free over $\mathcal{B}$ (or $\mathcal{B}$-free, or free with amalgamation over $\mathcal{B}$) whenever the following statement holds. Let $\mathcal{A}_1 \subset \mathcal{A}$, (resp. $\mathcal{A}_2 \subset \mathcal{A}$) be the algebra generated by $x$ (resp. $y$) and $\mathcal{B}$. For all $n \ge 1$ and $a_1, \cdots, a_n$ such that they are

* Centered: for all $1 \le i \le n$, $E(a_i) = 0$,

* Alternating: for all $1 \le i \le n$, $a_i \in \mathcal{A}_{j_i}$ with $j_1 \neq j_2, \cdots, j_{n-1} \neq j_n$,

then

$$E(a_1a_2\cdots a_n) = 0.$$

Let $\mathcal{X}$ be a self-adjoint formal variable algebraically free from $\mathcal{B}$, we define $\mathcal{B}\langle\mathcal{X}\rangle$ as the $\mathcal{B}$-bimodule $\mathcal{X}$-algebra of non-commutative polynomials over $\mathcal{B}$, that is the linear span of monomials of the form $b_1\mathcal{X}b_2\mathcal{X}\cdots\mathcal{X}b_n$ with $b_i \in \mathcal{B}$ for $1 \le i \le n$, with $(b_1\mathcal{X}b_2\mathcal{X}\cdots\mathcal{X}b_n)^* = b_n^*\mathcal{X}b_{n-1}^*\mathcal{X}\cdots\mathcal{X}b_1^*.$
**Definition 2.2:** Let $a \in (\mathcal{A}, \mathcal{B}, E)$ as above. The $\mathcal{B}$-valued distribution (or $E$-distribution) of $a$ is the map

$$ \mu_a : \mathcal{B}\langle\mathcal{X}\rangle \to \mathcal{B} \\ P \mapsto E(P(a)) $$

where $P(a)$ refers to the evaluation map of the non-commutative polynomial $P(\mathcal{X}) \in \mathcal{B}\langle\mathcal{X}\rangle$.

We define an abstract set of distributions $\Sigma_0$ as the set of unital, positive $\mathcal{B}$-bimodular maps $\mu : \mathcal{B}\langle\mathcal{X}\rangle \to \mathcal{B}$, such that

1. For any $n \in \mathbb{N}$ and any non commutative polynomial $P_1(\mathcal{X}), \dots, P_n(\mathcal{X}) \in \mathcal{B}\langle\mathcal{X}\rangle$, we have $[\mu(P_i(\mathcal{X})^*P_j(\mathcal{X}))]_{1\le i,j\le n} \ge 0$ in $M_n(\mathcal{B})$,

2. There exists $M > 0$ such that for all $b_1, \dots, b_n \in \mathcal{B}$,

$$ ||\mu(b_0\mathcal{X}b_1 \cdots \mathcal{X}b_n)|| \le M^n ||b_0|| \cdots ||b_n||. $$

The norm above is the norm inherited from the $C^*$-algebra, which is the operator norm whenever one deals with random matrices.

It turns out that these two conditions characterize the $\mathcal{B}$-valued distribution of an element.

**Theorem 2.3** (Proposition 2.2 of [19]). Let $\mu$ be a positive unital $\mathcal{B}$-bimodular map that satisfies the first point above. It satisfies the second point if and only if there exists a $\mathcal{B}$-valued non-commutative probability space $(\mathcal{A}, \mathcal{B}, E)$ and a self-adjoint element $a \in \mathcal{A}$ such that $\mu = \mu_a$.

As in the scalar case, it is possible to define some analytic transforms associated to a distribution $\mu$. Every element $x \in \mathcal{A}$ can uniquely be written as $\mathrm{Re}(x) + i\mathrm{Im}(x)$, where $\mathrm{Re}(x) = \frac{x+x^*}{2}$ and $\mathrm{Im}(x) = \frac{x-x^*}{2i}$. We denote $\mathbb{H}^+(\mathcal{B}) := \{b \in \mathcal{B}, \mathrm{Im}(b) > 0\}$, where $y > 0$ stands for $y \ge 0$ and $y$ invertible or equivalently, $y \ge \varepsilon 1_\mathcal{A}$ for some strictly positive real number $\varepsilon$. Elements in $\mathbb{H}^+(\mathcal{B})$ are all invertible. Furthermore, for a self-adjoint element $x = x^*$ and an element $b \in \mathbb{H}^+(\mathcal{B})$, $b - x$ is still invertible. Hence, the operator upper half-plane $\mathbb{H}^+(\mathcal{B})$ is the appropriate domain to define the Cauchy transform of a self adjoint element $x = x^*$

Let $x$ be a self-adjoint element in an operator valued probability space $(\mathcal{A}, \mathcal{B}, E)$,

* The operator-valued Cauchy transform of $x$ is

$$ G_x(b) := E((b-x)^{-1}) = \mu_x((b-\mathcal{X})^{-1}). \qquad (2.1) $$

* The reciprocal Cauchy transform of $x$ is

$$ F_x(b) := G_x(b)^{-1}. \qquad (2.2) $$

It verifies $\mathrm{Im}(F_x(b)) \ge \mathrm{Im}(b)$ (see Remark 2.5 in [6]).
They are both well defined on $H^+(\mathcal{B})$ and $F_x$ takes values in $H^+(\mathcal{B})$. Note that they can be defined for an arbitrary measure $\mu \in \Sigma_0$ thanks to Theorem 2.3. It should also be noted that, unlike the scalar case, they do not characterize the distribution $\mu$. It is shown in the pioneering work of Voiculescu [22] that one needs more information to retrieve the distribution $\mu$, namely the fully matricial extension of the Cauchy transform. However, we do not need this here.

We also recall simple facts about the $\mathcal{B}$-valued free sum of two non commutative $\mathcal{B}$-valued variables $x$ and $y$ in a $C^*$ operator-valued non commutative probability space $(\mathcal{A}, \mathcal{B}, E)$. We denote $\mathcal{A}_1 = \mathcal{B}\langle\mathcal{X}\rangle$ (resp. $\mathcal{A}_2 = \mathcal{B}\langle\mathcal{Y}\rangle$) the algebra generated by $\mathcal{B}$ and a formal variable $\mathcal{X}$ (resp. $\mathcal{Y}$). Note that there are canonical injective maps from $\mathcal{A}_1$ and from $\mathcal{A}_2$ to $\mathcal{B}\langle\mathcal{X}, \mathcal{Y}\rangle$, where $\mathcal{X}$ and $\mathcal{Y}$ are algebraically free. We identify $\mathcal{A}_1$ and $\mathcal{A}_2$ to their image through these morphism. We define the map $\mu: \mathcal{B}\langle\mathcal{X}, \mathcal{Y}\rangle \to \mathcal{B}$ through the following rule. For any $n \ge 1$, let $P_1, \dots, P_n$ such that $P_i \in \mathcal{A}_{j_i}$ with $j_1 \neq j_2, \dots, j_{n-1} \neq j_n$, denoting $\nu(P_i) = \mu_x(P_i)$ if $j_i = 1$ and $\nu(P_i) = \mu_y(P_i)$ if $j_i = 2$, we have

$$ \mu((P_1 - \nu(P_1)) \cdots (P_n - \nu(P_n))) = 0 \qquad (2.3) $$

Finally for any polynomial $P \in \mathcal{B}\langle\mathcal{Z}\rangle$ we denote $P(\mathcal{X} + \mathcal{Y}) \in \mathcal{B}\langle\mathcal{X}, \mathcal{Y}\rangle$ its image through $\mathcal{Z} \mapsto \mathcal{X} + \mathcal{Y}$ and $x \boxplus_{\mathcal{B}} y$ as the element having distribution $\mu_{x \boxplus_{\mathcal{B}} y}$ defined as

$$ \mu_{x \boxplus_{\mathcal{B}} y} : \mathcal{B}\langle\mathcal{Z}\rangle \to \mathcal{B} \\ P \mapsto \mu(P(x + y)), $$

with the natural evaluation map.

Hence, there exists a canonical way to build the amalgamated (over $\mathcal{B}$) free product between two non commutative operator-valued variable. We provide in Section 3 a more explicit construction in the case of random matrices.

**Remark 2.1:** Two cases of $C^*$-operator-valued probability spaces will be of importance later.

* The triplet $(M_N(\mathbb{C}), \mathcal{D}_N(\mathbb{C}), \Delta)$ where $\mathcal{D}_N(\mathbb{C})$ is the (commutative) **algebra of diagonal matrices** and $\Delta$ is the map defined by $\Delta(M) = (M_{i,j}1_{i=j})_{1 \le i, j \le N}$, is a $C^*$-operator-valued probability space.

* Moreover, one can also take any unital $*$-algebras $\mathcal{B} \subset \mathcal{A} \subset B(H)$, such that they are both closed in the norm topology of $B(H)$ and take any $*$-morphism from $\mathcal{A}$ to $\mathcal{B}$ which will automatically be completely positive (see [18] Chapter 3 and [9] Example 34.3).

**Definition 2.4:** A random matrix $M$ is said to be permutation invariant if for any $\sigma \in \mathfrak{S}_N$, the matrix $V_\sigma MV_\sigma^{-1}$ has the same law as $M$, where $V_\sigma = (1_{i=\sigma(j)})_{1 \le i, j \le N}$.

A key result from [1] is that independent permutation invariant random matrices that are bounded in operator norm are asymptotically free over the diagonal. We state a weaker version of this result.
**Theorem 2.5** (Theorem 1.2 of [1]). Let $A_1$ and $A_2$ be independent permutation invariant random matrices that are bounded in operator norm. Let $P_1, \dots, P_n \in \mathcal{D}_N \langle \mathcal{X} \rangle$ and $j_1 \neq j_2 \neq \dots \neq j_n$, then denoting

$$ \epsilon_N := \Delta((P_1(A_{j_1}) - \Delta(P_1(A_{j_1}))) \cdots (P_n(A_{j_n}) - \Delta(P_n(A_{j_n}))) , $$

we have

$$ \mathbb{E} \left[ \frac{1}{N} \mathrm{Tr}(\epsilon_N \epsilon_N^*)^p \right] \underset{N \to \infty}{\longrightarrow} 0. \qquad (2.4) $$

Our goal is to compare quantitatively the law of $A+B$ to the law of the amalgamated free sum of $A$ and $B$. Heuristically, to build the amalgamated free sum, we build from the data of $A$ and $B$ a bounded operator $a+b$ on some Hilbert space which is the adjacency operator of some graph. The important feature of this graph is that its graph of colored component with respect to the families $A$ and $B$ is a tree (see Section 4.1).

## 2.2 Main theorems and sketch of the proof

Let $A$ be permutation invariant, we can consider $B$ to also be permutation invariant. Indeed, denoting $\tilde{B} := VBV^{-1}$ where $V$ is a uniform permutation matrix, we have $\mathbb{E} \mathrm{Tr} G_{A+B}(zI) = \mathbb{E} \mathrm{Tr} G_{A+\tilde{B}}(zI)$. Therefore in the remainder of this paper, and in particular in the proofs of the following theorems, we consider $A$ and $B$ to be permutation invariant random matrices.

For $A$ and $B$ two random matrices we denote by $a+b$ their free sum over the diagonal, i.e. the operator constructed in Section 3. In this context, $a$ and $b$ are still free over the algebra of diagonal matrices, hence $G_{a+b}(D)$ takes values in $\mathcal{D}_N(\mathbb{C})$. For simplicity, we denote $G_X(z) = G_X(zI)$ the diagonal-valued Cauchy transform of $X$ taken at a scalar matrix $zI$. For a matrix $M$, we denote by $||M||_F := \sqrt{\mathrm{Tr}(MM^*)}$ the Frobenius norm of $F$ and $||M||_{op}$ its operator norm.

**Theorem 2.6.** Let $A$ and $B$ be random Hermitian matrices that satisfy Assumption 4.5 at speed $M$ with constants $h_1$ and $h_2$ respectively and Assumption 4.6 at speed $M$ with constant $C$ for both. Assume that one of them is permutation invariant. Let $0 \le c \le \frac{1}{h_1+h_2+6}$ and $|z|^2 > \max\{4C, 2c^2\} =: r_0^2$, we have

$$ \mathbb{E} \frac{1}{N} \| G_{a+b}(z) - G_{A+B}(z) \|_F^2 \le \frac{4}{|z|^2} \left( \frac{r_0}{|z|} \right)^{2cM} \qquad (2.5) $$

It is specified in the Assumptions that the speed $M$ cannot be greater than $\log N/\log \log N$. Therefore, the best speed one can achieve is of order $N^{\gamma/\log \log N}$.

The next theorem is more restrictive on the assumptions but provides a better speed of convergence and controls the difference of the operator-valued Cauchy transforms not only on scalar matrices.
**Theorem 2.7.** Let A and B be two Hermitian random matrices, one of them being per-mutation invariant. Assume that there exists $C > 0$ independent of N such that they are

1. Uniformly bounded in operator norm: $||A||_{op}, ||B||_{op} \le C$,

2. Sparse: $\forall 1 \le i \le N, \sum_{j=1}^{N} 1_{A_{i,j} \ne 0} + 1_{B_{i,j} \ne 0} \le C$.

Let $\eta_0 > ||A||_{op} + ||B||_{op}$ and $D \in \mathcal{D}_N(\mathbb{C})$ such that $\min\{\mathrm{Im}(D_{i,i})\} > \eta_0$, and denote $d := \min\{|D_{i,i}|, i \in [N]\}$, we have

$$ \mathbb{E} \frac{1}{N} ||G_{A+B}(D) - G_{a+b}(D)||_F^2 \le \frac{6}{d^2} N^{\frac{2 \log 2C}{1+2 \log C}}. \quad (2.6) $$

The proof of both theorems rely on a moment method: we compare the moments of $A+B$ to the moments of the operator $a+b$ constructed in Section 3.

## 3 Explicit construction of the amalgamated free sum

We give a constructive definition of the amalgamated free sum of A and B as the adjacency operator of a locally finite rooted weighted graph. This construction is inspired from [20] and from the methods developed in [12, 10]. Let $N \in \mathbb{N}$, for $x \in [N] := \{1, \dots, N\}$, we define

$$ V_N^x := \{x\} \sqcup \bigsqcup_{n=1}^{\infty} V_N^x(n, a) \sqcup V_N^x(n, b), \text{ where} $$

$$ V_N^x(n, a) := \{(j_1, \dots, j_n, a) \in [N]^n \times \{a\} | x \neq j_1, j_1 \neq j_2, \dots, j_{n-1} \neq j_n\}, $$

$$ V_N^x(n, b) := \{(j_1, \dots, j_n, b) \in [N]^n \times \{b\} | x \neq j_1, j_1 \neq j_2, \dots, j_{n-1} \neq j_n\}. $$

Let $\mathcal{H}_N^x := \ell^2(V_N^x)$ be the set of sequences $(y_v)_{v \in V_N^x}$ such that $\sum_{v \in V_N^x} |y_v|^2 < +\infty$. Since $(\delta_v)_{v \in V_N^x}$ is a basis of $\mathcal{H}_N^x$ (where $\delta_v$ denotes the sequence with 0 everywhere except at $v$), we often identify elements of this basis of $\mathcal{H}_N^x$ with elements of $V_N^x$. We let $V_N^x(0) := \{x\}$ for easier notations.

Note that for $x, y \in [N]$, there is a natural bijection between $V_N^x$ and $V_N^y$ where one sends a tuple $(j_1, \dots, j_n, a)$ to $(j'_1, \dots, j'_n, a)$ with $j'_i = j_i$ if $j_i \notin \{x, y\}$, $j'_i = x$ if $j_i = y$ and $j'_i = y$ if $j_i = x$ and similarly for tuple ending in b. This bijection naturally defines an isomorphism $\Psi_{x \to y}: \mathcal{H}_N^x \to \mathcal{H}_N^y$ when acting on elements of the basis, we thus often write $\mathcal{H}_N$ instead of $\mathcal{H}_N^x$.

We build a family of maps, for $x \in [N]$,

$$ \boxplus_{\Delta}^{x} : \mathcal{M}_{N}(\mathbb{C}) \times \mathcal{M}_{N}(\mathbb{C}) \to B(\mathcal{H}_{N}^{x}), \quad (3.1) $$

that verify the following property: $\forall x, y \in [N], (\boxplus_{\Delta}^{x}) = \Psi_{y \to x}(\boxplus_{\Delta}^{y})\Psi_{x \to y}$. Hence, one just needs to construct one of those maps and we will call it simply $\boxplus_{\Delta}$.
The idea is the following, for each matrix $A$ and $B$, we construct $A \oplus_{\Delta} B$ as follows. Viewing $A$ and $B$ as weighted graphs on the set of vertices $[N]$, we attach to each vertex $v$ of $A$, a copy of the graph $B$ by the same vertex $v$ of $B$. Then, to each new vertex created (hence vertices of one of the copies of the graph of $B$), we attach a new copy of $A$ to the corresponding vertex. Repeating this process infinitely many times, we obtain an infinite weighted locally finite graph. Its adjacency operator is in $B(H_N)$.

**Remark 3.1:** Starting from a different vertex $y$ leads to exactly the same graph after renaming the set of vertices as above

Figure 1 represents the first steps of this construction when the root is the vertex 2.

<figure><img src="image_2.png" /><figcaption>**Figure 1:** Construction of $A \oplus_{\Delta} B$ as an iterating process. The blue (resp. red) edges are labeled $a$ (resp. $b$).</figcaption></figure>

It should be noted that this graph has a tree-like structure when looking at the components that come from $A$ and the components that come from $B$. Formally, its graph of colored components with respect to the families $A$ and $B$ is an infinite tree (see Section 4).

We now explicitly construct operators $a, b \in B(H_N^x)$ associated to $A$ and $B$ such that $A \oplus_{\Delta} B = a+b$. Then, we show that they are free over the algebra of diagonal operators and even above the algebra of diagonal matrices in a sense to be made precise below. Therefore,
we define the amalgamated free sum of A and B as the sum of a and b (where the sum is now taken with respect to the natural sum operation on bounded linear operators).

In order to facilitate the definition of a and b, we use the convention $V_N(0, a) = V_N(0, b) = V_N(0) = \{x\}$ and when $n = 0$, $(j_1, \dots, j_n, a) = (j_1, \dots, j_n, b) = x$. With this, one has the following decompositions of the set $V_N^x$ as

$$V_N^x = \bigsqcup_{n=0}^{\infty} \bigsqcup_{v \in V_N(n,b)} R_a(v) = \bigsqcup_{n=0}^{\infty} \bigsqcup_{w \in V_N(n,a)} R_b(w), \quad (3.2)$$

where, for $n \ge 0$, $v = (j_1, \dots, j_n, b) \in V_N(n, b)$ and $w = (j_1, \dots, j_n, a) \in V_N(n, a)$, we denote

$$\begin{align}
R_a(v) &:= \{v\} \sqcup \{(j_1, \dots, j_n, j_{n+1}, a), j_{n+1} \in [N] \setminus \{j_n\}\}, \tag{3.3} \\
R_b(w) &:= \{w\} \sqcup \{(j_1, \dots, j_n, j_{n+1}, b), j_{n+1} \in [N] \setminus \{j_n\}\}. \nonumber
\end{align}$$

Looking at Figure 1, it is easy to understand this decomposition. One groups vertices that belong to a same colored component: blue for $R_a$ and red for $R_b$. We call the sets $R_a(v)$, $R_b(w)$ components in $a, b$ respectively.

With this decomposition, we define the operators $a$ and $b$ as follows.

Let $n \ge 0$ and $v = (j_1, \dots, j_n, b) \in V_N(n, b)$. Let $v_1, v_2 \in R_a(v)$, we denote $j(v_1)$ and $j(v_2)$ the last index of $v_1$ and $v_2$ respectively (it might be $j_n$ or some $j_{n+1} \ne j_n$) and we set $\langle a\delta_{v_1}, \delta_{v_2} \rangle = A(j(v_2), j(v_1))$.

Similarly, let $n \ge 0$ and $w = (j_1, \dots, j_n, a) \in V_N(n, a)$. Let $w_1, w_2 \in R_b(w)$, we denote $j(w_1)$ and $j(w_2)$ the last index of $w_1$ and $w_2$ respectively (it might be $j_n$ or some $j_{n+1} \ne j_n$) and we set $\langle b\delta_{w_1}, \delta_{w_2} \rangle = B(j(w_2), j(w_1))$.

Let $n \ge 0$, let $v \in V_N(n, b)$ for any $v_1 \in R_a(v)$, we define

$$a : \delta_{v_1} \mapsto \sum_{v_2 \in R_a(v)} \langle a\delta_{v_1}, \delta_{v_2} \rangle \delta_{v_2}. \quad (3.4)$$

Similarly, let $n \ge 0$, let $w \in V_N(n, a)$ for any $w_1 \in R_b(w)$, we define

$$b : \delta_{w_1} \mapsto \sum_{w_2 \in R_b(w)} \langle b\delta_{w_1}, \delta_{w_2} \rangle \delta_{w_2}. \quad (3.5)$$

Notice that $a$ and $b$ respect the decomposition given by (3.2) in the sense that any vertex $v$ is sent by $a$, resp. $b$, to vertices in its components in $a$ resp. $b$.

The matrices $A$ and $B$ being Hermitian, it is easy to see that $a$ and $b$ are bounded self-adjoint operators with same spectral norm than $A$ and $B$ respectively.

Recall that for $T \in B(H_N^x)$, we define the diagonal of $T$ as

$$\Delta(T) : \delta_v \mapsto \langle T(\delta_v), \delta_v \rangle \delta_v, \quad (3.6)$$

and note that $\Delta(B(H_N^x)) =: \mathcal{D}$ is a closed subalgebra of $B(H_N^x)$ for the norm topology.

Let $\mathcal{A} = \text{cl span}\{a, b, \mathcal{D}\}$ where cl is the closure in $B(H_N^x)$ for the norm topology. The triplet $(\mathcal{A}, \mathcal{D}, \Delta)$ is a $C^*$-operator-valued non commutative probability space.
**Proposition 3.1.** The operators a and b are Δ-free in (A, D, Δ).

*Proof.* We denote $X_1$ (resp. $X_2$) the subalgebra of $\mathcal{A}$ generated by $a$ and $\mathcal{D}$ (resp. $b$ and $\mathcal{D}$). Note that this is not only the vector space spanned by monomials of the form $(ad)^k$ for $d \in \mathcal{D}$ but since $a$ and $d$ do not commute in general, it is spanned by monomials of the form $d_0ad_1 \cdots ad_k$, for $d_0, d_1, \cdots, d_k \in \mathcal{D}$.

Let $m \ge 2$ and $x_1, \cdots, x_m$ be such that $x_{2i-1} \in X_1$ and $x_{2i} \in X_2$ for all $1 \le i \le \lfloor m/2 \rfloor$ and such that for all $1 \le i \le m$, $\Delta(x_i) = 0$. We want to show that $\Delta(x_1 \cdots x_m) = 0$. Let $v \in V_N^x$, we want to compute $\langle x_1 \cdots x_m(\delta_v), \delta_{v'} \rangle$. First assume that $x_m \in X_1$ and $v \in V_N(n, b)$ for some $n \ge 0$. Since $x_m$ is centered, we have

$$x_m(\delta_v) = \sum_{v' \in R_a(v) \setminus \{v\}} \langle x_m \delta_v, \delta_{v'} \rangle \delta_{v'}. \qquad (3.7)$$

Since $R_a(v) \setminus \{v\} \subset V_N(n+1, a)$, by induction, we have that $x_1 \cdots x_m(\delta_v) \subset V_N(n+m, a) \cup V_N(n+m, b)$, hence $\Delta(x_1 \cdots x_m) = 0$. The same reasoning applies when $x_m \in X_2$ and $v \in V_N(n, a)$ for some $n \ge 0$.

Let us now assume that $x_m \in X_1$ and $v = (j_1, \cdots, j_n, a) \in V_N(n, a)$ for some $n \ge 0$. To simplify notations, for any $k \ge 0$, we define by convention $V_N(-k, a) = V_N(k, a)$ and similarly for $b$. The vertex $v_{m-1} = (j_1, \cdots, j_{n-1}, b) \in V_N(n-1, b)$ is such that $v \in R_a(v_{m-1})$, thus

$$x_m(\delta_v) = \langle x_m \delta_v, \delta_{v_{m-1}} \rangle \delta_{v_{m-1}} + \sum_{w \in R_a(v_{m-1}) \setminus \{v, v_{m-1}\}} \langle x_m \delta_v, \delta_w \rangle \delta_w.$$

For any $w \in R_a(v_{m-1}) \setminus \{v, v_{m-1}\}$, $w = (j_1, \cdots, j_{m-1}, j, a)$ for some $j \neq j_m$. Hence $x_1 \cdots x_{m-1}(\delta_w)$ is supported by vertices of the form $(j_1, \cdots, j_{m-1}, j, i_1, \cdots, i_{m-1}, \varepsilon)$ for $\varepsilon \in \{a, b\}$ which can never be equal to $v$ since $j \neq j_m$. We can therefore disregard the contribution of these terms.

We repeat this process for $v_{m-1}$: the vertex $v_{m-2} = (j_1, \cdots, j_{n-2}, a) \in V_N(n-2, a)$ is such that $v_{m-1} \in R_b(v_{m-2})$. Hence

$$x_{m-1}(\delta_{v_{m-1}}) = \langle x_{m-1} \delta_{v_{m-1}}, \delta_{v_{m-2}} \rangle \delta_{v_{m-2}} + \sum_{w \in R_b(v_{m-2}) \setminus \{v_{m-1}, v_{m-2}\}} \langle x_n \delta_v, \delta_w \rangle \delta_w.$$

Any $w \in R_b(v_{m-2}) \setminus \{v_{m-1}, v_{m-2}\}$ is of the form $w = (j_1, \cdots, j_{n-2}, j, b)$ for some $j \neq j_{n-1}$, hence $x_1 \cdots x_{m-2}(\delta_w)$ will be supported by vertices of the form $(j_1, \cdots, j_{n-2}, j, i_1, \cdots, i_{m-2}, \varepsilon)$ for $\varepsilon \in \{a, b\}$. Again, we can disregard the contribution of those terms.

If $m \le n$, this reasoning can be applied $m$ times and at each step, $v_k \in V_N(n-(m-k), \varepsilon)$ for $\varepsilon \in \{a, b\}$, therefore, the product $x_1 \cdots x_m$ is centered.

Otherwise, if $m > n$, we apply this reasoning $n$ times until $v_{m-n} = x$. We next apply $x_{m-n}$. Hence $x_1 \cdots x_{m-n}(\delta_x)$ is supported on vertices of the form $(i_1, \cdots, i_{m-n}, \varepsilon)$ for $\varepsilon \in \{a, b\}$. Hence the only non-trivial case happens when $m-n = n$ which implies that $m$ is even. If $n$ is even, $x_{m-n} \in X_1$ otherwise $x_{m-n} \in X_2$. Furthermore, if $n$ is even, this implies on one hand $x_{m-n} \in X_1$ and on the other hand that $m-n$ is even. Therefore one must have $\varepsilon = b$: indeed we apply the reasoning of the first scenario to see that one takes
an even number of steps starting with a step labeled $a$ which will end in a step labeled $b$. Similarly, if $n$ is odd, this implies that $x_{m-n} \in X_2$ and $m-n$ is odd which in turns implies $\varepsilon = b$. In both cases the scalar product of $x_1 \cdots x_{m-n}(\delta_x)$ with $\delta_v$ will lead to a zero contribution. $\square$

**Remark 3.2:** Writing the proof and understanding it as it is is quite tedious. However, one should draw the graph associated to $a$ and the one associated to $b$ and see that, alternating between edges from $a$ and edges from $b$ while never staying at the same vertex (the $x_i$'s are centered), one can never return to the starting vertex.

**Remark 3.3:** There is a natural embedding of $\mathcal{D}_N(\mathbb{C})$ into $\mathcal{D}$: for $D \in \mathcal{D}_N(\mathbb{C})$, we still denote the associated diagonal operator $D \in \mathcal{D}$ defined by $D(\delta_v) = D_{j(v),j(v)}\delta_v$, for any $v \in V_N$, where $j(v)$ denotes the last index of $v$. We therefore identify $\mathcal{D}_N(\mathbb{C})$ with the image of $\mathcal{D}_N(\mathbb{C})$ through this embedding.

Defining $E_{\mathcal{D}_N(\mathbb{C})}: \mathcal{A} \to \mathcal{D}_N(\mathbb{C})$, $T \mapsto (\langle T\delta_{(i,a)}, \delta_{(i,a)}\rangle)_{1\le i\le N}$, it is not hard to see that $(\mathcal{A}, \mathcal{D}_N(\mathbb{C}), E_{\mathcal{D}_N(\mathbb{C})})$ is a $C^*$-operator-valued probability space

**Corollary 3.2.** The operators $a$ and $b$ are free in the $C^*$-operator-valued probability space $(\mathcal{A}, \mathcal{D}_N(\mathbb{C}), E_{\mathcal{D}_N(\mathbb{C})})$.

*Proof.* The algebra $\mathcal{D}_N(\mathbb{C})$ is a subalgebra of $\mathcal{D}(\mathcal{H}_N)$ and $E_{\mathcal{D}_N(\mathbb{C})} = E_{\mathcal{D}_N(\mathbb{C})} \circ \Delta$. Moreover, for any diagonal matrices $D_0, \cdots, D_n$, the moment $\Delta(D_0aD_1 \cdots aD_n)$ is actually in $\mathcal{D}_N(\mathbb{C})$ and the same goes when replacing $a$ by $b$. Indeed, the definition of $a$ and $b$ only depends on the last index of the vertex $v$. Hence, the $\Delta$-moments of $a$ and $b$ are in $\mathcal{D}_N(\mathbb{C})$, therefore, they are equal to their $E_{\mathcal{D}_N(\mathbb{C})}$-moments. Proposition 16, Chapter 9 of [17] concludes the proof. $\square$

Moreover, let $\varphi: \mathcal{A} \to \mathbb{C}$, $T \mapsto \frac{1}{N} \sum_{v \in R_a(x)} \langle T\delta_v, \delta_v \rangle$, be a unital positive $*$-morphism so that it endows $\mathcal{A}$, $\mathcal{D}$ and $\mathcal{D}_N(\mathbb{C})$ with a structure of $C^*$-probability space. Note that in the literature, a $C^*$-operator-valued probability space is sometimes required to be equipped with such a positive linear functional $\varphi: \mathcal{A} \to \mathbb{C}$.

A key result that one may find in [18] is that for any self-adjoint element $x$ in a $C^*$-probability space $(\mathcal{A}_0, \varphi_0)$, there exists a compactly supported real measure $\mu_x$ (with support included in the spectrum of $x$) such that for every continuous function $f$ on the spectrum of $x$, $\int f d\mu_x = \varphi_0(f(x))$, where on the right-hand side $f(x)$ is defined by functional calculus and on the left-hand side $\mu_x$ is viewed as a measure on the spectrum of $x$. This can then be applied to $(\mathcal{A}, \varphi)$.

# 4 Traffic notions and assumptions

The last ingredients we need in order to prove Theorems 2.6 and 2.7 come from traffic probability. It has been introduced by Male in [16], for the sake of completeness, we restate some of the relevant definitions and results required in this work.
## 4.1 Traffic notions

**Definition 4.1 (Graph of colored components):** Let $H$ be a graph with edges labeled by a family $\{x_i\}_{i \in I}$ (each $x_i$ may itself be a family of several labels as long as $x_i \cap x_j = \emptyset$ for $i \neq j$).

A colored component $T$ of $H$ is a maximal subgraph with at least one edge whose edges are labeled only with labels from a single family. We denote by $\mathcal{CC}(H)$ the set of colored components of $H$.

The graph of colored components of $H$ with respect to the families $\{x_i\}_{i \in I}$ denoted $\mathcal{GCC}(H)$ is the following bipartite graph:

* The first kind of vertices are the colored components $T_1, \dots, T_K$ of $H$.

* The second kind of vertices are vertices $v_1, \dots, v_L$ of $H$ that belong to at least two colored components.

* There is an edge between $v_i$ and $T_j$ if $v_i \in T_j$ for all $1 \le i \le L$, $1 \le j \le K$.

For a given connected simple graph $H = (V, E)$, we denote

$$ \eta(H) := |V| - |E| - 1. \qquad (4.1) $$

Note that $\eta(H) \le 0$ with equality if and only if $H$ is a tree (see [11] Lemma 1.1).

**Remark 4.1:** We will often talk about the graph of colored components of $A+B$, implicitly stating that it is with respect of the family of edges coming from $A$ and the family of edges coming from $B$. In that case, we denote $\mathcal{V}_{cc}$ (for colored component) the first kind of vertices of the graph of colored components of $H$ and $\mathcal{V}_{co}$ (for connectors) the second kind of vertices. Denoting $\mathcal{E}$ the set of edges of $\mathcal{GCC}(H)$, notice that $|\mathcal{E}| = 2|\mathcal{V}_{co}|$, hence $\eta(\mathcal{GCC}(H)) = |\mathcal{V}_{cc}| - |\mathcal{V}_{co}| - 1$.

**Definition 4.2:** Let $J$ be a set of indices and consider two families of formal variables $\mathbf{x} = (x_j)_{j \in J}$ and $\mathbf{x}^* = (x_j^*)_{j \in J}$.

1. A $*-test graph$ $T = (G, \gamma, \epsilon)$ in the variables $\mathbf{x}$ is a finite connected multi-digraph $G = (V, E, \text{src}, \text{tar})$ together with edge labels $\epsilon: E \to \{1, *\}$ and $\gamma: E \to J$. One can see the maps $\gamma$ and $\epsilon$ as indicating that an edge $e \in E$ is labeled $x_{\gamma(e)}^{\epsilon(e)}$. The maps $\text{src}, \text{tar}: E \to V$ specify the source, $\text{src}(e)$ and target, $\text{tar}(e)$ of each edge $e \in E$.

2. A $*-graph monomial$ $g = (T, v_{in}, v_{out})$ is a $*-test graph$ $T$ together with the data of two vertices $v_{in}$ and $v_{out}$ in $V$. We refer to the roots $(v_{in}, v_{out}) \in V^2$ as the input and the output, respectively, though they need not be distinct. We denote by $\mathcal{G}\langle \mathbf{x}, \mathbf{x}^* \rangle$ the set of all such $*-graph monomials which can be extended to $\mathcal{C}\mathcal{G}\langle \mathbf{x}, \mathbf{x}^* \rangle$ the space of finite linear complex combinations of $*-graph monomials in variable $\mathbf{x}$ (graphs are considered up to isomorphisms of graphs preserving labeled and in/outputs).
**Example 4.1:** For a family $\mathbf{A}_N = (A_{N,j})_{j \in J}$ of random matrices, we define the evaluation of a *-graph monomial $g$ in the family $\mathbf{A}_N$ via the formula,

$$g(\mathbf{A}_N)(i, j) := \sum_{\substack{\phi:V \to [N] \\ \phi(v_{\text{out}})=i, \phi(v_{\text{in}})=j}} \prod_{e \in E} A_{N,\gamma(e)}^{\epsilon(e)}(\phi(\text{tar}(e)), \phi(\text{src}(e))). \quad (4.2)$$

For convenience, we will often denote $\phi(e)$ for $(\phi(\text{tar}(e)), \phi(\text{src}(e)))$. When one studies random matrices in the framework of free probability, one is interested in the expectation of the normalized trace of any polynomials evaluated in a family of random matrix. In the context of this section, the traffic distribution of a family of random matrices is the data of the expectation of the normalized trace of any *-graph monomial evaluated in this family.

**Example 4.2:** Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be a locally finite rooted graph (possibly dependent on $N$). Let $\mathbf{a}_N = (a_{N,j})_{j \in J}$ be a family of random operators on $B(L^2(\mathcal{V}))$ such that for all $j \in J$, $\langle a_{N,j}\delta_v, \delta_w \rangle = 0$ if $(v, w)$ is not an edge of $\mathcal{G}$. We define the evaluation of a *-graph monomial $g$ in the family $\mathbf{a}_N$ via the formula,

$$\langle g(\mathbf{a}_N)\delta_v, \delta_w \rangle := \sum_{\substack{\phi:V \to \mathcal{V} \\ \text{graph morphism,} \\ \phi(v_{\text{out}})=v, \phi(v_{\text{in}})=w}} \prod_{e \in E} \langle a_{N,\gamma(e)}^{\epsilon(e)} \delta_{\phi(\text{tar}(e))}, \delta_{\phi(\text{src}(e))} \rangle. \quad (4.3)$$

For convenience, we will often denote $a(\phi(e))$ for $\langle a\delta_{\phi(\text{tar}(e))}, \delta_{\phi(\text{src}(e))} \rangle$. Note that $g(\mathbf{a}_N)$ does not necessarily verify the condition that $\langle g(\mathbf{a}_N)\delta_v, \delta_w \rangle = 0$ if $(v, w) \notin \mathcal{E}$ however, it can be seen as an adjacency operator of some weighted locally finite graph. Note that this coincides with the previous definition when $\mathcal{G}$ is the complete graph on $N$ vertices.

The following definitions are usually defined for test-graphs. We define their counterpart for (rooted) graph monomials and we keep the same names.

**Definition 4.3:** Let $i \in [N]$, the $i$-rooted traffic distribution of a family $\mathbf{A}_N$ of random matrices is the map

$$\Phi_{\mathbf{A}_N}^i : g \in \mathbb{C}\mathcal{G}\langle \mathbf{x}, \mathbf{x}^* \rangle \to \mathbb{E}[g(\mathbf{A}_N)_{i,i}]. \quad (4.4)$$

Let $\mathbf{a}_N$ be a family of random operators acting on $L^2(\mathcal{V})$ where $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \rho)$ is a locally finite $\rho$-rooted graph dependent on $N$. The $\rho$-rooted traffic distribution of $\mathbf{a}_N$ is

$$\Phi_{\mathbf{a}_N}^{\rho} : g \in \mathbb{C}\mathcal{G}\langle \mathbf{x}, \mathbf{x}^* \rangle \to \mathbb{E}[\langle g(\mathbf{a}_N)\delta_{\rho}, \delta_{\rho} \rangle]. \quad (4.5)$$

With a slight abuse of notation, we also denote $\tau_i(g(\mathbf{A}_N)) = \Phi_{\mathbf{A}_N}^i(g)$ and similarly for operators.

Note that these two definitions coincide when $\mathcal{G}$ is the complete graph on $N$ vertices. It is natural in a traffic probability framework to decompose the sums in Examples 4.1 and
4.2 depending on the default of injectivity of $\phi$. More precisely,

$$
\begin{align*}
g(\mathbf{A}_N)(i,j) &= \sum_{\pi \in P(V)} \sum_{\substack{\phi: V^\pi \to [N], \\ \phi \text{ injective,} \\ \phi(v_{\text{out}})=i, \phi(v_{\text{in}})=j}} \prod_{e \in E^\pi} A_{N,\gamma(e)}^{\epsilon(e)}(\phi(\text{tar}(e)), \phi(\text{src}(e))), \\
\langle g(\mathbf{a}_N)\delta_v, \delta_w \rangle &= \sum_{\pi \in P(V)} \sum_{\substack{\phi: V^\pi \to V \\ \text{injective graph morphism,} \\ \phi(v_{\text{out}})=v, \phi(v_{\text{in}})=w}} \prod_{e \in E^\pi} \langle a_{N,\gamma(e)}^{\epsilon(e)} \delta_{\phi(\text{tar}(e))}, \delta_{\phi(\text{src}(e))} \rangle,
\end{align*}
$$

where a partition $\pi$ of the vertices of the graph monomial $g$ induces a new graph monomial $g^\pi = (V^\pi, E^\pi, \gamma, \varepsilon, v_{in}, v_{out})$ obtained from $g$ after identifying vertices in a same block of $\pi$. This motivates the following definition

**Definition 4.4:** The *i*-rooted injective trace of *g* in the matrices **A**<sub>N</sub>, and the *ρ*-rooted injective trace of *g* in the operators **a**<sub>N</sub> is

$$
\begin{align*}
\operatorname{Tr}_i^0(g(\mathbf{A}_N)) &= \sum_{\substack{\phi:V \to [N], \\ \phi \text{ injective,} \\ \phi(v_{\text{out}})=\phi(v_{\text{in}})=i}} \prod_{e \in E} A_{N,\gamma(e)}^{\epsilon(e)}(\phi(\text{tar}(e)), \phi(\text{src}(e))), \\
\operatorname{Tr}_{\rho}^0(g(\mathbf{a}_N)) &= \sum_{\substack{\phi:V \to V \\ \text{injective graph morphism,} \\ \phi(v_{\text{out}})=\phi(v_{\text{in}})=\rho}} \prod_{e \in E} \langle a_{N,\gamma(e)}^{\epsilon(e)} \delta_{\phi(\text{tar}(e))}, \delta_{\phi(\text{src}(e))} \rangle,
\end{align*}
$$

so that

$$
\begin{align*}
\tau_i(g(\mathbf{A}_N)) &= \sum_{\pi \in P(V)} \mathbb{E} \operatorname{Tr}_i^0(g^\pi(\mathbf{A}_N)) := \sum_{\pi \in P(V)} \tau_i^0(g^\pi(\mathbf{A}_N)), \\
\tau_\rho(g(\mathbf{a}_N)) &= \sum_{\pi \in P(V)} \mathbb{E} \operatorname{Tr}_\rho^0(g^\pi(\mathbf{A}_N)) := \sum_{\pi \in P(V)} \tau_\rho^0(g^\pi(\mathbf{A}_N)).
\end{align*}
$$

Note that if $\pi$ does not identify $v_{in}$ and $v_{out}$, the injective trace is zero.

**Remark 4.2:** In [16] it is shown that whenever the families $\mathbf{A}_N^{(1)}, \dots, \mathbf{A}_N^{(L)}$ are permutation invariant, converge in traffic distribution and satisfy some factorization property, then they are asymptotically traffic independent. Moreover, it is shown in [1] that, provided the same condition holds, they are asymptotically free over the diagonal.

In the following, we still call $T_N$ a test graph where $T_N := (V_N, E_N, \gamma, \epsilon)$ is no longer fixed with respect to $N$ but is allowed to have a number of vertices and edges dependent of $N$. Furthermore, when specified, we also allow the test-graph to have several connected components, however one should be careful when dealing with this case since the injective trace does not behave well with multiple components. Again, when unspecified, a generic test-graph is always finite and have a single connected component.
## 4.2 Assumption on the injective trace

We provide in this subsection one of the assumptions of Theorem 2.6. Heuristically, this is a boundedness condition for large "moments" but in traffic framework, i.e. for large test graphs. We then provide several random matrix models that satisfy this condition.

**Assumption 4.5:** Let $M = M(N)$ be a sequence that goes to infinity with $N$ and that is smaller than $\log N/\log \log N$. The sequence $X_N$ of random matrices satisfies Assumption 4.5 at speed $M$ if there exists some positive constant $h$ such that for any positive constant $c$ and for any sequence of test-graphs $T_N := (V_N, E_N, \epsilon)$ such that $T_N$ has $K(N)$ connected components: $T_{1,N}, \dots, T_{K(N),N}$ ($T_{i,N} := (V_{i,N}, E_{i,N})$) verifying

$$ \sum_{k=1}^{K(N)} |V_{k,N}| \le cM, \quad \sum_{k=1}^{K(N)} |E_{k,N}| \le cM, \qquad (4.6) $$

we have

$$ \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] = O(N^{c \cdot h}), \qquad (4.7) $$

for some constant $h$.

First note that $M \le \log N$, so we often show that the quantity in the left-hand side of (4.7) is bounded by $C^M$ for some constant $C$ which yields equation (4.7). We check that several model of random matrices verify these assumptions.

**Diluted matrices with bounded entries.** Let $X_N$ be a (possibly random) matrix of size $N$ such that almost surely, the number of non zero entries of $X$ per row and per column is bounded by $C = C(N)$. Moreover, assume also that the absolute value of the entries are bounded by $C$. The speed $C$ must be such that $\log C/\log N \to 0$ as $N \to \infty$. We first use the bound

$$ \left| \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] \right| \le \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(|X_N|)) \right]. $$

Now choose an arbitrary vertex in each connected component, say $v_1, \dots, v_{K(N)} \in V_{1,N} \times \dots \times V_{K(N),N}$, and sum over all possible values they can take. Since we sum over injective vertex assignments, the other vertices must take a different value. Denoting $V'_N := V_N \setminus \{v_1, \dots, v_{K(N)}\}$ and $[N]' := \{1, \dots, N\} \setminus \{i_1, \dots, i_{K(N)}\}$ for short, we get

$$ \frac{1}{N^{K(N)}} \mathrm{Tr}^0(T(|X_N|)) = \frac{1}{N^{K(N)}} \sum_{\substack{i_1, \dots, i_{K(N)}=1, \\ \text{pairwise distinct}}} \sum_{\phi: V'_N \to [N]', e \in E_N} \prod_{\phi \text{ injective}} |X(\phi(e))|, $$

where $\phi$ is extended on $V_N$ by $\phi(v_k) = i_k$ for $1 \le k \le K(N)$. For every $1 \le k \le K(N)$, we do the following reasoning. After having chosen the value of $v_k$, since $X_N$ is sparse, for each vertex $w$ at distance 1 of $v_k$ there is at most $C$ possible values for $\phi(w)$ that lead to a non
zero contribution. The same goes for vertices at distance 2 from $v_k$: after having chosen the values of vertices at distance $\le 2$ from $v_k$, there are at most $C$ possible values that lead to a non zero contribution for each new vertex at distance 2. Hence, after having chosen the value of the vertex $v_k$, we have at most $C^{|V_{k,N}|}$ choices for the remaining vertices in the connected component of $v_k$. Furthermore, since the entries are bounded, each contribution is less than $C^{|\bar{E}_{k,N}|}$. We obtain the bound

$$ \left| \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] \right| \le \frac{N(N-1)\cdots(N-K(N)+1)}{N^{K(N)}} \prod_{k=1}^{K(N)} C^{|V_{k,N}|+|E_{k,N}|}, \\ \le C^{2cM}. $$

Choosing $M$ such that $M \log C = \log N$ is the best speed we can achieve provided $M \le \log N/\log \log N$ and $\log N/\log C \to \infty$. Otherwise, one may just take $M = \log N/\log \log N$. Note that random permutation matrices, adjacency matrices of uniform $C$-regular graphs are special cases of such sparse bounded matrices.

**Erdos-Renyi matrices.** Let $B_N$ be the adjacency matrix of an Erdos-Renyi random graph: a graph with set of vertices $[N]$ and where each (undirected) edge $e = \{i, j\}$ with $i \ne j$ is present with probability $p = p(N)$ for some $0 < p < 1$ such that $p \to 0$ as $N \to \infty$ and $Np \to \infty$. Note that since the edges are undirected $X_N$ is symmetric with 0 on the diagonal and i.i.d. sub-diagonal entries following a Bernoulli law of parameter $p$. Let $X_N = \frac{B_N - p(J-I)}{\sqrt{Np(1-p)}}$, be the centered, normalized version of $B_N$ where $J$ is the full 1 matrix and $I$ the identity. Note that if the test graph $T_N$ has a loop, its injective trace is zero since $X_N$ only has 0's on its diagonal. Let us assume that $T_N$ does not have any loops and let us denote $\bar{E}$ the set of edges once we forget the multiplicity and the orientation of the edges of $T_N$. We denote $m(e)$ the multiplicity of the edge $e$ when forgetting about the orientation of the edges. Using the independence of the entries, we can explicitly compute

$$ \begin{aligned} \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] &= \frac{1}{N^{K(N)}} \sum_{\substack{\phi:V \to [N], \\ \phi \text{ injective}}} \mathbb{E} \left[ \prod_{\bar{e} \in \bar{E}} X(\phi(e))^{m(e)} \right] \\ &= \frac{1}{N^{K(N)}} \# \left\{ \phi:V \to [N], \phi \text{ injective} \right\} \prod_{\bar{e} \in \bar{E}} \left( p \left( \frac{1-p}{\sqrt{Np(1-p)}} \right)^{m(\bar{e})} + (1-p) \left( \frac{-p}{\sqrt{Np(1-p)}} \right)^{m(\bar{e})} \right), \\ &= N^{|V|-K(N)-|\bar{E}|} (1+o(1)) \prod_{\bar{e} \in \bar{E}} \left( (1-p) \left( \frac{1-p}{Np} \right)^{\frac{m(\bar{e})}{2}-1} + (-1)^{m(\bar{e})} p \left( \frac{p}{N(1-p)} \right)^{\frac{m(\bar{e})}{2}-1} \right), \end{aligned} $$

where we used Proposition A.1 for the last line. If there is some edge of multiplicity exactly one, since the entries are centered, the above quantity is 0. Otherwise the second term in
each term of the product is negligible and we obtain

$$ 
\begin{aligned}
\mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] &= N^{|V|-K(N)-|\bar{E}|} (1+o(1)) \prod_{\bar{e} \in \bar{E}} \left( \frac{1}{Np} \right)^{m(\bar{e})/2-1}, \\
&= N^{|V|-K(N)-|\bar{E}|} (Np)^{|\bar{E}|-|E|/2} (1+o(1)).
\end{aligned}
$$

By Euler's identity, we have $|V| - K(N) - |\bar{E}| \le 0$ with equality if and only if each connected component is a tree when forgetting about the multiplicity and the orientation of the edges. Since the edges all have at least multiplicity 2, $|\bar{E}| - |E|/2 \le 0$ with equality if and only if each connected component of $T_N$ is a double tree. Finally, we get the bound

$$ \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] = O(1). \qquad (4.8) $$

This assumption is also satisfied for $Np \to c > 0$, however, this model does not verify Assumption 4.6.

**Diluted Wigner matrices with moment conditions.** Erdös-Renyi matrices as above are a special case of diluted Wigner matrices in the following sense.

Let $X = (x_{i,j}^N)_{1 \le i,j \le N}$ be a Hermitian matrix such that the $(x_{i,j}^N)_{1 \le i \le j \le N}$ are centered, independent random variables that have moments up to order $cM$ (where $M$ goes to infinity and is smaller than $\log N/\log \log N$) and such that there exists some constants $h, \varepsilon > 0$ independent of $N$ such that for all $1 \le i \le j \le N$ and for all $2 \le k_1, k_2 \le cM$, we have

$$ N|\mathbb{E}(x_{i,j}^N)^{k_1} \overline{(x_{i,j}^N)^{k_2}}| \le \frac{\log(N)^{h(k_1+k_2)}}{N^\varepsilon}, \qquad (4.9) $$

and $N\mathbb{E}|x_{i,j}^N|^2 = 1$. Note that $M$ depends on $N$ so that Equation (4.9) must be satisfied for $k_1, k_2$ possibly dependent on $N$.

These matrices are a special case of heavy Wigner matrices (see [24]) since at fixed $k$ the quantity in (4.9) goes to 0 but we also impose a bound of order $N^c$ for the moments of order $\log N/\log \log N$. Actually, heavy Wigner matrices with moments conditions similar to (4.9) also satisfy Assumption 4.5 however, they do not satisfy in general Assumption 4.6.

Take $T_N$ as in Assumption 4.5 of size at most $cM$. For $\bar{e} \in \bar{E}$, recall that $\bar{e}$ is the set of all edges that are between two vertices, say $v$ and $w$. Choose an arbitrary orientation, say from $v$ to $w$ and, set $m_+(\bar{e})$, resp. $m_-(\bar{e})$, the number of edges in the equivalence class $\bar{e}$ that have the same orientation, resp. the opposite one. With similar technique as in the previous case, we obtain

$$ \mathbb{E} \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) = N^{|V|-K(N)-|\bar{E}|} \prod_{\bar{e} \in \bar{E}} \mathbb{E} \left( N X_N (\phi_N(\bar{e}))^{m_+(\bar{e})} \overline{X_N(\phi_N(\bar{e}))}^{m_-(\bar{e})} \right). $$

We denote by $\bar{E}_2 \subset \bar{E}$ the set of edges such that $m_+(\bar{e}) = m_-(\bar{e}) = 1$, i.e. edges that will contribute for one since $N\mathbb{E}|x|^2 = 1$. Each of the other edges $\bar{e} \in \bar{E} \setminus \bar{E}_2$ will have
a contribution of $\log_N^{h(m_+(\bar{e})+m_-(\bar{e}))}/N^\epsilon$. Denoting now $E_2 \subset E$ the set of edges such that $m_+(\bar{e}) = m_-(\bar{e}) = 1$, we obtain

$$ \left| \mathbb{E} \frac{1}{N^{K(N)}} \mathrm{Tr}^0(T_N(X_N)) \right| \le N^{|V|-|\bar{E}|-K(N)} \frac{\log(N)^{h(|E|-2|\bar{E}_2|)}}{N^{\epsilon(|\bar{E}|-|\bar{E}_2|)}} \le N^{hc}. \quad (4.10) $$

**Entry wise product.** Let $X_N$ be a matrix that verifies Assumption 4.5 at speed $M$ for some constant $h$ and let $\Gamma_N$ be a matrix that have all entries bounded by $C = C(N)$ such that there exists a constant $h'$ for which $M \log C \le h' \log N \Leftrightarrow C^M \le N^{h'}$ (note that this is always the case for $C = \log(N)^\alpha$ for any constant $\alpha$). Denote $W_N := X_N \circ \Gamma_N$ the entry wise product of the two matrices. We easily have

$$ \left| \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N \circ \Gamma_N)) \right] \right| \le \left| \mathbb{E} \left[ \frac{1}{N^{K(N)}} \mathrm{Tr}^0 (T_N(X_N)) \right] \right| \times C^{cM} = O \left( N^{c(h+h')} \right), \quad (4.11) $$

showing that $W_N$ also verifies Assumption 4.5.

## 4.3 Assumption on the Frobenius norm

**Assumption 4.6:** Let $M = M(N)$ be a sequence that goes to infinity with $N$. The sequence of random matrices $X_N$ satisfies Assumption 4.6 at speed $M$ if there exists a positive constant $C$ independent of $N$ such that for all $N$,

$$ \mathbb{E} \frac{1}{N} ||X^M||_F^2 \le C^M. \quad (4.12) $$

This is obviously true at any speed for sequences of matrices that are uniformly bounded in operator norm since $\frac{1}{N}||X_N^M||_F^2 \le ||X_N^M||_{op}^2 \le ||X_N||_{op}^{2M} \le C^{2M}$ where $C$ is the bound of the operator norm of $X_N$.

However, this might also hold even though the operator norm of $X_N$ diverges. Take for instance the re-centered re-normalized version of the adjacency matrix of an Erdos-Renyi graph of parameter $p$ with $Np \to \infty$ and $Np/\log N \to 0$ as $N \to \infty$. It is shown in [7] that the largest eigenvalue of $X_N$ diverges. However, developing the trace in the Frobenius norm in term of injective trace and using calculations from the previous subsection we have the expression.

$$ \mathbb{E} \frac{1}{N} \mathrm{Tr}(X^{2M}) = \mathbb{E} \frac{1}{N} \mathrm{Tr}(T_{2M}(X)) = \sum_{\pi \in P(V_{2M})} N^{|V_\pi|-|\bar{E}_\pi|-1} (Np)^{|\bar{E}_\pi|-|E_\pi|/2} (1+o(1)), $$

where the test-graph $T_{2M} = (V_{2M}, E_{2M})$ is a cycle of length $2M$. When the partition $\pi$ makes $T^\pi$ into a double tree, then the contribution is 1. When the partition $\pi$ makes $T^\pi$ a fat tree (i.e. there is some edge with multiplicity at least 4) then the contribution is at most $(Np)^{-1}$ and otherwise the contribution is at most $1/N$. Bounding the number of partition by $2M^{2M}$ we obtain

$$ \mathbb{E} \frac{1}{N} \mathrm{Tr}(X^{2M}) \le C_M + M^M (Np)^{-1} + M^M N^{-1}, $$
where $C_M$ is the M-th Catalan number, i.e. the number of trees with M edges (or double trees with 2M edges). The Catalan number can be bounded by some power of M whereas, taking $M = \log(Np)/\log\log(Np)$, we obtain Equation (4.12).

On the contrary, taking a sparse Erdos-Renyi graph, i.e. $Np \to c > 0$, we would have had a contribution of order 1 for each fat tree and the number of fat trees of size M cannot be bounded by some power of M.

Similarly for diluted Wigner matrices, distinguishing between double trees that have a contribution of 1, fat trees that have at least an edge of multiplicity strictly greater than 2 or other cases, recalling that $\bar{E}_{\pi,2}$ is the set of edges of $\bar{E}_{\pi}$ that have multiplicity exactly 2, we have

$$ \left| \mathbb{E} \frac{1}{N} \mathrm{Tr}(T_{2M}(X)) \right| \le \sum_{\pi \in P(V_{2M})} N^{|V_{\pi}| - |\bar{E}_{\pi}| - 1} \frac{\log(N)^{h(|E_{\pi}| - 2|\bar{E}_{\pi,2}|)}}{N^{\varepsilon|(|\bar{E}_{\pi}| - |\bar{E}_{\pi,2}|)|}}, \\ \le C_M + M^M \log(N)^{2hM} N^{-\varepsilon} + M^M \log(N)^{2hM} N^{-1}. $$

Take now $M = \beta \log N/\log\log N$, with $\beta < \frac{\varepsilon}{1+2h}$, only the contribution of $C_M$ remains and we obtain the wanted bound. Hence diluted Wigner matrices satisfy Assumption 4.6 at speed $\beta \log N/\log\log N$ for $\beta$ small enough.

# 5 Proof of the main theorems

## 5.1 Preliminary results

We provide some useful lemmas and notations prior to the proof of Theorems 2.6 and 2.7. The first lemma ensures that when we glue two graphs together while not identifying vertices from a same graph, if we start with a graph that has a graph of colored components which is not a tree, the resulting graph will also have a graph of colored components which is not a tree. Recall from (4.1) that, for a simple connected graph $H = (V, E)$, $\eta(H) := |V| - |E| - 1 \le 0$, and the equality holds if and only if $H$ is a tree.

**Lemma 5.1.** Let $S_1 = (V_1, E_1, \gamma_1, \varepsilon_1)$, $S_2 = (V_2, E_2, \gamma_2, \varepsilon_2)$ be two test graphs labeled by $\{a, b\}$ and let $\sigma$ be an amalgamation between $V_1$ and $V_2$, i.e. a partition of $V_1 \sqcup V_2$ where all the blocks are either of size one, either of size two with one vertex from $V_1$ and one vertex from $V_2$. Assume moreover that $\sigma$ has at least one block of size two (hence $(S_1 \sqcup S_2)^\sigma$ is connected). Then, we have

$$ \eta(\mathcal{G}\mathcal{C}\mathcal{C}((S_1 \sqcup S_2)^\sigma)) \le \min\{\eta(\mathcal{G}\mathcal{C}\mathcal{C}(S_1)), \eta(\mathcal{G}\mathcal{C}\mathcal{C}(S_2))\}. \quad (5.1) $$

*Proof.* The graph $(S_1 \sqcup S_2)^\sigma$ can be obtained by the following process. Start with $G_0 = S_1$. Since $\sigma$ has a block of size two, there is a couple $(v, w) \in V_1 \times V_2$ such that $v \nsim w$. Choose an arbitrary edge adjacent to $w$ in $S_2$: say $e = (w, w')$. If $w'$ is in a block of size one of $\sigma$, add a new vertex $w'$ to $G_0$ and an edge between $v$ and $w'$ with the same label as $e$. Else, if there exists $v' \in V(G_0) = V_1$ such that $v' \nsim w'$, then add an edge in $G_0$ between $v$ and $v'$.
and $v'$ with the same label as $e$. The graph thus obtained is $G_1$. Repeat this process by choosing at step $l$, a new edge $e = (u, u') \in E_2$ that is adjacent to an edge chosen before (i.e. $u$ is a vertex of $G_l$) until there is no more edge in $E_2$. If $k$ denotes the number of edges of $S_2$ then $G_k = (S_1 \sqcup S_2)^\sigma$. We denote $\eta(l) := \eta(\mathcal{G}\mathcal{C}\mathcal{C}(G_l))$ and we show that this quantity does not increase. From Remark 4.1, recall that for any graph $G$ labeled by $A$ and $B$, $\eta(\mathcal{G}\mathcal{C}\mathcal{C}(G)) = |\mathcal{V}_{cc}| - |\mathcal{V}_{co}| - 1$. Hence, in order to keep track of $\eta(l)$ we only need to look at the different type of vertices added at each step.

To go from $G_l$ to $G_{l+1}$ we distinguish two cases. Either we add an edge $e$ (labeled $a$ or $b$) (i)- between two already existing vertices $v_1, v_2$ of $G_l$ or (ii)- between an already existing vertex $v_1$ of $G_l$ and a new vertex $v_2$. In other words, when an edge $(w, w')$ of $S_2$ has its two vertices in blocks of size two of $\sigma$, i.e. $\exists v, v' \in V_1, v \not\sim w, v' \not\sim w'$, then we add an edge between $v$ and $v'$ in $G_l$ otherwise we add a new vertex and a new edge to it.

We write

$$G_l = \bigsqcup_{i=1}^{I} T_i^{l,a} \cup \bigsqcup_{j=1}^{J} T_j^{l,b},$$

where the $T_i^{l,a}$ are the disjoint colored components labeled by $a$ of $G_l$ and the $T_j^{l,b}$ are the disjoint colored components labeled by $b$ of $G_l$. We write $V_i^{l,a}$ the set of vertices of $T_i^{l,a}$ (and similarly for $b$). For $i \in I$, we write $V_i^{\circ, l,a} \subset V_i^{l,a}$ the subset of vertices $v \in V_i^{l,a}$ that only have adjacent edges labeled $a$ and similarly for $b$.

Let $0 \le l \le k-1$ us assume that $\eta(l) \le \eta(0) = \eta(S_1)$ and, without loss of generality, let us assume that the new edge $e = (v, w')$ we add is labeled $a$ (recall that $v$ is a vertex of $G_l$). If we are in the first scenario, let $v' \in V_1 \subset V(G_l)$ be such that $v' \not\sim w'$, we add an edge labeled $a$ between $v$ and $v'$.

1. If $v \in V_i^{l,a}$ and $v' \in V_i^{l,a}$, adding an edge labeled $a$ between $v$ and $v'$ does not change the graph of colored components since they are already in the same colored component (with labels $a$), hence $\eta(l+1) = \eta(l)$. Note that it does not matter whether $v$ or $v'$ are connectors or not.

2. If $v \in V_{i_1}^{l,a}$ and $v' \in V_{i_2}^{l,a}$ with $i_1 \neq i_2$. Adding an edge between $v$ and $v'$ will merge the colored components $T_{i_1}^{l,a}$ and $v' \in T_{i_2}^{l,a}$, hence the graph of colored components has one vertex less: $\eta(l+1) = \eta(l) - 1$.

3. If $v \in V_{j_1}^{\circ, l,b}$,

(a) and if $v' \in V_{j_2}^{\circ, l,b}$ for some $j_2 \in J$, in the graph of colored components, we add one vertex of type $cc$ and 2 vertices of type $co$ hence $\eta(l+1) = \eta(l) - 1$;

(b) and if $v' \in V_{j_2}^{l,b} \cap V_i^{l,a}$ for some $j_2 \in J$ and some $i \in I$, in the graph of colored components we add one vertex of type $co$, hence $\eta(l+1) = \eta(l) - 1$;

(c) and if $v' \in V_i^{\circ, l,a}$ for some $i \in I$, in the graph of colored components we also add one vertex of type $co$, hence $\eta(l+1) = \eta(l) - 1$.
If we are in the second scenario: $w'$ is in a block of size one of $\sigma$. There are two cases:

1. either $v \in V_i^{l,a}$ for some $i \in I$, then the graph of colored components does not change, hence $\eta(l+1) = \eta(l)$;

2. or $v \in V_j^{l,b}$ for some $j \in J$, then we add one vertex of type co and one vertex of type cc in the graph of colored components, hence $\eta(l+1) = \eta(l)$.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Examples of the modification of the $GCC$ when adding an edge. The top picture is a detail of the $GCC$ with a blue dashed line representing the edge we add at step $l$ in the graph. The bottom picture is the local change of the $GCC$. Colored squares are vertex from colored components ($a$ is blue, $b$ is red) and gray circles are connectors.</figcaption></figure>

Figure 2 provides several examples of different cases. After exhausting every case, we see that $(\eta(l))_{0 \le l \le k}$ does not increase. Hence $\eta(k) \le \eta(GCC(S_1))$. This construction being symmetric, it concludes the proof. $\square$

We now prove several results concerning the trace and injective trace of graph monomials in terms of $A+B$, $a+b$, $A$ and $B$.

For a graph monomial $h$ labeled by a single variable with $L$ connected components, we define

$$t(h(X)) := \mathbb{E} \frac{1}{N^L} \sum_{\substack{\phi:V_h \to [N], e \in E_h \\ \text{injective}}} \prod_{e \in E_h} X(\phi(e))$$

the quantity appearing in Assumption 4.5.
**Lemma 5.2.** Let A and B be random matrices that verify Assumption 4.5 at speed M with constants $h_1$ and $h_2$. Let g be a graph monomial labeled by a and b with $m \le cM$ vertices and edges and set $\eta := \eta(GCC(g))$. We have the following estimate :

$$ \tau_i^0(g(A, B)) = t(g_a(A))t(g_b(B))N^\eta + O(N^{\eta+c(h_1+h_2)-1}m^2), \quad (5.2) $$

where $g_a$ is the graph monomial obtained from g after deleting all edges labeled b and the isolated vertices and similarly for $g_b$.

The argument is made in [16] for test-graphs with bounded number of edges and vertices but it remains valid in our case. For completeness, we restate it here.

*Proof.* Let $g = (V, E, \gamma, \varepsilon, v_{in} = v_{out})$ be a graph monomial labeled by two formal variables a and b. Moreover since the matrices A and B are hermitian, we can omit $\varepsilon$ and we denote $X^a = A, X^b = B$. First note that since A and B are permutation invariant,

$$ \tau_i^0(g(A, B)) = \frac{1}{N} \sum_{j=1}^{N} \tau_j^0(g(A, B)), $$

hence

$$ \tau_i^0(g(A, B)) = \frac{1}{N} \sum_{\substack{\phi:V \to [N], \\ \phi \text{ injective}}} \mathbb{E} \left[ \prod_{e=(v,w) \in E} X^{\gamma(e)}(\phi(w), \phi(v)) \right] \\ = \frac{(N-1)!}{(N-|V|)!} \mathbb{E}_{\phi_N} \left[ \prod_{e=(v,w) \in E} X^{\gamma(e)}(\phi_N(w), \phi_N(v)) \right], $$

where the expectation is also taken with respect to $\phi_N$, an injective map chosen uniformly among all injective maps from V to [N], independent of A and B. Since the matrices A and B are invariant in law by permutation, we can add another 'layer' of random injective maps for one of these matrices, say B as follows,

$$ \tau_i^0(g(A, B)) = \frac{(N-1)!}{(N-|V|)!} \mathbb{E} \left[ \prod_{e \in E, \gamma(e)=a} A(\phi_N(e)) \prod_{e \in E, \gamma(e)=b} B(\sigma \circ \phi_N(e)) \right], $$

where $\sigma$ is a random uniformly chosen element of $\mathfrak{S}_N$ independent of $(\phi_N, A, B)$. It is not hard to see that $(A, \phi_N)$ is independent from $(B, \sigma \circ \phi_N)$ and that $\sigma \circ \phi_N$ has same law as $\phi_N$. Hence we can separate the contribution from A and from B. Let $g_a = (V_a, E_a)$, resp. $g_b = (V_b, E_b)$, be the graph monomial obtained from g by keeping the edges labeled a, resp. b and then deleting the isolated vertices. Denote $K_a$, resp. $K_b$ the number of connected components of $g_a$, resp. $g_b$. We now have

$$ \tau_i^0(g(A, B)) = \frac{(N-1)!}{(N-|V|)!} \mathbb{E} \left[ \prod_{e \in E_a} A(\phi_N(e)) \right] \mathbb{E} \left[ \prod_{e \in E_b} B(\phi_N(e)) \right] \\ = \frac{(N-|V_a|)!(N-|V_b|)!}{(N-|V|)!(N-1)!} N^{K_a-1} N^{K_b-1} t(g_a(A))t(g_b(B)). $$
In order to use the second point of Lemma A.1, we only have to verify that $\eta := K_a(N) + K_b(N) - 1 - |V_a| - |V_b| + |V|$ is non positive. Recall that the graph of colored components $\mathcal{G}\mathcal{C}\mathcal{C}(S) := (\mathcal{V}, \mathcal{E})$ of $S$ has two type of vertices. The first type are the colored components: there are $K_a(N) + K_b(N)$ of them. The second type are the vertices from $S$ that belong to both a colored component in $a$ and a colored component in $b$, there are $|V_a \cap V_b|$ of them. Hence $|\mathcal{V}| = K_a(N) + K_b(N) + |V_a \cap V_b|$. Moreover, for each vertex of the second type, there are two corresponding edges in the graph of colored component, hence $|\mathcal{E}| = 2|V_a \cap V_b|$. Finally, noting that $|V| - |V_a| - |V_b| = -|V_a \cap V_b|$, we see that $\eta = |\mathcal{V}| - |\mathcal{E}| - 1$. Using Equation (4.1), we obtain $\eta \le 0$ with equality if and only if $\mathcal{G}\mathcal{C}\mathcal{C}(S)$ is a tree.

Finally, we get that

$$ \tau_i^0(g(A, B)) = N^\eta t(g_a(A))t(g_b(B)) \left(1 + O\left(\frac{m^2}{N}\right)\right), $$

which concludes the proof using Assumption 4.5. $\square$

We now compute the injective traffic distribution of the operators $a$ and $b$ in terms of injective distribution of the matrices $A$ and $B$. We denote $G_N = (V_N, E_N, \gamma_N, \rho)$ the underlying $\rho$-rooted, labeled graph defined in Section 3, where $\rho \in [N]$ and where there is an edge between $v$ and $w$ if $\langle a\delta_v, \delta_w \rangle \neq 0$ (then $\gamma_N((v, w)) = a$) or $\langle b\delta_v, \delta_w \rangle \neq 0$ (then $\gamma_N((v, w)) = b$). Let $g = (V, E, \gamma, \varepsilon, v_{in}, v_{out})$ be a graph monomial labeled by two formal variables $a$ and $b$. Moreover since the matrices $A$ and $B$ are Hermitian, we can omit $\varepsilon$. It is easy to see that if $g$ has a $\mathcal{G}\mathcal{C}\mathcal{C}$ with respect to the families $a$ and $b$ that is not a tree, then there is no injective labeled graph morphism from $g$ to $G_N$, otherwise the graph of colored component of $G_N$ would not be a tree.

We denote

$$ \begin{gathered} \Phi:V_N \to [N] \\ \rho \mapsto \rho, \\ (j_1, \dots, j_n, \star) \mapsto j_n, \end{gathered} \qquad (5.3) $$

where $\star$ stands for $a$ or $b$. The map $\Phi$ induces a labeled graph morphism from $G_N$ to the complete graph with $N$ vertices associated to the matrices $A$ and $B$ by keeping the labels as they are.

**Lemma 5.3.** Let $g$ be a graph monomial with $v_{in} = v_{out}$ and such that its $\mathcal{G}\mathcal{C}\mathcal{C}$ is a tree. There is a bijection between the set of injective graph morphisms from $g$ to $G_N$ and maps from $V$ to $[N]$ that are injective on each colored components of $g$. This bijection is induced by the map $\Phi$.

*Proof.* Let $\phi: V \to V_N$ be an injective graph morphism. The map $\Phi \circ \phi: V \to [N]$ is injective on each colored component of $g$. Indeed, let $S$ be a colored component, say of color $a$, of $g$. Since $\phi$ is an injective morphism, its image via $\phi$ is a subgraph of some
$R_a(v) = \{(j_1, \dots, j_n, b)\} \sqcup \{(j_1, \dots, j_{n+1}, a), j_{n+1} \in [N] \setminus \{j_n\}\}$ (see Section 3). Since $\Phi$ is injective on $R_a(v)$, $\Phi \circ \phi$ is injective on $S$.

Let now $\psi: V \to [N]$ be injective on each colored component of $g$ and denote $CC(g)$ the set of colored components of $g$. We define a function $h: CC(g) \to \mathbb{N}_{>0}$ which is a slight deformation of the graph-distance on $GCC(g)$ as follows,

$$h(S) = \begin{cases} \frac{1}{2}(d_{GCC}(S, v_{in}) + 1) & \text{if } v_{in} \in \mathcal{V}_{co}, \\ \frac{1}{2}d_{GCC}(S_{in}, S) + 1, & \text{if } v_{in} \in \mathcal{S}_{in}^{\circ}, \end{cases} \quad (5.4)$$

where $\mathcal{S}_{in}^{\circ}$ is the set of vertices of $S_{in}$ that are not connectors. Note that $h(S)$ is indeed a natural number and that if $v_{in} \in S$, $h(S) = 1$. Moreover, $h$ induces a function, still denoted $h$ on $V$, by taking $h(v_{in}) = 0$ and $h(v) = \min\{h(S), S \ni v\}$ otherwise. Finally, for $v \neq v_{in}$ denote $c(v) \in \{a, b\}$, the color of the colored component that realizes the minimum, i.e. the color that gets $v$ closer to $v_{in}$. Since $GCC(g)$ is a tree, for any vertex $v \neq v_{in}$, there exists a unique path $v_{in} = v_0, v_1, \dots, v_{h(v)-1}, v_{h(v)} = v$ such that for all $1 \le i \le h(v)$, the vertices $v_{i-1}$ and $v_i$ belong to the same colored component, they are all connectors except possibly $v_{in}$ and $v$ and $h(v_i) = i$. Denote $(j_1, \dots, j_{h(v)}) = (\psi(v_1), \dots, \psi(v_{h(v)}))$ and define $\phi: V \to V_N$ by $\phi(v_{in}) = \rho$ and $\phi(v) = (j_1, \dots, j_{h(v)}, c(v))$. This is well defined since $\psi$ is injective on each colored component and $v_{i-1}, v_i$ belong to the same colored component and are two distinct vertices, we have $j_{i-1} \neq j_i$. Moreover, $\phi$ induces a graph morphism. Indeed, for any edge $e = (v, w)$, either $v = w$ and it is clear that $(\phi(v), \phi(w))$ is a n edge of $G_N$, either $v \neq w$. In that last case, since they are in the same colored component, $\phi(v)$ and $\phi(w)$ are both in the same colored component in $G_N$, hence $(\phi(v), \phi(w))$ is indeed an edge of $G_N$. Finally $\phi$ is injective : if $(\psi(v_1), \dots, \psi(v), c(v)) = (\psi(w_1), \dots, \psi(w), c(w))$, then $v$ and $w$ are in the same colored component and using the injectivity of $\psi$ on this colored component, we recursively show that $v = w$. $\square$

Recall that a partition $\sigma$ of the vertices of a graph monomial $g$ is said to be an amalgamation between the colored components, written $\sigma \in P_{\#}(CC(g))$, if the blocs of $\sigma$ contain at most one vertex from each colored components. In other words, it may identify vertices from different colored components but never two vertices of the same one. We denote 1 the special amalgamation consisting in only singletons. For any partition of the vertices of a graph monomial, recall that we denote $g^{\sigma}$ the graph monomial obtained after identifying vertices in a same block.

**Lemma 5.4.** Let A and B be random matrices and a, b the associated operators constructed in Section 3. Let g be a graph monomial labeled in two variables such that its $GCC$ is a tree. We have

$$\mathrm{Tr}_{\rho}^{0}(g(a, b)) = \mathrm{Tr}_{\rho}^{0}(g(A, B)) + \sum_{\substack{\sigma \in P_{\#}(CC(g)), \\ \sigma \neq 1}} \mathrm{Tr}_{\rho}^{0}(g^{\sigma}(A, B)). \quad (5.5)$$
Proof. With the definition of Φ and recalling that the operators a and b are defined through the last index of the vertex, we have

$$
\mathrm{Tr}_{\rho}^{0}(g(a, b)) = \sum_{\substack{\phi: V \to V_N, \\ \text{injective graph morphism,} \\ \phi(v_{in}) = \rho}} \prod_{e \in E} X^{\gamma(e)}(\Phi(\phi(e))),
$$

where $X^a = A$ and $X^b = B$. Using Lemma 5.3 we have

$$
\mathrm{Tr}_{\rho}^{0}(g(a, b)) = \sum_{\phi} \prod_{e \in E} X^{\gamma(e)}(\phi(e)),
$$

where the sum over $\phi$ now runs through all maps $\phi : V \to [N]$ that are injective on each colored component and such that $\phi(v_{in}) = \rho$.

A map $\phi : V \to [N]$ injective on each colored component can be seen as an injective map $\psi : V^\sigma \to [N]$ where $\sigma(i) \sim \sigma(j) \Leftrightarrow \phi(i) = \phi(j)$, is an amalgamation of the colored components of $g$. Hence

$$
\begin{align*}
\mathrm{Tr}_{\rho}^{0}(g(a, b)) &= \sum_{\sigma \in P_{\#}(CC(g))} \sum_{\substack{\psi: V^{\sigma} \to [N], \\ \text{injective,} \\ \psi(v_{in}) = \rho}} \prod_{e \in E} X^{\gamma(e)}(\phi(e)), \\
&= \sum_{\sigma \in P_{\#}(CC(g))} \mathrm{Tr}_{\rho}^{0}(g^{\sigma}(A, B))
\end{align*}
$$

The special case $\sigma = 1 = \{\{v_1\}, \dots, \{v_m\}\}$ does not change $g$ and we get the result.

<figure><img src="image_4.png" /></figure>

**Corollary 5.5.** Let $m \le cM$, let $A$ and $B$ be two matrices that satisfy Assumption 4.5 at speed $M$, then

$$
\langle (a+b)^m \delta_{\rho}, \delta_{\rho} \rangle - (A+B)_{\rho,\rho}^m = O(2^m m^{2m} N^{c(h_1+h_2)-1}). \quad (5.6)
$$

Proof. For $f : [m] \to \{a, b\}$, call $g_f$ the graph monomial which is a directed cycle whose edges are labeled by $f$ along the cycle. Expanding the moment by multi-linearity on the edges, we obtain

$$
\begin{align*}
\langle (a+b)^m \delta_{\rho}, \delta_{\rho} \rangle &= \sum_{f:\{m\} \to \{a,b\}} \sum_{\substack{\pi \in P(g_f), \\ \mathrm{G}\mathrm{C}\mathrm{C}(g_f^{\pi})=\mathrm{tree}}} \mathrm{Tr}_{\rho}^{0}(g_f^{\pi}(a,b)), \\
&= \sum_{f:\{m\} \to \{a,b\}} \sum_{\substack{\pi \in P(g_f), \\ \mathrm{G}\mathrm{C}\mathrm{C}(g_f^{\pi})=\mathrm{tree}}} [\mathrm{Tr}_{\rho}^{0}(g_f^{\pi}(A,B))] + \sum_{\substack{\sigma \in P_{\#}(\mathrm{CC}(g_f^{\pi})), \\ \sigma \neq 1}} \mathrm{Tr}_{\rho}^{0}((g_f^{\pi})^{\sigma}(A,B)).
\end{align*}
$$
Hence, the left-hand side on Equation (5.6) is equal to

$$ \sum_{f:\{m\} \to \{a,b\}} \left( \sum_{\substack{\pi \in P(g_f), \\ \mathrm{GCC}(g_f^\pi) = \mathrm{tree}}} \sum_{\substack{\sigma \in P_\#(\mathrm{CC}(g_f^\pi)), \\ \sigma \neq 1}} \mathrm{Tr}_\rho^0((g_f^\pi)^\sigma(A, B)) - \sum_{\substack{\pi \in P(g_f), \\ \mathrm{GCC}(g_f^\pi) \neq \mathrm{tree}}} \mathrm{Tr}_\rho^0(g_f^\pi(A, B)) \right). $$

Bound now each injective trace by $N^{c(h_1+h_2)}N^\eta$ using Assumption 4.5 and Lemma 5.2. Since we are only summing over partitions that have their graph of colored components that are not trees, we have $\eta \le -1$ for each term. Bounding the number of partition we are summing over by $m^m$, we obtain Equation (5.6). $\square$

## 5.2 Proof of Theorem 2.6

Throughout the proof, we write $G_{A+B}(z) := G_{A+B}(zI)$ and similarly for $G_{a+b}$. Let $(\mathcal{A}, \mathcal{D}_N(\mathbb{C}), E)$, be a $C^*$-probability space, let $X \in \mathcal{A}$ be self-adjoint and let $z \in \mathbb{C}$ be a complex number with strictly positive imaginary part. We choose $M$ the minimum speed at which the matrices $A$ and $B$ satisfy Assumptions 4.5 and 4.6 and set $c > 0$ to be chosen later. We have the identity

$$ G_X(z) = E((z - X)^{-1}) = \sum_{n=0}^{cM-1} \frac{1}{z^{n+1}} E(X^n) + \frac{1}{z^{cM}} E(X^{cM}(z - X)^{-1}). \quad (5.7) $$

We call $I_X^M(z)$ the first term and $R_X^M(z)$ the second on the right-hand side of the above equality. We apply this result to $X = A+B$ with $E = \Delta$ and to $X = a+b$ with $E = E_{\mathcal{D}_N(\mathbb{C})}$ defined in Section 2. We first expand the norm of $I^M(z) := I_{a+b}^M(z) - I_{A+B}^M(z)$ as follows

$$ \begin{aligned} \|I^M(z)\|_F^2 = & \sum_{\rho=1}^{N} \sum_{n,m=0}^{cM-1} \frac{1}{z^{m+1}\bar{z}^{n+1}} (\langle g_m(a+b)\delta_\rho, \delta_\rho \rangle - g_m(A+B)_{\rho,\rho}) \times \\ & (\langle g_n(a+b)\delta_\rho, \delta_\rho \rangle - g_n(A+B)_{\rho,\rho}), \end{aligned} \quad (5.8) $$

where $g_m$ denotes an oriented cycle of length $m$ labeled by a single variable. Hence $\mathrm{Tr} g_m(X) = \mathrm{Tr} X^m$. We reproduce the proof of Corollary 5.5 to obtain

$$ \begin{aligned} \langle g_m(a+b)\delta_\rho, \delta_\rho \rangle - g_m(A+B)_{\rho,\rho} = & \sum_{f_1:\{m\} \to \{a,b\}} \sum_{\substack{\pi_1 \in P(g_{f_1}), \\ \mathrm{GCC}(g_{f_1}^\pi) = \mathrm{tree}}} \sum_{\substack{\sigma_1 \in P_\#(\mathrm{CC}(g_{f_1}^\pi)), \\ \sigma_1 \neq 1}} \mathrm{Tr}_\rho^0((g_{f_1}^{\pi_1})^{\sigma_1}(A, B)) \\ & - \sum_{\substack{\pi_1 \in P(g_{f_1}), \\ \mathrm{GCC}(g_{f_1}^\pi) \neq \mathrm{tree}}} \mathrm{Tr}_\rho^0(g_{f_1}^{\pi_1}(A, B)), \end{aligned} \quad (5.9) $$

and similarly for the $n$-th moment replacing all 1 subscripts by 2's. Note that for any $\pi_1, \sigma_1$ in the last sums, the graph of colored components of $(g_{f_1}^{\pi_1})^{\sigma_1}$ is not a tree, hence
$\eta(\mathcal{G}\mathcal{C}( (g_{f_1}^{\pi_1})^{\sigma_1})) \leq -1$. Hence when expanding the product in Equation (5.8), we will have a sum of expressions of the form

$$ \mathrm{Tr}_{\rho}^{0}(h(A, B)) \mathrm{Tr}_{\rho}^{0}(h'(A, B)), $$

for some graph monomials $h, h'$ that have their graph of colored components which is not a tree and have the same input and output vertex. We express this product as a sum of injective trace of some modified graph monomial. Set $h \cdot h'$ the graph monomial obtained after identifying the input vertex of $h$ with that of $h'$, so that we have

$$ \mathrm{Tr}_{\rho}^{0}(h(A, B)) \mathrm{Tr}_{\rho}^{0}(h'(A, B)) = \sum_{\sigma \in P_{\#}(h, h')} \mathrm{Tr}_{\rho}^{0}((h \cdot h')^{\sigma}(A, B)). $$

Using Lemma 5.1, we know that $\eta(\mathcal{G}\mathcal{C}((h \cdot h')^{\sigma})) \leq -1$. We use Lemma 5.2 to bound the expectation of each injective trace that appear in the sums by $N^{c(h_1+h_2)-1}$. Finally, we bound the number of partitions of a set with $k$ elements by $k^k$ and we obtain

$$ \begin{aligned} \mathbb{E}||I^M(z)||_F^2 &\leq \sum_{\rho=1}^{N} \sum_{n,m=0}^{cM-1} \sum_{\substack{f_1:[m]\to\{a,b\}, \\ f_2[n]\to\{a,b\}}} \frac{1}{|z|^{n+m+2}} n^{2n} m^{2m} (n+m)^{n+m} N^{c(h_1+h_2)-1}, \\ &\leq \frac{N}{|z|^2} \left( \sum_{m=0}^{cM-1} \left( \frac{2(cM)^3}{|z|} \right)^m \right)^2 N^{c(h_1+h_2)-1}, \\ &\leq \frac{4N}{|z|^2} \left( \frac{2c^3}{|z|} \right)^{2cM} M^{6cM} N^{c(h_1+h_2)-1}, \end{aligned} $$

where for the last line, we bounded each term in the sum by $(\frac{2(cM)^3}{|z|})^{cM-1}$ which is valid for $M$ large enough, hence $N$ large enough. Using $M^{6cM} \leq N^{6c}$, we have for $|z| \geq 2c^3$,

$$ \mathbb{E} \frac{1}{N} ||I^M(z)||_F^2 \leq \frac{1}{|z|^2} N^{c(h_1+h_2+6)-1} e^{2cM \log(2c^3/|z|)}. \quad (5.10) $$

We now bound the norm of $R_{A+B}^M(z)$. Recall that the Fröbenius norm is the Schatten-2 norm and that the operator norm is the Schatten-$\infty$ norm. Hölder's inequality on Schatten norms yields

$$ ||R_{A+B}^M(z)||_F \leq \frac{1}{|z|^{cM}} ||(A+B)^{cM}||_F ||(z-A-B)^{-1}||_{op}. $$

Since $A$ and $B$ are Hermitian, denoting $||X||_p := \mathrm{Tr}((XX^*)^p)^{1/2p}$ the Schatten $p$-norm of a matrix $X$ and using Minkowski's inequality, then Hölder's inequality, we have

$$ \begin{aligned} ||(A+B)^{cM}||_F^2 &= ||A+B||_{cM}^{2cM} \leq (||A||_{cM} + ||B||_{cM})^{2cM}, \\ &\leq (||A^{cM}||_F^{1/cM} + ||B^{cM}||_F^{1/cM})^{2cM}, \\ &\leq 2^{2cM-1} (||A^{cM}||_F^2 + ||B^{cM}||_F^2). \end{aligned} $$
Since A and B satisfy Assumption 4.6 at speed cM with constant C, we finally obtain

$$ \mathbb{E} \frac{1}{N} \| R_{A+B}^{M}(z) \|_{F}^{2} \leq \left( \frac{4C}{|z|^{2}} \right)^{cM} \frac{1}{|\mathrm{Im}(z)|^{2}}. \qquad (5.11) $$

To estimate $R_{a+b}^M(z)$, recall from the end of Section 3 that $\varphi: \mathcal{A} \to \mathbb{C}$, $T \mapsto \frac{1}{N} \sum_{v \in R_a(x)} \langle T \delta_v, \delta_v \rangle$, is positive and makes $(\mathcal{A}, \varphi)$ into a $C^*$-probability space. Moreover, setting $x := (z - a - b)^{-1}(a + b)^{cM}$ we can write

$$ \frac{1}{N} \| R_{a+b}^{M}(z) \|_{F}^{2} = \frac{1}{|z|^{2cM}} \varphi(E_{\mathcal{D}_{N}(\mathbb{C})}(x) E_{\mathcal{D}_{N}(\mathbb{C})}(x)^{*}) \leq \frac{1}{|z|^{2cM}} \varphi(xx^{*}), $$

where we used that $E_{\mathcal{D}_{N}(\mathbb{C})}$ is a $*$-homomorphism and is also a projection: one may compute explicitly $\langle x\delta_v, x\delta_v \rangle = \langle (x - p(x) + p(x))\delta_v, (x - p(x) + p(x))\delta_v \rangle$ for any $*$-homomorphism $p$ which is also a projection to obtain the inequality above. Now, since $a+b$ is self-adjoint, there exists a compactly supported measure $\mu$ such that

$$ \varphi(xx^*) = \int (z-t)^{-1} t^{2cM} (\bar{z}-t)^{-1} d\mu(t) \leq \frac{1}{|\mathrm{Im}(z)|^2} \frac{1}{N} \sum_{\rho=1}^{N} \langle (a+b)^{2cM} \delta_{\rho}, \delta_{\rho} \rangle. $$

Using Corollary 5.5, we have,

$$ \begin{aligned} \mathbb{E} \frac{1}{N} \| R_{a+b}^{M}(z) \|_{F}^{2} &\leq \frac{1}{|z|^{2cM} |\mathrm{Im}(z)|^{2}} \left( \frac{1}{N} \|(A+B)^{cM}\|_{F}^{2} + O(2^{cM} (cM)^{2cM} N^{c(h_{1}+h_{2})-1}) \right), \\ &\leq \left( \frac{1}{|z|^{2}} \right)^{cM} \left( \frac{(4C)^{cM}}{|\mathrm{Im}(z)|^{2}} + (2c^{2})^{cM} N^{c(h_{1}+h_{2}+2)-1} \right), \end{aligned} \qquad (5.12) $$

where we used for the last line the fact that A and B satisfy Assumption 4.6 at speed M with constant C and that $M^{2M} \leq N^{2c}$.

Putting everything together, for $0 < c < \frac{1}{h_1+h_2+6}$ - this ensures that the terms with $N^{c(h_1+h_2+p)-1}$ for $p=2$ (Equation (5.12)) and $p=6$ (Equation (5.10)) go to zero faster than the terms in $\alpha^M$ for some constant $0 < \alpha < 1$ (Equations (5.12),(5.11))- and $|z|^2 \geq \max\{4C, 2c^2, 2c^3\} = \max\{4C, 2c^2\} =: r_0^2$, we obtain

$$ \mathbb{E} \frac{1}{N} \| G_{a+b}(z) - G_{A+B}(z) \|_{F}^{2} \leq \frac{4}{|z|^{2}} \left( \frac{r_{0}}{|z|} \right)^{2cM} \qquad (5.13) $$

## 5.3 Proof of Theorem 2.7

Note that Theorem 2.6 already includes sparse bounded matrices. We improve the bound with a slightly different proof. The proof still relies on a moment method but we now show that the moments of $A+B$ and the moments of $a+b$ coincide up to order $\log N$ with high probability.
**Graph-related definitions** Given a graph $G = (V, E)$, we define, for $x, y \in V$, $d_G(x, y)$ to be the length of the shortest path from $x$ to $y$, where the length of a path is its number of edges. In the following, if the graph $G$ is $A+B$ we will simply denote its distance by $d$. Let $x \in V$, $k \in \mathbb{N}$ and denote

$$B_G(x, k) := \{y \in V, d_G(x, y) \le k\}, \quad B_G(k) := \max_{x \in V} \{|B_G(x, k)|\}$$

$$C_G(x, k) := \{y \in V, d_G(x, y) = k\}, \quad C_G(k) := \max_{x \in V} \{|C_G(x, k)|\}.$$

Note that for $C$-sparse matrices, we always have

$$|B_A(x, n)| \le C^n. \qquad (5.14)$$

For $G = A + B$, for all $x \in V = [N]$, we denote

$$R(x) := \max\{k \in \mathbb{N}, \mathcal{G}\mathcal{C}\mathcal{C}(B(x, k)) \text{ is a tree}\}.$$

Finally, we set

$$F_N(n) := \{x \in [N], R(x) \ge n\}.$$

The quantity $R(x)$ has to be thought of as the girth of $x$ with respect to the colored components: it is the maximal radius such that, locally, the ball around $x$ satisfies the condition that its graph of colored components is a tree. For the graph associated to $a+b$ constructed in Section 3, the girth is infinite for all vertices since the graph of colored component is a tree.

**Lemma 5.6.** Let $A_N$ and $B_N$ be $C$-sparse matrices, we have

$$\mathbb{E}(|F_N(\kappa \log N)|) \le (eC^2)^n. \qquad (5.15)$$

*Proof.* Throughout the proof, we let $n$ be an integer smaller than $\kappa \log N$ for some constant $\kappa$ to be chosen later. Notice that

$$\mathbb{E}(|F_N(n)^c|) = \sum_{x=1}^{N} \mathbb{P}(\mathcal{G}\mathcal{C}\mathcal{C}(B(x, n)) \text{ is not a tree}).$$

Let $x_1, x_2 \in [N]$, and $2 \le k, l \le n$ and set

$$f_{2l}^{a \to b}(x_1, x_2, k) := \mathbb{P} \left( \exists \gamma_1, \dots, \gamma_{2l}, \sum_{i=1}^{2l} \ell(\gamma_i) \le k, x_1 \stackrel{a}{\sim} y_1 \stackrel{b}{\sim} \dots \stackrel{a}{\sim} y_{2l-1} \stackrel{b}{\sim} x_2 \right),$$

where $\ell(\gamma)$ is the length (i.e. the number of edges) of the path $\gamma$ in $A+B$ and where the notation $x_1 \stackrel{a}{\sim} y_1 \stackrel{b}{\sim} \dots \stackrel{a}{\sim} y_{2l-1} \stackrel{b}{\sim} x_2$ stands for the condition that the path $\gamma_{2i+1}$ only uses edges from $A \cap B(x, n)$ and links $y_{2i}$ to $y_{2i+1}$, the path $\gamma_{2i}$ only uses edges from $B \cap B(x, n)$ and links $y_{2i-1}$ to $y_{2i}$, such that $\gamma := \coprod \gamma_i$ does not use twice the same edge, with the convention that $y_0 = x_1$ and $y_{2l} = x_2$.
Hence, we obtain

$$ \mathbb{E}(|F_N(n)^c|) \le \sum_{x=1}^{N} \sum_{y \in B(x,n)} \sum_{l=1}^{\lfloor n/2 \rfloor} f_{2l}^{a \to b}(y, y, n). \quad (5.16) $$

Note that we only took into account paths that go through an even number of colored components since a path $\gamma$ of the form $x_1 \stackrel{a}{\sim} y_1 \stackrel{b}{\sim} \cdots \stackrel{b}{\sim} y_{2l-2} \stackrel{a}{\sim} x_2$ can be understood as a path going through $2l$ colored components where the last $\gamma_{2l}$ is empty.

Let us now bound $f_{2l}^{a \to b}(y, y, n)$ recursively in $l$.

For $l=1$, we bound more generally the following quantity:

$$ \begin{aligned} f_2^{a \to b}(x_1, x_2, n) &\le \sum_{k=1}^{n-1} \mathbb{P}[(B_A(x_1, k) \setminus \{x_1\}) \cap (B_B(x_2, n-k) \setminus \{x_2\}) \ne \emptyset] \\ &\le \sum_{k=1}^{n-1} \left(1 - \frac{\binom{N-B_A(x_1,k)+1}{B_B(x_2,n-k)-1}}{\binom{N}{B_B(x_2,n-k)-1}}\right), \end{aligned} $$

where we used the fact that the matrices $A$ and $B$ being permutation invariant, we can conjugate $A$ and $B$ by two independent uniform permutation matrices and obtain the second line.

Since $A$ and $B$ are sparse, the quantity $\frac{|B_A(n)||B_B(n)|}{N}$ goes to 0 as $N$ goes to infinity for $\kappa < (2 \log C)^{-1} s$, see Equation (5.14). Hence, using Stirling's formula, we get

$$ \begin{aligned} f_2^{a \to b}(x_1, x_2, n) &\le \sum_{j=1}^{n-1} \frac{|B_A(x_1, j)||B_B(x_2, n-j)|}{N} + O\left(n\left(\frac{|B_A(n)||B_B(n)|}{N}\right)^2\right) \\ &\le \frac{nC^n}{N} + O\left(\frac{nC^{2n}}{N^2}\right). \end{aligned} $$

We show by induction that

$$ f_{2l}^{a \to b}(x_1, x_2, n) \le \frac{n^{2l-1}C^n}{(2l-1)!N}(1+o(1)). $$

Notice now that for $2l+2 \le n$,

$$ f_{2l+2}^{a \to b}(x_1, x_2, n) \le \sum_{j_1=1}^{n} \sum_{y_1 \in C_A(x_1, j_1)} \sum_{j_2=1}^{n-j_1} \sum_{y_2 \in C_B(x_2, j_2)} f_{2l}^{a \to b}(y_2, y_1, n-j_1-j_2). $$

Hence, using the induction hypothesis, we get

$$ \begin{aligned} f_{2l+2}^{a \to b}(x_1, x_2, n) &\le \sum_{j_1+j_2 \le n} C^{j_1} C^{j_2} \frac{(n-j_1-j_2)^{2l-1} C^{n-j_1-j_2}}{(2l-1)!N} (1+o(1)), \\ &\le \frac{n^{2l+1} C^n}{(2l+1)!N} (1+o(1)), \end{aligned} $$
where we used the fact that

$$
\begin{align*}
\sum_{i+j \le n} (i+j)^{2l-1} &= n^{2l+1} \frac{1}{n^2} \sum_{(i+j)/n \le 1} \left(\frac{i+j}{n}\right)^{2l-1} \\
&= n^{2l+1} \int_{0 \le x+y \le 1} (1-(x+y))^{2l-1} dx dy (1+o(1)), \\
&= \frac{n^{2l+1}}{2l(2l+1)} (1+o(1)).
\end{align*}
$$

Going back to Equation 5.16, we have

$$
\mathbb{E} (|F_N(n)^c|) \le \sum_{x=1}^{N} \sum_{y \in B(x,n)} \sum_{l=1}^{\lfloor n/2 \rfloor} \frac{n^{2l-1} C^n}{(2l-1)!N} \le \sum_{x=1}^{N} \sum_{y \in B(x,n)} \frac{e^n C^n}{N} \le (eC^2)^n.
$$

<figure><img src="image_5.png" /></figure>

Proof of Theorem 2.7. Let $0 < \kappa < 1/2$ to be chosen later, let $\eta_0$ and $D$ as in Theorem 2.7. Writing $\tilde{A} = D^{-1/2}AD^{-1/2}$ and $\tilde{B} = D^{-1/2}BD^{-1/2}$, we obtain

$$
G_{A+B}(D)_{i,i} = D_{i,i}^{-1} \sum_{n=0}^{\infty} (\tilde{A} + \tilde{B})_{i,i}^{n} = D_{i,i}^{-1} \sum_{n=0}^{\kappa \log N} (\tilde{A} + \tilde{B})_{i,i}^{n} + D_{i,i}^{-1} \sum_{n=\kappa \log N}^{\infty} (\tilde{A} + \tilde{B})_{i,i}^{n}.
$$

The last term on the right-hand side is bounded as follows

$$
\left| D_{i,i}^{-1} \sum_{n=\kappa \log N}^{\infty} (\tilde{A} + \tilde{B})_{i,i}^{n} \right| &\le \frac{\left( \frac{\|A\|_{op} + \|B\|_{op}}{d} \right)^{\kappa \log N}}{d - \|A\|_{op} - \|B\|_{op}}, \\
&\le \frac{1}{d} N^{\kappa \log \left( \frac{2C}{d} \right)},
$$

where we recall that $d := \inf\{|\mathrm{Im}D_{i,i}|, 1 \le i \le N\}$. The same goes for $G_{a+b}(D)$ since the operator norms of $a$ and $b$ are the same as those of $A$ and $B$ respectively

Recall from Corollary 3.2, that the operator-valued measure $\mu_{a+b} : \mathcal{D}_N(\mathbb{C})\langle\mathcal{X}\rangle \to \mathcal{D}_N(\mathbb{C})$ describes the law of the free sum over the diagonal of $A$ and $B$. We denote $\overline{a+b} := D^{-1/2}(\overline{a+b})D^{-1/2}$ where $D^{-1/2}$ is to be seen as a diagonal operator through the embedding of diagonal matrices into diagonal operators described in Section 3, and let $\mu_{\overline{a+b}}$ denote the associated operator-valued measure.

Expanding both operator-valued Cauchy transforms, we obtain

$$
\begin{align*}
\mathbb{E} \frac{1}{N} \| G_{A+B}(D) - G_{a+b}(D) \|_F^2 &\le \frac{2}{d^2} \mathbb{E} \frac{1}{N} \sum_{i=1}^N \left| \sum_{n=0}^{\kappa \log N} (\tilde{A} + \tilde{B})_{i,i}^n - \langle (\overline{a+b})^n \delta_i, \delta_i \rangle \right|^2 \\
&\quad + 4 \frac{1}{d^2} N^{2\kappa \log(\frac{2C}{d})}
\end{align*}
$$
Note now that, looking at the proof of Corollary 5.5, $i \in F_N(\kappa \log N) \implies (\tilde{A} + \tilde{B})_{i,i}^n = \langle (\overline{a+b})^n \delta_i, \delta_i \rangle, \forall 1 \le n \le \kappa \log N$. Indeed, Corollary 5.5 is a statement on each realization of $a+b$ and $A+B$ and all the remaining terms are equal to 0 because they are injective trace of graph monomials that have their $GCC$ which is not a tree. Hence we have,

$$ \begin{aligned} \mathbb{E} \frac{1}{N} ||G_{A+B}(D) - G_{a+b}(D)||_F^2 & \le \frac{2}{d^2} \mathbb{E} \left[ \frac{|F_N(\kappa \log N)|^c}{N} \left( \frac{||A||_{op} + ||B||_{op}}{d} \right)^{2\kappa \log N} \right] \\ & \qquad + 4 \frac{1}{d^2} N^{2\kappa \log(\frac{2C}{d})}, \\ & \le \frac{2}{d^2} N^{\kappa \log(eC^2) - 1 + 2\kappa \log(\frac{2C}{d})} + 4 \frac{1}{d^2} N^{2\kappa \log(\frac{2C}{d})}, \end{aligned} $$

where the last inequality comes from Lemma 5.6. Taking $\kappa = \frac{1}{1+2\log C} < 1/2$, we obtain the wanted bound. □

## A An asymptotic development

**Lemma A.1 (Two asymptotic developments).**
$N$ such that $|V|^2/N \to 0$ as $N \to \infty$.

1. Let $V$ be a set of size dependent on

$$ \frac{N!}{(N - |V|)!} = N^{|V|} \left( 1 + O\left( \frac{|V|^2}{N} \right) \right). $$

2. Let $V, V_1, V_2$ be sets of size dependent on $N$ and $K_1, K_2$ be numbers also dependent on $N$ with the following conditions:

* We have the inclusions $V_1, V_2 \subset V$ and we denote $\delta V := V_1 \cap V_2$.

* The ratio $|V|^2/N$ goes to 0 as $N$ goes to infinity (hence it is also true for $V_1$ and $V_2$ instead of $V$).

* The quantity $\eta := K_1 + K_2 - 1 - |V_1| - |V_2| + |V|$ is non positive.

Then, we have

$$ \Gamma_N := N \frac{(N - |V_1|)!(N - |V_2|)!}{(N - |V|)!N!} N^{K_1 - 1} N^{K_2 - 1} = N^{\eta} \left( 1 + O\left( \frac{|V|^2}{N} \right) \right) $$
Proof. For the first part, we use Stirling’s equivalent formula:

$$
\begin{align*}
\frac{N!}{(N - |V|)!} &= \frac{N^N e^{N - |V|}}{(N - |V|)^{N - |V|} e^N} \left(1 - \frac{|V|}{N}\right)^{-1/2} \left(1 + O\left(\frac{1}{N}\right)\right), \\
&= N^{|V|} \exp\left(-\left(N - |V| + \frac{1}{2}\right) \log\left(1 - \frac{|V|}{N}\right) - |V|\right) \left(1 + O\left(\frac{1}{N}\right)\right), \\
&= N^{|V|} \exp\left(-\frac{|V|^2}{N} + \frac{|V|}{2N} + \frac{|V|^2}{2N} + O\left(\frac{|V|^3}{N^2}\right)\right) \left(1 + O\left(\frac{1}{N}\right)\right), \\
&= N^{|V|} \left(1 + O\left(\frac{|V|^2}{N}\right)\right),
\end{align*}
$$

where the asymptotic development in the exponential is valid since all the terms are of the
form $\frac{|V|^{k+1}}{N^k}$ which goes to 0 as $N$ goes to infinity by assumption. For the second point, we
note that we already proved that

$$
f_{\pm}(V) := \exp \left( \pm \left[ \left( N - |V| + \frac{1}{2} \right) \log \left( 1 - \frac{|V|}{N} \right) + |V| \right] \right) = 1 + O \left( \frac{|V|^2}{N} \right),
$$

and similarly for $V_1, V_2$ since they all verify the assumptions of the first point. Again, using
the asymptotic development of the factorial, we get

$$
\begin{align*}
\Gamma_N &= N^\eta \frac{\left(1 - \frac{|V_1|}{N}\right)^{N-|V_1|+1/2} \left(1 - \frac{|V_2|}{N}\right)^{N-|V_2|+1/2}}{\left(1 - \frac{|V|}{N}\right)^{N-|V|+1/2}} e^{|V_1|+|V_2| - |V|} \left(1 + O\left(\frac{1}{N}\right)\right), \\
&= N^\eta f_+(V_1) f_+(V_2) f_-(V) \left(1 + O\left(\frac{1}{N}\right)\right) = N^\eta \left(1 + O\left(\frac{|V|^2}{N}\right)\right).
\end{align*}
$$

<figure><img src="image_6.png" /></figure>

References

[1] Benson Au, Guillaume Cébron, Antoine Dahlqvist, Franck Gabriel, and Camille Male. Large permutation invariant random matrices are asymptotically free over the diagonal. *Ann. Probab.*, 49(1), January 2021.

[2] Zhigang Bao, László Erdos, and Kevin Schnelli. Convergence rate for spectral distribution of addition of random matrices. *Advances in Mathematics*, 319:251–291, October 2017.

[3] Zhigang Bao, László Erdos, and Kevin Schnelli. Local law of addition of random matrices on optimal scale. *Commun. Math. Phys.*, 349(3):947–990, February 2017. arXiv:1509.07080 [math].
[4] Roland Bauerschmidt, Jiaoyang Huang, and Horng-Tzer Yau. Local Kesten–McKay law for random regular graphs. *Commun. Math. Phys.*, 369(2):523–636, July 2019. arXiv:1609.09052 [math].

[5] Roland Bauerschmidt, Antti Knowles, and Horng-Tzer Yau. Local semicircle law for random regular graphs. *Comm Pure Appl Math*, 70(10):1898–1960, October 2017. arXiv:1503.08702 [math].

[6] S. T. Belinschi, M. Popa, and V. Vinnikov. Infinite divisibility and a non-commutative Boolean-to-free Bercovici–Pata bijection. *Journal of Functional Analysis*, 262(1):94–123, January 2012.

[7] Florent Benaych-Georges, Charles Bordenave, and Antti Knowles. Largest eigenvalues of sparse inhomogeneous Erdos–Rényi graphs. *Ann. Probab.*, 47(3), May 2019.

[8] Sourav Chatterjee. Concentration of Haar measures, with an application to random matrices. *Journal of Functional Analysis*, 245(2):379–389, April 2007.

[9] John B. Conway. *A course in operator theory*, volume 21 of *Grad. Stud. Math*. Providence, RI: American Mathematical Society, 2000. ISSN: 1065-7338.

[10] László Erdos, Antti Knowles, Horng-Tzer Yau, and Jun Yin. Spectral statistics of Erdos–Rényi graphs I: Local semicircle law. *Ann. Probab.*, 41(3B):2279–2375, May 2013.

[11] Alice Guionnet. *Large Random Matrices: Lectures on Macroscopic Asymptotics: École d'Été de Probabilités de Saint-Flour XXXVI - 2006*, volume 1957 of *Lecture Notes in Mathematics*. Springer, Berlin, Heidelberg, 2009.

[12] Jiaoyang Huang and Horng-Tzer Yau. Spectrum of random d-regular graphs up to the edge. *Comm Pure Appl Math*, 77(3):1635–1723, 2024.

[13] Vladislav Kargin. A concentration inequality and a local law for the sum of two random matrices. *Probab. Theory Relat. Fields*, 154(3):677–702, December 2012.

[14] Vladislav Kargin. Subordination for the sum of two random matrices. *Ann. Probab.*, 43(4):2119–2150, 2015.

[15] Camille Male. The limiting distributions of large heavy wigner and arbitrary random matrices. *Journal of Functional Analysis*, 272(1):1–46, 2017.

[16] Camille Male. *Traffic Distributions and Independence: Permutation Invariant Random Matrices and the Three Notions of Independence*, volume 267 of *Memoirs of the American Mathematical Society*. American Mathematical Society, September 2020.

[17] James A. Mingo and Roland Speicher. *Free Probability and Random Matrices*, volume 35 of *Fields Institute Monographs*. Springer, New York, NY, 2017.
[18] Alexandru Nica and Roland Speicher. *Lectures on the combinatorics of free probability*, volume 335 of *Lond. Math. Soc. Lect. Note Ser*. Cambridge: Cambridge University Press, 2006.

[19] Mihai Popa and Victor Vinnikov. Non-commutative functions and the non-commutative free Lévy-Hinčin formula. *Advances in Mathematics*, 236:131-157, March 2013.

[20] Sarah Timhadjelt. Spectral gap of convex combination of a random permutation and a bistochastic matrix, June 2025. arXiv:2310.16434 [math].

[21] Dan Voiculescu. Operations on certain non-commutative operator-valued random variables. In *Recent advances in operator algebras*, pages 243-275. Paris: Société Mathématique de France, 1995.

[22] Dan Voiculescu, Kenneth Dykema, and Alexandru Nica. *Free Random Variables*, volume 1 of *CRM Monograph Series*. American Mathematical Society, Providence, Rhode Island, December 1992.

[23] John D. Williams. Analytic function theory for operator-valued free probability. *Journal für die reine und angewandte Mathematik (Crelles Journal)*, 2017(729):119-149, August 2017.

[24] Inna Zakharevich. A Generalization of Wigner's Law. *Commun. Math. Phys.*, 268:403-414, December 2006.