Trace norm of a triangular matrix with only ones above the diagonal

Question

For $n\in\mathbb N^*$, we consider the triangular matrix $$ T_n = \begin{pmatrix} 1 & \cdots & 1 \\ & \ddots & \vdots \\ 0 & & 1 \end{pmatrix} \in M_{n,n}(\mathbb R) \,. $$ The trace norm of $T_n$, that is the sum of the singular values of $T_n$, is denoted by $\|T_n\|_{\text{Tr}}$.

Is it true that $$ \sup_{n\in\mathbb N^*} \Big\{\frac{1}{n}\|T_n\|_{\text{Tr}}\Big\} < \infty \,? $$

---

EDIT

Is it true that $$ \sup_{n\in\mathbb N^*} \Big\{\frac{1}{n\log(n)}\|T_n\|_{\text{Tr}}\Big\} < \infty \,? $$

An equivalent definition of the trace norm is $\|T_n\|_{\text{Tr}}:=\text{Tr}[\sqrt{T_n^T T_n}]$, where the square root $\sqrt{A}$ of a nonnegative matrix $A$ is the only nonnegative matrix such that $\sqrt{A}^2=A$. (And by $A$ nonnegative I mean $⟨u,Au⟩\geq0$ for all vector $u\in\mathbb R^n$).

---

EDIT 2

One can explicitly compute the singular values of $T_n$.

$$T_n^{-1} = \begin{pmatrix} 1 & -1 & & 0 \\ & \ddots & \ddots & \\ & & \ddots & -1 \\ 0 & & & 1 \end{pmatrix} \in M_{n,n}(\mathbb R) \,. $$

The singular values $\sigma_1,\dots,\sigma_n$ of $T_n$ are related to those, $\lambda_1,\dots,\lambda_n$, of $T_n^{-1}$ through $\sigma_j=\lambda_j^{-1}$.

It is easier to compute the singular values of $T_n^{-1}$ because the eigenvalues $\mu_j=\lambda_j^2$ of $$A_n = (T_n^{-1})^* T_n^{-1} = \begin{pmatrix} 1 & -1 & & & 0 \\ -1 & 2 & -1 & & \\ & -1 & \ddots & \ddots & \\ & & \ddots & \ddots & -1 \\ 0 & & & -1 & 2 \end{pmatrix} \,,$$ can be computed explicitly (as for the discrete laplacian).

Eigenvalues of $A_n$

First, $A_n$ is real symmetric, hence it can be diagonalized in an orthonormal basis, and its eigenvalues $\mu_j$ are real. Then using, say, Gershgorin's circle theorem, the eigenvalues are in the interval $[0,4]$.

If $\psi=(\psi_1,\dots,\psi_n)^T$ is an eigenvector of $A_n$ associated with the eigenvalue $\mu$, then \begin{align} \psi_2 & = (1-\mu)\psi_1 & (1) \\ \psi_3 & = (2-\mu)\psi_2 - \psi_1 & (2)\\ & \vdots \\ \psi_{j+2} &= (2-\mu)\psi_{j+1} - \psi_j & (j)\\ & \vdots \\ \psi_n & = (2-\mu)\psi_{n-1} - \psi_{n-2} & (n-1)\\ (2-\mu)\psi_n &= \psi_{n-1} & (n) \end{align} From Eq. $(2)$ to $(n-1)$, one can see that $\psi_j$ is linear, recursive sequence of order two. Since the roots of the polynomial $X^2+(\mu-2)X+1$ are $$\frac{2-\mu\pm i \sqrt{\mu(4-\mu)}}{2}=e^{\pm i\theta}$$ with $\theta\in [0,\pi]$ and $\cos(\theta)=1-\frac{\mu}{2}$, $\psi_j=\Re(a e^{i(j-1)\theta})$ with $a$ a complex number. Up to a (real) normalization factor $\psi_j=\Re(e^{i(\varphi+(j-1)\theta)})$ for some $\varphi\in\mathbb R$.

