Problem: Given an $n\times n$ symmetric positive semidefinite (PSD) $\color{blue}{\textbf{integer}}$ matrix $Q$ with $\mathrm{Rank}(Q) = r$, find $\color{blue}{\textbf{integer}}$ vectors $u_i, i=1, \cdots, r$ and positive $\color{blue}{\textbf{integer}}$ pairs $(c_i, d_i), i=1, \cdots, r$ such that $$Q = \frac{c_1}{d_1} u_1u_1^\mathsf{T} + \frac{c_2}{d_2} c_2u_2 u_2^\mathsf{T} + \cdots + \frac{c_r}{d_r} u_r u_r^\mathsf{T}.$$
Background:
The problem arises when we express a non-negative polynomial as a sum of squares (SOS) of polynomials.
See e.g. https://web.stanford.edu/class/ee364b/lectures/sos_slides.pdf.
When we get $f(x) = Z(x)^\mathsf{T}Q Z(x)$ (see page 8 in the link above), we hope to do rational rank one decomposition of $Q$
such that we can express $f(x)$ as sum of squares of polynomials that is $f(x) = \sum_{i=1}^r [f_i(x)]^2$.
Also see my answers for the following questions:
https://mathoverflow.net/questions/193753/this-inequality-why-cant-solve-it-by-now-only-four-variables-inequality,
https://mathoverflow.net/questions/239243/an-inequality-concerning-lagranges-identity
Discussion:
This task is easy by the following fact:
Fact 1: Let $B$ be an $n\times n$ real symmetric positive semidefinite matrix. Let $u\in \mathbb{R}^n$ is a vector such that $u^\mathsf{T}Bu \ne 0$, then \begin{align} \mathrm{Rank}\left(B - \frac{1}{u^\mathsf{T}Bu} Buu^\mathsf{T}B\right) &= \mathrm{Rank}(B) - 1, \tag{1}\\ B - \frac{1}{u^\mathsf{T}Bu} Buu^\mathsf{T}B &\succeq 0. \tag{2} \end{align} For (1), see Theorem 1.1 in [1]. (2) is obvious.
According to Fact 1, we have the following process:
First we choose any integer vector $v_1$ such that $v_1^\mathsf{T}Qv_1 \ne 0$, let $Q_1 = Q - \frac{1}{v_1^\mathsf{T}Qv_1} Qv_1v_1^\mathsf{T}Q$.
Second, choose any integer vector $v_2$ such that $v_2^\mathsf{T}Q_1v_2 \ne 0$, let $Q_2 = Q_1 - \frac{1}{v_2^\mathsf{T}Q_1v_2}Q_1v_2v_2^\mathsf{T}Q_1$.
$\cdots\cdots$
Finally we get $Q = \frac{1}{v_1^\mathsf{T}Qv_1} Qv_1v_1^\mathsf{T}Q + \frac{1}{v_2^\mathsf{T}Q_1v_2} Q_1v_2v_2^\mathsf{T}Q_1 + \cdots$.
Example 1:
$$Q = \left(\begin{array}{rrr} 16 & -17 & 12\\ -17 & 23 & -6\\ 12 & -6 & 19 \end{array}\right),$$ $v_1 = [1, 0, 0]^\mathsf{T}$, $$Q_1 = \left(\begin{array}{rrr} 0 & 0 & 0\\ 0 & 79/16 & 27/4\\ 0 & 27/4 & 10 \end{array}\right),$$ $v_2 = [0, 1, 0]^\mathsf{T}$, $$Q_2 = \left(\begin{array}{rrr} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 61/79 \end{array}\right).$$ Terminate since $\mathrm{Rank}(Q_2) = 1$. We have $$Q = \frac{1}{16} u_1u_1^\mathsf{T} + \frac{1}{1264}u_2u_2^\mathsf{T} + \frac{61}{79}u_3u_3^\mathsf{T}$$ where $u_1 = [16, -17, 12]^\mathsf{T}, u_2 = [0, 79, 108]^\mathsf{T}, u_3 = [0, 0, 1]^\mathsf{T}$.
Example 2: For the same $Q$ as Example 1, we choose different $v_1, v_2$.
$$Q = \left(\begin{array}{rrr} 16 & -17 & 12\\ -17 & 23 & -6\\ 12 & -6 & 19 \end{array}\right),$$ $v_1 = [2, 1, -1]^\mathsf{T}$, $$Q_1 = \left(\begin{array}{rrr} 23/2 & -19/2 & 27/2\\ -19/2 & 21/2 & -17/2\\ 27/2 & -17/2 & 37/2 \end{array}\right),$$ $v_2 = [1, 0, -1]^\mathsf{T}$, $$Q_2 = \left(\begin{array}{rrr} 61/6 & -61/6 & 61/6\\ -61/6 & 61/6 & -61/6\\ 61/6 & -61/6 & 61/6 \end{array}\right).$$ Terminate since $\mathrm{Rank}(Q_2) = 1$. We have $$Q = \frac{1}{2} u_1u_1^\mathsf{T} + \frac{1}{3}u_2u_2^\mathsf{T} + \frac{61}{6}u_3u_3^\mathsf{T}$$ where $u_1 = [3, -5, 1]^\mathsf{T}, u_2 = [-2, -1, -5]^\mathsf{T}, u_3 = [1, -1, 1]^\mathsf{T}$.
Example 3: See https://mathoverflow.net/questions/239243/an-inequality-concerning-lagranges-identity
$$Q = \left(\begin{array}{rrrr} 7942 & -4138 & 917 & -4721\\ -4138 & 7934 & -4717 & 921\\ 917 & -4717 & 6000 & -2200\\ -4721 & 921 & -2200 & 6000 \end{array}\right),$$ $v_1 = [1, 0, 0, 0]^\mathsf{T}$, $$Q_1 = \left(\begin{array}{rrrr} 0 & 0 & 0 & 0\\ 0 & 22944392/3971 & -16833934/3971 & -6110458/3971\\ 0 & -16833934/3971 & 46811111/7942 & -13143243/7942 \\ 0 & -6110458/3971 & -13143243/7942 & 25364159/7942 \end{array}\right),$$ $v_2 = [0, 1, 0, 0]^\mathsf{T}$, $$Q_2 = \left(\begin{array}{rrrr} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 7984289425/2868049 & -7984289425/2868049 \\ 0 & 0 & -7984289425/2868049 & 7984289425/2868049 \end{array}\right).$$ Terminate since $\mathrm{Rank}(Q_2) = 1$. We have $$Q = \frac{1}{7942} u_1u_1^\mathsf{T} + \frac{1}{22778045158}u_2u_2^\mathsf{T} + \frac{7984289425}{2868049}u_3u_3^\mathsf{T}$$ where $u_1 = [7942, -4138, 917, -4721]^\mathsf{T}, u_2 = [0, 11472196, -8416967, -3055229]^\mathsf{T}$ and $u_3 = [0, 0, 1, -1]^\mathsf{T}$.
Question:
From Examples 1-2, we see that the numbers ($c_i$'s, $d_i$'s, elements of $u_i$'s, in absolute value) in Example 2 is smaller than that in Example 1 which is due to different choice of $v_1, v_2$. We say the rank one decomposition in Example 2 is better.
From Example 3, we see that the numbers ($c_i$'s, $d_i$'s, elements of $u_i$'s, in absolute value) can be quite large (the biggest one is $22778045158$) even when the numbers in $Q$ is not large (the biggest one is $7942$). Is there another $v_1, v_2$ such that the numbers are much smaller?
One can imagine that when $n$ is large and $\mathrm{Rank}(Q)$ is large (e.g., $n>100$, I have ever encountered), the numbers may be very very large if we randomly choose $v_1, v_2, \cdots$.
Is there algorithms to find the better solution by nicely choosing $v_1, v_2, \cdots$?
Any comments and solutions are welcome and appreciated.
Reference
[1] Moody T. Chu, Robert E. Funderlic and Gene H. Golub, “A Rank-One Reduction Formula and its Applications to Matrix Factorizations”, SIAM Review, Vol. 37, No. 4 (Dec., 1995), pp. 512-530.
Beginning with rational symmetric $H,$ we may calculate a nonsingular rational $L$ such that $H = L D L^T$ with $D$ diagonal rational. Taking the diagonal elements $d_i$ of $D,$ we know $D = \sum d_i e_i e_i^T,$ where $e_i$ is the column vector with a single $1$ at position $i$ and otherwise $0.$ It follows that $$ H = \sum d_i L e_i e_i^T L^T = \sum d_i (Le_i) (Le_i)^T$$
There are two basic methods for diagonalizing a quadratic form. One may repeatedly complete the square, as in many quadratics forms books. Students seem to have trouble with that, although it has always seemed easy to me. The opposite method is suitable for computers, so I will put in output from my program.
for now, see reference for linear algebra books that teach reverse Hermite method for symmetric matrices
The matrix I call $L$ above becomes $L=Q^T$ in the output below
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
$$ P^T H P = D $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ \frac{ 17 }{ 16 } & 1 & 0 \\ - \frac{ 174 }{ 79 } & - \frac{ 108 }{ 79 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 16 & - 17 & 12 \\ - 17 & 23 & - 6 \\ 12 & - 6 & 19 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & \frac{ 17 }{ 16 } & - \frac{ 174 }{ 79 } \\ 0 & 1 & - \frac{ 108 }{ 79 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 16 & 0 & 0 \\ 0 & \frac{ 79 }{ 16 } & 0 \\ 0 & 0 & \frac{ 61 }{ 79 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - \frac{ 17 }{ 16 } & 1 & 0 \\ \frac{ 3 }{ 4 } & \frac{ 108 }{ 79 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 16 & 0 & 0 \\ 0 & \frac{ 79 }{ 16 } & 0 \\ 0 & 0 & \frac{ 61 }{ 79 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - \frac{ 17 }{ 16 } & \frac{ 3 }{ 4 } \\ 0 & 1 & \frac{ 108 }{ 79 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 16 & - 17 & 12 \\ - 17 & 23 & - 6 \\ 12 & - 6 & 19 \\ \end{array} \right) $$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
$$ P^T H P = D $$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ \frac{ 2069 }{ 3971 } & 1 & 0 & 0 \\ \frac{ 3060867 }{ 11472196 } & \frac{ 8416967 }{ 11472196 } & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} 7942 & - 4138 & 917 & - 4721 \\ - 4138 & 7934 & - 4717 & 921 \\ 917 & - 4717 & 6000 & - 2200 \\ - 4721 & 921 & - 2200 & 6000 \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & \frac{ 2069 }{ 3971 } & \frac{ 3060867 }{ 11472196 } & 1 \\ 0 & 1 & \frac{ 8416967 }{ 11472196 } & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} 7942 & 0 & 0 & 0 \\ 0 & \frac{ 22944392 }{ 3971 } & 0 & 0 \\ 0 & 0 & \frac{ 7984289425 }{ 2868049 } & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ - \frac{ 2069 }{ 3971 } & 1 & 0 & 0 \\ \frac{ 917 }{ 7942 } & - \frac{ 8416967 }{ 11472196 } & 1 & 0 \\ - \frac{ 4721 }{ 7942 } & - \frac{ 3055229 }{ 11472196 } & - 1 & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} 7942 & 0 & 0 & 0 \\ 0 & \frac{ 22944392 }{ 3971 } & 0 & 0 \\ 0 & 0 & \frac{ 7984289425 }{ 2868049 } & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & - \frac{ 2069 }{ 3971 } & \frac{ 917 }{ 7942 } & - \frac{ 4721 }{ 7942 } \\ 0 & 1 & - \frac{ 8416967 }{ 11472196 } & - \frac{ 3055229 }{ 11472196 } \\ 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} 7942 & - 4138 & 917 & - 4721 \\ - 4138 & 7934 & - 4717 & 921 \\ 917 & - 4717 & 6000 & - 2200 \\ - 4721 & 921 & - 2200 & 6000 \\ \end{array} \right) $$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$