1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.