Using $\mu = 2-e^{i\theta}-e^{-i\theta}$ and Eq.(1) and (n), yields \begin{align} e^{i(\varphi+\theta)}+e^{-i(\varphi+\theta)}&=(e^{i\theta}+e^{-i\theta}-1)(e^{i\varphi}+e^{-i\varphi}) \\ (e^{i\theta}+e^{-i\theta})(e^{i(\varphi+(n-1)\theta)}+e^{-i(\varphi+(n-1)\theta)})&=e^{i(\varphi+(n-2)\theta)}+e^{-i(\varphi+(n-2)\theta)} \end{align} i.e. \begin{align} \cos(\varphi-\theta)&=\cos(\varphi) & (1)'\\ \cos(\varphi+n\theta)&=0 & (n)' \end{align} From $(1)'$, either $\theta=0$ or $\varphi = \frac{\theta}{2}+k\pi$. $\theta=0$ would give $\mu=0$ which is excluded since $A_n$ is an invertible matrix. Hence using $\varphi = \frac{\theta}{2}+k\pi$ and $(n)'$: $$(n+\frac{1}{2})\theta=(k+\frac{1}{2})\pi$$ Using that $\theta\in[0,\pi]$, we get that $\theta\in \Big\{\frac{j-\frac{1}{2}}{n+\frac{1}{2}} \pi \mid j=1,\dots,n\Big\}$. And in fact each of these values yields an eigenvalue and an eigenvector. The corresponding eigenvalues are $\mu_j=4\sin^2\Big(\frac{j-\frac{1}{2}}{n+\frac{1}{2}} \frac{\pi}{2}\Big)$, $ j=1,\dots,n$.

Trace Norm of $T_n$

The singular values of $T_n$ can now be deduced: $$\sigma_j=\frac{1}{2\sin\Big(\frac{j-\frac{1}{2}}{n+\frac{1}{2}} \frac{\pi}{2}\Big)}\,,\quad j=1,\dots,n$$ and the trace norm is $$ \|T_n\|_{\text{Tr}}=\frac{1}{2}\sum_{j=1}^n \frac{1}{\sin\Big(\frac{j-\frac{1}{2}}{n+\frac{1}{2}} \frac{\pi}{2}\Big)} \,.$$

Using that $\sin x\geq \frac{2}{\pi}x$ on $[0,\frac{\pi}{2}]$ one gets the upper bound: $$ \|T_n\|_{\text{Tr}}\leq \frac{n+\frac{1}{2}}{2}\sum_{j=1}^n \frac{1}{j-1/2}\leq \frac{n+\frac{1}{2}}{2} \Big(\frac{1}{2}+\ln(2n+1)\Big)\,,$$ which implies that $$ \limsup_{n\in\mathbb N^*} \Big\{\frac{1}{n\log(n)}\|T_n\|_{\text{Tr}}\Big\} \leq \frac{1}{2} \,. $$

Actually one also has a lower bound $$ \frac{n+1/2}{\pi}\Big(\ln(\tan(\frac{\pi}{4}))-\ln(\tan(\frac{\pi}{4(n+1/2)}))\Big) \leq \frac{n+1/2}{\pi} \int_{\frac{\pi}{2n+1}}^{\frac{\pi}{2}} \frac{dx}{\sin(x)} \leq \|T_n\|_{\text{Tr}} \,,$$ which implies that $$ \frac{1}{\pi} \leq \liminf_{n\in\mathbb N^*} \Big\{\frac{1}{n\log(n)}\|T_n\|_{\text{Tr}}\Big\} \,. $$

Answer 1

