Why is the minimum rank of a matrix that fits a graph G larger or equal to the cardinality of the maximum stable set. So, we say a matrix $B$ fits a graph $G=(V,E)$ if 


*

*$B_{ii} \neq 0$ $\forall i\in V$

*$B_{ij} =0$ for all $\{i,j\}\in \bar{E}$ (which is the complement of the edge set of G)


And we define $R(G) = \min \{rank(B) | B$ fits $G\}$. 
Now I want to show $R(G) \leq \alpha(G) = \max \{|S|$  |  $ S\subset V$ stable in $ G\}$. 
How do I do this? Really hard to do when you're working with a minimum on $R(G)$. 
 A: The correct inequality is the reverse, which explains why you have a hard time proving it.
If $S$ is an independent (or stable) set of vertices in $G$, and $B$ is any matrix that fits $G$, then take the $|S| \times |S|$ submatrix of $B$ corresponding to the vertices in $S$. This submatrix must be a nonsingular diagonal matrix, since $B_{ii} \ne 0$ for all $i \in S$ and $B_{ij} = 0$ for all $i,j \in S$ with $i \ne j$.
In particular, if $B$ has an $|S| \times |S|$ nonsingular matrix inside it, then $\operatorname{rank}(B) \ge |S|$, proving that $R(G) \ge \alpha(G)$.
Finally, to take away any hope of proving the inequality $R(G) \le \alpha(G)$, we show that $R(C_5) > \alpha(C_5)$. We know that $\alpha(C_5) = 2$. Meanwhile, any matrix $B$ that fits $C_5$ must have the structure
$$
\begin{bmatrix}
    a &   & 0 & 0 &   \\
      & b &   & 0 & 0 \\
    0 &   & c &   & 0 \\
    0 & 0 &   & d &   \\
      & 0 & 0 &   & e
\end{bmatrix}
$$
where the blank entries are not yet determined, but entries $a,b,c,d,e \ne 0$. This cannot have rank $1$, because $R(C_5) \ge \alpha(C_5) \ge 2$. But it would have rank $1$ if any two adjacent columns were multiples of each other. Therefore some two adjacent columns - without loss of generality, the first two - are linearly independent.
But the fourth column is also linearly independent from the first two columns, because it has $d \ne 0$ in the fourth entry and the first two columns both have a zero there. So the rank of this matrix is at least $3$, and $R(C_5) \ge 3$. Just for completeness, $R(C_5) = 3$ since we can achieve rank $3$ with the matrix
$$
\begin{bmatrix}
    1 & 0 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 0 \\
    0 & 1 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 1 & 1
\end{bmatrix}.
$$
