Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$.

I am trying to write $$ Set=\{x\in\mathbb Z^n:C[x]'\leq d\}\quad\text{where $C$ has $r'$ rows.} $$

Is the number of rows $r'\leq r^{m}$?

In my situation in addition to $A$ having $r=O(m)$ rows and every row has $1$, $2$ or $3$ entries. We further divide $n+m$ columns to first $m_0=n$ columns, next $m_1$ columns until final $m_d$ columns ($m=\sum_{i=1}^d m_i$) and so $A$ is block matrix of $d(d+1)$ blocks (rows are $k$ times number of columns). A block is non-zero iff it is $(i,i)$ and $(i,i+1)$ block (diagonal and one above).

$$A=\begin{bmatrix} A_{0,0}&A_{0,1}&0&\dots&0&0\\ 0&A_{1,1}&A_{1,2}&\dots&0&0\\ \vdots\\ 0&0&0&\dots&A_{d-1,d-1}&A_{d-1,d} \end{bmatrix}$$ where $A_{j-1,j}=\mathbb I_{m_j,m_j}\otimes\mathbb 1_{k}$ where $\mathbb I_{m_j,m_j}$ is $m_j\times m_j$ identity and $\mathbb 1_k$ is $k\times 1$ vectors of every entry being $1$ and $A_{j,j}$ has $km_{j+1}$ rows and $m_j$ columns. In addition at every block matrix $A_{j,j+1}$ every column is non-zero and every row has $1$ non-zero entry. Every row of $A$ has $1$, $2$ or $3$ non-zero entries.

In the situation involved is it possible that $r'=\operatorname{poly}(2^d{m}r)=\operatorname{poly}(m2^d)$ holds?


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.