# If a set of linear functionals define semispaces that cover the space then they are linearly dependent.

Let $V$ be a finite dimensional vector space. If $A=\{l_i\}_{i=1}^n \subseteq V^*$ are linear functional such that $\displaystyle\max_{i=1,\dots, n}\{l_i(x)\}\geq 0$ for all $x\in V$, then $A$ is linearly dependent.

A geometrical way to interpret $\displaystyle \max_{i=1,\dots,n}\{l_i(x)\}\geq 0$ for all $x\in V$ is to say that the family of semispaces $\{x\in V\mid l_i(x)\geq 0\}$ cover $V$.

How can I prove this?

Let $f(x) = \max_k l_k(x)$. Note that $f(0) = 0$ and $f(x) \ge 0$ for all $x$. Since $f$ is convex, we have $0 \in \partial f(0)$.
We have $\partial f(0) = \operatorname{co} \{ l_k \}_{k \in I(0)}$, where $I(x) = \{ k | f(x) = l_k(x) \}$.
In particular, there is a (non zero) convex multiplier $\mu$ such that $\sum_k \mu_k l_k = 0$ from which it follows that $A$ is not linearly independent.
• Thanks! It took me a while to understand this question but I think at the end it reduces to this facts: • $f$ is convex • $0$ is a subgradient of $f$ at $0$ because $0$ is a minimum for $f$ there • The set $\partial f(x)$ of all subgradients of $f=\max f_i$ is the cone generated by the union of the sets $\partial f_i(x)$ • We have $\partial l_i (0)= \{l_i\}$ Sep 2, 2018 at 10:43
• Sorry but, why $\mu$ is non zero? Sep 2, 2018 at 14:48
• A convex multiplier satisfies $\mu_k \ge 0$ and $\sum_k \mu_k = 1$ so it cannot be zero. Sep 2, 2018 at 14:59