Does an adjacency matrix need to have equal rows and columns?

Question

If it needs to be the same number of rows and columns, then why? If not, then why not?

Answer 1

Hi, Jeiku W,

An adjacency matrix shows how each node in a graph is connected (if at all) to every other node in the graph. So, each row in the adjacency matrix represents e.g. "from node x", and each column represents "to node y". It is possible that one or more nodes is connected to every other node (including itself, though it's not always done), so the number of columns necessarily equals the number of rows; that's a square matrix.

Note that the [square] matrix can show that e.g. there is an edge from node x to y, but that there is no edge from node y to node x; this is because the edges are [assumed to be] uni-directional:

From\To

\ A B C... X Y Z

A 0 . .... . . .

B . 0 .... . . .

C . . 0... . . .

.

.

.

X . . .... 0 1 . // An edge from X to Y...

Y . . .... 0 0 . // ... but no edge from Y back to X!

Z . . .... . . 0

Since no nodes in the above graph are connected to themselves, the diagonal is all 0's.

If the edges are intended to be bi-directional, the matrix can be reduced to the upper-right, or lower-left triangular part of the square matrix.

Hope this helps!

Answer 2

By definition it is a square matrix, so yes