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

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\} \,.$$

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$.

• Perfect, maybe this could also give me a good upper bound? What is Loewner ordering? Odering using the positivity for quadratic forms? Commented Jul 13, 2016 at 6:52
• Ok, Loewner ordering is defined on Wikipedia. Commented Jul 13, 2016 at 7:21
• @SebastienB It's really not a tight bound. While the relative error given by this bound decreases when $n$ is getting larger and larger, convergence is ridiculously slow, mainly because the bound $\frac12\sec\left(\frac{n\pi}{2(n+1)}\right)$ underestimates the largest singular value by a fairly large margin. Commented Jul 13, 2016 at 15:10
• nice one (+1) !! Commented Jul 13, 2016 at 16:31
• Your observation that the inverse matrix is simple also allows to compute explicitly the singular values and to give good bounds on the trace norm, I added that in an edit, thanks a lot. Commented Jul 26, 2016 at 14:37

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.

• So it looks that $1\leq \frac{\pi i s_i}{n}\leq 2$, which would imply $c n\log(n) \leq \|T_n\|_{\text{Tr}}\leq C n\log(n)$. Thank you very much, I understand better what I shall try to prove. Commented Jul 12, 2016 at 15:46
• It seems there is some function $g:[0,1]\to[1,2]$ such that $\frac{\pi i s_{n,i}}{n}\approx g(i/n)$. Commented Jul 12, 2016 at 15:49
• That's my impression as well. The limiting case is the Volterra operator on $L^2(0,1)$, $u \mapsto K(u), K(u)(t) = \int_t^1 u(s) ds$, which I think has been well studied. Commented Jul 12, 2016 at 15:55
• I now have an explicit expression for $s_i$, and it confirms your observations, thanks a lot! Commented Jul 26, 2016 at 14:51

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$.