Dual LP of Helly's theroem using linear algebra I will first write down the problem statement (also known as Helly's Theorem)
We have linear inequalities given by $Ax\le b,x\in \mathbb R^n$ and also that they don't have a feasible solution. We want to show that there are $n+1$ inequalities among them such that the resulting subsystem also does not have a solution.
I will now state how far I arrived. I looked at the following LP problem :
$$\max 0$$
$$Ax\le b$$
Next we take the dual to get $$\min b^Ty$$
$$A^Ty=0$$
$$y\ge0$$
and since the original primal has no soulution, and this dual problem has a feasible solution ($y=0$) the dual solution is unbounded. I do not know what the simplex method is(which is how this proof works). So I am trying to use Algebra and rank-nullity theorem.
Hence $\exists y_0$ such that $y_0\ge0$ and $\begin{bmatrix}
A^t\\
b^T\\
\end{bmatrix}y_0=\begin{bmatrix}
0\\
-a\\
\end{bmatrix}$ for some $a> 0$. This is a necessary and sufficient condition to have an unbounded solution in the dual.
Now assuming $A_{m\times n}(m\ge n+1)$, we have that rank of $A\le n\implies $ rank of $A^T\le n$. Also $b^T\notin$ row space of $A^T$,else $A^T y_0=0$ would imply that $b^T y=0$. So rank of $A^T\ne n$ i.e. rank of $A<n$. Now, $\begin{bmatrix}
A^T\\
b^T\\
\end{bmatrix}$ is an $(n+1)\times m$ matrix with rank $k+1$. Where $k$ is the rank of $A$. We would like to say that there exists $n+1$ columns of $\begin{bmatrix}
A^T\\
b^T\\
\end{bmatrix}$ such that $\exists y_1\ge 0,y_1\in \mathbb R^{n+1}$ satisfying $\begin{bmatrix}
A'\\
b'\\
\end{bmatrix}^Ty_1=\begin{bmatrix}
0\\
-x\\
\end{bmatrix}$. (Where $A'$ and $B'$ are the trimmed matrices with selected columns).
Will selecting $k+1$ independent columns and randomly selecting rest columns help?
 A: The property of the dual LP you want is Carathéodory's theorem.
I don't think you can do this by pure linear algebra like just picking independent columns - you need to ensure you get a non-negative $y_1.$
Take $a>0$ and $y_0\geq 0$ such that:
$$\begin{bmatrix}
A^t\\
b^T\\
\end{bmatrix}y_0=\begin{bmatrix}
0\\
-a\\
\end{bmatrix}\in\mathbb R^{n+1}\tag{*}$$
and such that $y_0$ has the minimum possible number of positive components (fixing $a$).
Suppose for contradiction that $y_0$ has more than $n+1$ positive components. Then there is a linear dependency between the subset of rows $i$ such that $(y_0)_i>0.$ This means there is some non-zero $z$ such that:
$$\begin{bmatrix}
A^t\\
b^T\\
\end{bmatrix}z=0\in\mathbb R^{n+1}$$
and with $z_i\neq 0\implies (y_0)_i> 0.$ Let $\lambda$ be the value of $(y_0)_i/z_i$ with minimum absolute value among the choices of $i$ with $z_i\neq 0.$ Then $y'_0=y_0-\lambda z\geq 0$ by continuity of each component (any negative component would have become zero at some smaller $|\lambda|$). So $y'_0$ is non-negative, has fewer positive components than $y_0,$ and still satisfies (*). This contradicts the choice of $y_0.$
Using the duality you mentioned,  $A'x\leq b'$ is inconsistent where $A'$ and $b'$ are $A$ and $b$ respectively restricted to the rows $i$ such that $(y_0)_i>0.$
