Why can't the dual and primal linear program both be unbounded? I know if a dual is unbounded then the primal is unfeasible and vice versa, but I don't know why they can't both be unbounded. Is it because it's impossible to have linear constraints that are unbounded in the direction of the gradient and the opposite direction?
 A: Well, it is because of the weak duality theorem
A: Note: although unbounded primal is sufficient for an infeasible dual, it is not a necessary condition. Because there can be a case when both are infeasible. When one is infeasible we can say that the other is either unbounded or infeasible.
Given primal (P) normal max-LP:
\begin{equation*}
\begin{aligned}
& \underset{\vec{x}}{\text{max}}
& & z=\vec{c}^T\vec{x} \\
& \text{subject to}
& & A\vec{x} \leq \vec{b}, \\
& & &\,\,\,\,\vec{x} \geq \vec{0}
\end{aligned}
\end{equation*}
and dual (D) normal min-LP:
\begin{equation*}
\begin{aligned}
& \underset{\vec{y}}{\text{min}}
& & w=\vec{b}^T\vec{y} \\
& \text{subject to}
& & A\vec{y} \geq \vec{c}, \\
& & & \,\,\,\,\vec{y} \geq \vec{0}
\end{aligned}
\end{equation*}
Lemma 1 (weak duality): If $\vec{x}$ is feasible for (P) and $\vec{y}$ is feasible for (D), we have $z=\vec{c}^T\vec{x}\leq\vec{b}^T\vec{y}=w$. 
Proof: 
$\vec{x}$ is feasible for (P) $\Rightarrow$ $A\vec{x} \leq \vec{b}$, $\vec{x}\geq\vec{0}$
$\vec{y}$ is feasible for (D) $\Rightarrow$ $A\vec{y} \geq \vec{c}$, $\vec{y}\geq\vec{0}$
$\vec{y}^T(A\vec{x}\leq\vec{b}) \Rightarrow \vec{y}^T A\vec{x}\leq\vec{y}^T\vec{b}={w}$
$(A^T\vec{y}\geq\vec{c})^T \Rightarrow (\vec{y}^TA\geq\vec{c}^T)\vec{x} \Rightarrow \vec{y}^TA\vec{x} \geq\vec{c}^T\vec{x}=z$
combining, we get $z=\vec{c}^T\vec{x}\leq\vec{b}^T\vec{y}=w\,\,\square$
Lemma 2 (Strong Duality): if $z=\vec{c}^T\vec{x}=\vec{b}^T\vec{y}=w$ for feasible $\vec{x}$,$\vec{y}$ in (P) and (D), respectively, then $\vec{x}$,$\vec{y}$ are optimal for (P) and (D), respectively.
Proof: All z values lie below all w values (Lemma 1). Hence when z=w, we get optimality for both. 
Lemmas 3&4: If (P) is unbounded, then (D) is infeasible. Similarly if (D) is unbounded, (P) is infeasible. 
Explanation:
If (P) is unbounded, we can push z up without limits. Hence there are no finite w values, i.e, there are no feasible $\vec{y}$ for (D).
