Return to Question

Let $Q(x_1,\dots,x_n)$ be a quadratic form with all non-negative and integral coefficients given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^cf_i^+(x_1,\dots,x_n)g_i^+(x_1,\dots,x_n)$$ where $c$ is the length of the expression where both $f_i^+,g_i^+$ are both linear in each variable with all non-negative and integral coefficients. Call minimal value of $c$ among all such expressions as the length $L(Q)$.

Note if rank of $Q$ is $R(Q)$, then $Q(x_1,\dots,x_n)$ can be given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^{R(Q)}f_i(x_1,\dots,x_n)g_i(x_1,\dots,x_n)$$ where both $f_i,g_i$ are both linear in each variable with any coefficients.

Note that $R(Q)\leq L(Q)$ holds true.

Is either $L(Q)=O(R(Q)^\alpha)$ or $O(2^{(\log_2R(Q))^\alpha})$ for an universal constant $\alpha>1$ true as well?

Let $Q(x_1,\dots,x_n)=X'PX$ be a quadratic form with all non-negative and integral coefficients given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^cf_i^+(x_1,\dots,x_n)g_i^+(x_1,\dots,x_n)$$ where $c$ is the length of the expression where both $f_i^+,g_i^+$ are both linear in each variable with all non-negative and integral coefficients. Call minimal value of $c$ among all such expressions as the length $L(Q)$.

Note if rank of $Q$ is $R(Q)$, then $Q(x_1,\dots,x_n)$ can be given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^{R(Q)}f_i(x_1,\dots,x_n)g_i(x_1,\dots,x_n)$$ where both $f_i,g_i$ are both linear in each variable with any coefficients.

Note that $R(Q)\leq L(Q)$ holds true.

Is either $L(Q)=O(R(Q)^\alpha)$ or $O(2^{(\log_2R(Q))^\alpha})$ for an universal constant $\alpha>1$ true as well?

Atleast if one assumes $f_i^+g_i^+=Q_i=X'P_iX$ where each $P_i$ is a rank one matrix, can we show this? In this case, we will get $L_1(Q)$ as minimum length where $1$ stands for rank $1$ decomposition of $P$ in $Q=X'PX$ (that is $P=\sum_{i=1}^{L_1(Q)}P_i$) and $R(Q)\leq L(Q)\leq L_1(Q)$. We would then want to show $$L_1(Q)=O(R(Q)^\alpha)\mbox{ or }O(2^{(\log_2R(Q))^\alpha})$$ for an universal constant $\alpha>1$ true as well?

Let $Q(x_1,\dots,x_n)$ be a quadratic form with all non-negative coefficients given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^cf_i^+(x_1,\dots,x_n)g_i^+(x_1,\dots,x_n)$$ where $c$ is the length of the expression where both $f_i^+,g_i^+$ are both linear in each variable with all non-negative coefficients. Call minimal value of $c$ among all such expressions as the length $L(Q)$.

Note if rank of $Q$ is $R(Q)$, then $Q(x_1,\dots,x_n)$ can be given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^{R(Q)}f_i(x_1,\dots,x_n)g_i(x_1,\dots,x_n)$$ where both $f_i,g_i$ are both linear in each variable with any coefficients.

For instance if $Q$ is given by $X'AX$, then if $PAP'$ diagonalizes $A$ to $\Lambda$, then $\tilde{X}'\Lambda\tilde{X}=X'P'\Lambda PX= X'P'PAP'PX=X'AX$ and so $f_i=\sqrt{\lambda_i} \tilde{x}_{i}'$ and $g_i=\sqrt{\lambda_i} \tilde{x}_{i}$ and $$Q(x_1,\dots,x_n)=\sum_{i=1}^{R(Q)}\lambda_i ( \tilde{x}_{i}')( \tilde{x}_{i})=\sum_{i=1}^{R(Q)}(\sum_{j=1}^n\sqrt{\lambda_i}P_{ij}'x_j')(\sum_{j=1}^n\sqrt{\lambda_i}P_{ij}x_j).$$

It should be possible to replace this by $$Q(x_1,\dots,x_n)=\sum_{i=1}^{L(Q)}(\sum_{j=1}^nS_{ij}x_j')(\sum_{j=1}^nT_{ij}x_j)$$ with all $S_{ij},T_{ij}\geq 0$ so that $L(Q)$ is minimum possible since $Q$ has no negative coefficients.

Note that $R(Q)\leq L(Q)$ holds true.

Is either $L(Q)=O(R(Q)^\alpha)$ or $O(2^{(\log_2R(Q))^\alpha})$ for an universal constant $\alpha>1$ true as well?

Let $Q(x_1,\dots,x_n)$ be a quadratic form with all non-negative and integral coefficients given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^cf_i^+(x_1,\dots,x_n)g_i^+(x_1,\dots,x_n)$$ where $c$ is the length of the expression where both $f_i^+,g_i^+$ are both linear in each variable with all non-negative and integral coefficients. Call minimal value of $c$ among all such expressions as the length $L(Q)$.

Note if rank of $Q$ is $R(Q)$, then $Q(x_1,\dots,x_n)$ can be given by $$Q(x_1,\dots,x_n)=\sum_{i=1}^{R(Q)}f_i(x_1,\dots,x_n)g_i(x_1,\dots,x_n)$$ where both $f_i,g_i$ are both linear in each variable with any coefficients.

Note that $R(Q)\leq L(Q)$ holds true.

Is either $L(Q)=O(R(Q)^\alpha)$ or $O(2^{(\log_2R(Q))^\alpha})$ for an universal constant $\alpha>1$ true as well?