In Loewner ordering, we have $$ T_n^{-1}(T_n^{-1})^\top =\pmatrix{2&-1\\ -1&\ddots&\ddots\\ &\ddots&2&-1\\ &&-1&1} \preceq\pmatrix{2&-1\\ -1&\ddots&\ddots\\ &\ddots&2&-1\\ &&-1&2}=P. $$ Using the spectral formula for tridiagonal Toeplitz matrices, the eigenvalues of $P$ are given by $2+2\cos\left(\frac{k\pi}{n+1}\right)=4\cos^2\left(\frac{k\pi}{2(n+1)}\right)$ with $k=1,2,\ldots,n$. Therefore, the $k$-th smallest singular value of $T_n$ is bounded below by $\frac12\sec\left(\frac{k\pi}{2(n+1)}\right)$ and \begin{align} \frac1n\|T_n\|_{\text{Tr}} &\ge\frac1n\sum_{k=1}^n\frac12\sec\left(\frac{k\pi}{2(n+1)}\right)\\ &\ge\frac1\pi\int_0^{n\pi/2(n+1)}\sec x\,dx\\ &=\frac1\pi\ln\left(\sec\frac{n\pi}{2(n+1)} + \tan \frac{n\pi}{2(n+1)}\right), \end{align} which is unbounded when $n\to\infty$.

Answer 2

This is not an answer to this interesting question, but it may shed additional light. When computing the singular values of such matrices (which is possible with R for $n \le 2000$ without trouble), I find that the $i$-th singular value $s_i$ of such a matrix satisfies very nearly
$$ s_i \ge c \cdot \frac{n}{i} $$
for some constant $c$ that does not depend on $n$. The picture below shows plots of $const. \cdot \frac{ i \cdot s_i}{n}$ against $i$ for $n = 500, 1000, 1500, 2000$, with $const. = \pi$.

If such an estimate is correct then clearly $$ \|T_n\|_{Tr} \ge c \cdot n \cdot \log n \, . $$ So one might try to prove something like this estimate.

Answer 3

It can be easily shown, that $$\sup_{n\in\mathbb N^*} \Big\{\frac{1}{n\sqrt{n}}\|T_n\|_{\text{Tr}}\Big\} < \infty$$

In order to find a better assymptotic bound we need information about singular values of $T_n$ or some related matrices.

Let $\Omega_n = T_n^TT_n + T_nT_n^T$. This is a special Toeplitz matrix and its eigenvalues are computed in Bünger, F. "Inverses, determinants, eigenvalues, and eigenvectors of real symmetric Toeplitz matrices with linearly increasing entries." Linear Algebra and its Applications 459 (2014): 595-619.

Result from this paper: let eigenvalues of $\Omega_n$ be sorted decreasingly. Then even eigenvalues are given by for $k = 1,\dots, n/2$ $$\lambda_{2k} = -\left(-1 + \cos\frac{(2k-1)\pi}{n}\right)^{-1}$$ This paper also gives implicit formula for odd eigenvalues, but highly complicated. Additionally $\sum_{i=1}^{n}\lambda_i = tr(\Omega_n) = n(n+1)$. This allows to for deriving a stringent upper bound for $\|T_n\|_{tr}$ \begin{align} \|T_{n}\|_{tr} &= tr\sqrt{T_n'T_n} \leq tr\sqrt{\Omega_n}= \sum_{i=1}^n\lambda_i^{1/2} \leq \lambda_1^{1/2} + \sum_{i=1}^{n/2}\lambda_{2i}^{1/2} + \sum_{i=1}^{n/2-1}\lambda_{2i+1}^{1/2}\\ &\leq\lambda_1^{1/2} + 2\sum_{i=1}^{n/2}\lambda_{2i}^{1/2}\equiv M_n \end{align} with $\lambda_1\leq (n+1)n - \lambda_2 - 2\sum_{i=2}^{n/2}\lambda_{2i}$.

It is stil complicated to simplify this expression, but allows for numerical experiments with large $n$ $$ \begin{array}{c|l} n & M_n/n\\ \hline 10^3 & 4.7422\\ 10^4 & 5.7782\\ 10^5 & 6.8147\\ 10^6 & 7.8512\\ 10^7 & 8.8883\\ 10^8 & 9.9731\\ \end{array} $$

This suggests, that the limit to prove is not valid, the best what can be expected is $\sup_{n\in\mathbb N^*} \Big\{\frac{1}{n\log{n}}\|T_n\|_{\text{Tr}}\Big\} < \infty$.