We study the relationship between the minimum dimension of an orthogonalrepresentation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph that the 3-colorability problem is equivalent to deciding whether the class defined by the graph has a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class.
展开▼
