  Farkas' lemma is a fundamental result from linear programming providing
linear certificates for infeasibility of systems of linear inequalities. In
semidefinite programming, such linear certificates only exist for strongly
infeasible linear matrix inequalities. We provide nonlinear algebraic
certificates for all infeasible linear matrix inequalities in the spirit of
real algebraic geometry. More precisely, we show that a linear matrix
inequality is infeasible if and only if -1 lies in the quadratic module
associated to it. We prove exponential degree bounds for the corresponding
algebraic certificate. In order to get a polynomial size certificate, we use a
more involved algebraic certificate motivated by the real radical and Prestel's
theory of semiorderings. Completely different methods, namely complete
positivity from operator algebras, are employed to consider linear matrix
inequality domination.
