Return to Answer

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{N}$ times a Wigner matrix of a matrix of rank $1$ and norm $pN$. Thus, your top eigenvalue will concentrate around $pn$ ($\pm O(\sqrt{N}))$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{n}$ times a Wigner matrix of a matrix of rank $1$ and norm $pn$. Thus, your top eigenvalue will concentrate around $pn$ ($\pm O(\sqrt{n}))$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{N}$ times a Wigner matrix of a matrix of rank $1$ and norm $pN$. Thus, your top eigenvalue will concentrate around that value ($\pm O(\sqrt{N})$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{N}$ times a Wigner matrix of a matrix of rank $1$ and norm $pN$. Thus, your top eigenvalue will concentrate around $pn$ ($\pm O(\sqrt{N}))$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

I first did not see that the entries that are not $1$ are uniform on $[0,1]$ (thanks to Will Sawin for pointing this out). What follows is the solution for the case that they ar 0. At the bottom, after the edit, I answer the original question.

CASE 1: only 0/1 entries, no uniform variables.

All depends on what $k$ is. If $k/n^2\to \alpha\in (0,1/2)$, you are essentially dealing with a symmetric matrix whose entries above the diagonal are iid Bernoulli $\{0,1\}$ of parameter (=mean) $p=2\alpha$ and variance $\sigma^2=p(1-p)$. (I will discuss below the difference between your model and the Bernoulli one). Let $X$ be this Bernoulli matrix. Write $X=\sqrt{n} (Y+p/\sqrt{n} 1 1^T)=\sqrt{n} Z$ where the $Y$'s now have mean $0$ and variance $1/n$. It is a standard fact that there is a transition: if $p\leq \sigma$ then the largest eigenvalue of $Z$ concentrates at $2\sigma$. If $p>\sigma$ then it concentrates at $p+\sigma^2/p$. Fluctuation results are also known, see https://arxiv.org/pdf/math/0605624v1.pdf

Note that your model is sandwiched whp between $p_-=p-K/\sqrt{n}$ and $p_+=p+K/\sqrt{n}$, for $K$ large with probability $\epsilon(K)\to_{K\to\infty}0$, so your model behaves the same (up to multiplication by $\sqrt{n}$ and shift by $1$).

If on the other hand $k/n^2\to 0$, you have that the rank 1 perturbation disappears (formally, note that this is the behavior when $p\to 0$ and $p/\sigma^2\to 1$, so $p<\sigma$). But in this case, of course the scaling is not $\sqrt{n}$ but rather $\sqrt{n}\sigma \sim \sqrt{pn}$. This will work as long as $k$ is not too small, I have not checked exactly the threshold, but $k/n\to \infty$ faster than some poly log should work https://arxiv.org/abs/1309.4922

Finally, if $k/n\to 0$, you will have many empty rows and columns, so you need to first erase those. I did not check and am not sure what happens there.

EDIT: CASE 2: the original OP.

Here, the mean of the entries is $q=p+(1-p)/2$ and the variance of the entries is not $p(1-p)$ but rather $p+(1-p)/3 -q^2$. The matrix is never sparse, so no need to single out the case $k/n^2\to 0$.

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{N}$ times a Wigner matrix of a matrix of rank $1$ and norm $pN$. Thus, your top eigenvalue will concentrate around that value ($\pm O(\sqrt{N})$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.