# Problem on singular value and trace of matrix

Let $A,B\in \mathbb{R}^{n\times n}$ show that there exists

(1) Orthogonal matrix U,V satisfying $|trace(AB)|\leq\sum_{i=1}^{n}\sum_{j=1}^{n}(\sigma_{i}(A)\sigma_{j}(B)|u_{ij}v_{ij}|)$

(2) Double stochastic matrix $C$ satisfying $|trace(AB)|\leq\sum_{i=1}^{n}\sum_{j=1}^{n}(\sigma_{i}(A)\sigma_{j}(B)c_{ij})\leq\sum_{i=1}^{n}(\sigma_{i}(A)\sigma_{i}(B))$

Note that $\sigma_{1}(M)\geq ...\sigma_{n}(M)\geq 0$ are ordered singular value of matrix $M$

I do know the definition of singular value and orthogonal matrix but only a few properties about them. Maybe singular value decomposition can deal with the problems but I had trouble expressing its product. Any ideas how to find these matrixes and what properties or theorems should I apply here?

Hint for (1): $A=\sum_{i=1}^n \sigma_iu_iv_i^T$ where the vectors $u_i,v_i$ correspond to the SVD. If you have $A,B$, then they both have a corresponding SVD with $u_i',v_i'$ so write it out and expand the product of $AB$ as a double sum, giving terms like $\sigma_i(A)\sigma_j(B)u_iv_i^T u'_jv_j'^T$. Now notice that $U:=u_iv^T_i$ and $V:=u_j'v'^T_j$ are unitary.

Definitions and properties

A orthogonal matrix $\mathbf{U}\in\mathbb{R}^{n\times n}$ matrix satisfies $$\mathbf{U}^{\mathrm{T}} \mathbf{U} = \mathbf{U}\, \mathbf{U}^{\mathrm{T}}= \mathbf{I}_{n}.$$ Such a matrix has full rank, and all eigenvalue are $\pm 1$, which implies the determinant: $$\det \mathbf{U} = \pm 1.$$

The singular value decomposition of a rank $\rho$ matrix $\mathbf{A}\in\mathbb{R}^{n\times n}_{\rho}$ is $$\mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = % \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}\left(\mathbf{A}\right)}} & \color{red} {\mathbf{U}_{\mathcal{N}\left(\mathbf{A}^{*}\right)}} \end{array} \right] % \Sigma % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}\left(\mathbf{A}^{*}\right)}}^{*} \\ \color{red} {\mathbf{V}_{\mathcal{N}\left(\mathbf{A}\right)}}^{*} \end{array} \right] %$$ The coloring identifies entities in $\color{blue}{range}$ and $\color{red}{null}$ spaces.

The ordered singular values $$\sigma_{1} \ge \sigma_{2} \ge \dots \ge \sigma_{\rho} > 0$$ form the diagonal matrix $$\mathbf{S}_{k,k} = \sigma_{k}, \quad k = 1, \rho.$$ Embed this in a sabot matrix $$\Sigma = \left[ \begin{array}{cc} \mathbf{S} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} \end{array} \right]$$

The domain matrices are orthonormal spans. For the range spaces: \begin{align} \color{blue}{\mathcal{R}\left( \mathbf{A} \right)} &= \text{span} \left\{ \color{blue}{u_{1}}, \color{blue}{u_{2}}, \dots, \color{blue}{u_{\rho}} \right\} ,\\ % \color{blue}{\mathcal{R}\left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{blue}{v_{1}}, \color{blue}{v_{2}}, \dots, \color{blue}{v_{\rho}} \right\} . \end{align} For the null spaces: \begin{align} \color{red}{\mathcal{N}\left( \mathbf{A} \right)} &= \text{span} \left\{ \color{red}{u_{\rho+1}}, \color{red}{\rho+u_{2}}, \dots, \color{red}{u_{n}} \right\} ,\\ % \color{red}{\mathcal{N}\left( \mathbf{A}^{*} \right)} &= \text{span} \left\{ \color{red}{v_{\rho+1}}, \color{red}{v_{\rho+2}}, \dots, \color{red}{v_{n}} \right\} . \end{align}

Tools

The SVD resolves the matrix $\mathbf{A}$ into $\rho$ mutually orthogonal components: $$\mathbf{A} = \sum_{k=1}^{\rho} \sigma_{k} \color{blue}{u_{k}} \color{blue}{v_{k}^{\mathrm{T}}}$$

$$\text{tr }\left( \mathbf{A} \mathbf{B} \right) = % \sum_{k=1}^{n} \left| \mathbf{A} \mathbf{B} \right|_{k,k} = % \sum_{k=1}^{n} \mathbf{A}_{k,:} \mathbf{B}_{:,k} = % \sum_{j=1}^{n} \sum_{k=1}^{n} a_{j,k} b_{k,j}$$