# What is low rank intuitively for an adjacency matrix?

If you have a graph represented by an adjacency matrix, what intuitively in terms of the original graph would low rank correspond to?

I am interested in this for both directed and undirected graphs.

This is relevant because low rank is very important in common techniques such as non-negative matrix factorization and it would be interesting to understand what the assumptions mean for graphs.

I'm not sure if your question is easy to answer, but I will try to provide an intuition. I am not an expert in non-negative matrix factorisation so I can't explain the connections there.

Let's restrict out attention to simple, undirected graphs $G$ with $n$ vertices. I will assume by low-rank you mean, low-rank of the adjacency matrix. These properties are derived from here Here's are a characterisation low-rank graphs:

• the graph with no vertices is the only graph with rank 0
• a complete bipartite graph is the only connected graph with rank 2
• a complete tripartite graph is the only connected graph with rank 3

Rank is known to be preserved between subgraphs as follows:

• if H is an induced subgraph of G, then $rank(H) \leq rank(G)$.
• Let $G = G1 \cup G2 \cup··· \cup G_n$, where $G_1, G_2,...,G_n$ are connected components of G, then $rank(G) = \sum_i^n rank(G_i)$

Since the complete graph has rank $n$, it follow from this that $largest \_clique(G) \leq rank(G)$.

What is the rank of an average graph? Consider this simple model of a random graph $G$: for every pair of vertices flip a fair coin to determine whether there is an edge between them. It has been shown that with very high probability $G$ has rank $n$.

This suggests to me that low rank graphs are locally sparse or have a densely connected component but have lots of isolated vertices. A graph picked at random is likely to be full rank, however.

• +1 for clear useful information. Note that the sense of "almost surely" in the paper you reference is nonstandard: there is always a finite chance that the rank will be less than $n$ in the random Bernoulli graph on $n$ vertices, whereas the usual meaning of "almost surely" is zero chance. – whuber Aug 23 '16 at 16:03
• Thanks for the feedback, I've revised the answer so that it's hopefully a little clearer. – MachineEpsilon Aug 24 '16 at 8:16