<p>Assume you are given a matrix
$$
X=
\begin{bmatrix}
x_1^1 &amp; x_1^2 &amp; \dots &amp; x_1^m \\
x_2^1 &amp; x_2^2 &amp; \dots &amp; x_2^m \\
\vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
x_n^1 &amp; x_n^2 &amp; \dots &amp; x_n^m
\end{bmatrix}
$$
such that all $x_i^j \in \big\{0,1\big\}$, $\vee$ is the logical OR, and:
$$
\forall i,j, \quad x_{i}^j = 
\begin{cases}
x_{i+1}^{j}\vee x_{i+1}^{j-1} &amp; \text{if }\:j\neq1,\\
x_{i+1}^1\vee x_{i}^m &amp; \text{otherwise}.
\end{cases}
$$
This is quite similar to the Pascal triangle with binomials, except here we are dealing with $0/1$ variables and regular addition is replaced by the logical OR.</p>

<p>The problem now is to minimize: $$S=\sum_{i,j} x_i^j,$$ where the trivial case $S=0$ with all $x_i^j=0$ is not an option. The sum is the one in the integers: $0&lt;S\leq n m$.</p>

<p><strong>EDIT:</strong> What can we say about the case where the $\vee$ operator is no longer the logical OR, but is defined by: $0\vee0=0$, $1\vee0=0\vee1=1$ and $1\vee1\in\{0,1\}$.</p>

<p>Does this problem reduces to another one? Maybe there are references that I am not aware of. </p>

<p>Thanks for your help.</p>

CC BY-SA 3.0
2012-03-02T10:36:54.850Z
How is $x_i^j$ defined for $i=n$? And: is it really $x_i^m$ in the second of the definition?
Marcus Ritt
CC BY-SA 3.0
2012-03-04T11:48:54.003Z
When $i=n$, there is no constraint: values are free to choose. And yes, it is $x_i^m$: there is this linking property the Pascal triangle does not have.
wwjoze
<cc.complexity-theory><reference-request><optimization>
Minimization on a binary matrix
wwjoze
# Minimization on a binary matrix

(Asked by: username_0 on 2012-02-26)

Assume you are given a matrix
$$
X=
\begin{bmatrix}
x\_1^1 & x\_1^2 & \dots & x\_1^m \\
x\_2^1 & x\_2^2 & \dots & x\_2^m \\
\vdots & \vdots & \ddots & \vdots \\
x\_n^1 & x\_n^2 & \dots & x\_n^m
\end{bmatrix}
$$
such that all $x\_i^j \in \big\{0,1\big\}$, $\vee$ is the logical OR, and:
$$
\forall i,j, \quad x\_{i}^j =
\begin{cases}
x\_{i+1}^{j}\vee x\_{i+1}^{j-1} & \text{if }\:j\neq1,\\
x\_{i+1}^1\vee x\_{i}^m & \text{otherwise}.
\end{cases}
$$
This is quite similar to the Pascal triangle with binomials, except here we are dealing with $0/1$ variables and regular addition is replaced by the logical OR.

The problem now is to minimize: $$S=\sum\_{i,j} x\_i^j,$$ where the trivial case $S=0$ with all $x\_i^j=0$ is not an option. The sum is the one in the integers: $0

**EDIT:** What can we say about the case where the $\vee$ operator is no longer the logical OR, but is defined by: $0\vee0=0$, $1\vee0=0\vee1=1$ and $1\vee1\in\{0,1\}$.

Does this problem reduces to another one? Maybe there are references that I am not aware of.

Thanks for your help.

**Tags:** cc.complexity-theory, reference-request, optimization
> **Comments:**
> **username_1**: How is $x_i^j$ defined for $i=n$? And: is it really $x_i^m$ in the second of the definition?  
> **username_0**: When $i=n$, there is no constraint: values are free to choose. And yes, it is $x_i^m$: there is this linking property the Pascal triangle does not have.  

---

## 0 answers

