Question 107
Suppose that a matrix of nonnegative entries,
$$
P = \begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{15} & x_{16} & x_{17} & x_{18} & x_{19} \\ x_{21} & x_{22} & x_{23} & x_{24} & x_{25} & x_{26} & x_{27} & x_{28} & x_{29} \\ x_{31} & x_{32} & x_{33} & x_{34} & x_{35} & x_{36} & x_{37} & x_{38} & x_{39} \end{bmatrix}
$$
has the following properties:
(1) Numbers in a row are different from each other;
(2) The sum of the numbers in a column from the first six columns is $1$;
(3) $x_{17} = x_{28} = x_{39} = 0$;
(4) $x_{27}, x_{37}, x_{18}, x_{38}, x_{19}, x_{29} \gt 1$.
Assume that matrix $S$ is constituted by the first three columns of $P$, i.e.
$$
S = \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}
$$
has the following property:
(O) For any column $[x_{1k} \ x_{2k} \ x_{3k}]$ ($k = 1, 2, ..., 9$) in $P$, there exists $i \in \{1, 2, 3\}$ such that
$$
x_{ik} \le u_i = \min\{x_{i1}, x_{i2}, x_{i3}\}. \qquad \textcircled{1}
$$
Prove that:
(i) each column of $S$ contains at least one of $u_1, u_2, u_3$ (that is, an entry equal to the minimum of its row of $S$);
(ii) there is exactly one $k^* \in \{4, 5, \ldots, 9\}$ such that the matrix $S'$ formed by columns $1$, $2$, $k^*$ of $P$ also has property (O).
$$
P = \begin{bmatrix} x_{11} & x_{12} & x_{13} & x_{14} & x_{15} & x_{16} & x_{17} & x_{18} & x_{19} \\ x_{21} & x_{22} & x_{23} & x_{24} & x_{25} & x_{26} & x_{27} & x_{28} & x_{29} \\ x_{31} & x_{32} & x_{33} & x_{34} & x_{35} & x_{36} & x_{37} & x_{38} & x_{39} \end{bmatrix}
$$
has the following properties:
(1) Numbers in a row are different from each other;
(2) The sum of the numbers in a column from the first six columns is $1$;
(3) $x_{17} = x_{28} = x_{39} = 0$;
(4) $x_{27}, x_{37}, x_{18}, x_{38}, x_{19}, x_{29} \gt 1$.
Assume that matrix $S$ is constituted by the first three columns of $P$, i.e.
$$
S = \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}
$$
has the following property:
(O) For any column $[x_{1k} \ x_{2k} \ x_{3k}]$ ($k = 1, 2, ..., 9$) in $P$, there exists $i \in \{1, 2, 3\}$ such that
$$
x_{ik} \le u_i = \min\{x_{i1}, x_{i2}, x_{i3}\}. \qquad \textcircled{1}
$$
Prove that:
(i) each column of $S$ contains at least one of $u_1, u_2, u_3$ (that is, an entry equal to the minimum of its row of $S$);
(ii) there is exactly one $k^* \in \{4, 5, \ldots, 9\}$ such that the matrix $S'$ formed by columns $1$, $2$, $k^*$ of $P$ also has property (O).