0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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\}$ $\endgroup$
    – Walter Simon
    Sep 2, 2018 at 10:43
  • $\begingroup$ Sorry but, why $\mu$ is non zero? $\endgroup$
    – Walter Simon
    Sep 2, 2018 at 14:48
  • 1
    $\begingroup$ A convex multiplier satisfies $\mu_k \ge 0$ and $\sum_k \mu_k = 1$ so it cannot be zero. $\endgroup$
    – copper.hat
    Sep 2, 2018 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .