Sin soluciones a una matriz de la desigualdad?

Question

Deje $A$ ser una matriz estocástica. Por lo tanto $A$ no negativo de las entradas, y la suma de los elementos de cada fila es 1. Esto implica que el vector $\begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}^T$ es un autovector correspondiente al autovalor 1. Es cierto que existe un vector $b$ tal que

$$(A - I)x \geq b$$

no tiene soluciones en $x$? Si es así, hay una prueba simple?

Motivación: he estado tratando de construir una respuesta a otra pregunta utilizando programación lineal dualidad (como el OP implica que él está interesado). Si mi razonamiento es correcto, este es el único paso que necesito para completar el argumento. Siento que esta debe ser una pregunta fácil de contestar, pero he estado trabajando en él durante un rato, pero sin éxito.

Answer 1

Su desigualdad $(A-I)x \ge b$ no tiene soluciones en $x$ tan pronto como $b>0$. De hecho, cualquier posible solución tendría que satisfacer $A x \ge x + b$ y, desde las filas de $A$ son no negativos y se suma a uno, cada elemento del vector de $Ax$ es una combinación convexa de los componentes de $x$, el cual debe ser menor que $x_{max}$, el mayor componente de la $x$. Por otro lado, al menos un elemento de a $x+b$ es mayor que $x_{max}$, lo que demuestra la imposibilidad.

Por cierto, la aplicación de Farkas Lema para este imposible el sistema muestra la siguiente siempre admite soluciones y $$y^T (A-I) = 0, y \ge 0 \text{ and } y^T b > 0$$ que expresa el hecho de que $A$ necesariamente la presencia de un no negativo a la izquierda autovector con autovalor $1$ (la última desigualdad se asegura de que $y$ es distinto de cero).