# Get degree distribution of a graph from its Adjacency matrix

How can you get the degree distribution of a graph from the following formulas, and also determine if those graphs are directed or not ? :

where $\delta$ represents the Kronecker delta

a) $A_{ij} = \delta_{i,j+1}$ for $j< N$ , and $A_{iN} = 0.$

b) $A_{ij} = 1$ for all $i,j \in {1,.....,N}$

I tried to represent those graphs with a $3$ node graph to begin but for the first graph I get an adjacency matrix where the diagonal is all made of $1$ and the rest $0$ which is impossible.

Do you have any ideas ?

• – Salomo Apr 9 '15 at 9:34
• Thank you but I dont see how it can help solve the two questions – user2505650 Apr 9 '15 at 9:36
• Actually I don't quite understand your question, can you state it more formally... – Salomo Apr 9 '15 at 10:00

## 1 Answer

Start by looking at a small example of each graph, say the case $N=4$. The second one is easy: the adjacency matrix is

$$\begin{array}{cc} &v_1\;\;v_2\;\;v_3\;\;v_4\\ \begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}&\begin{bmatrix} 1&1&\color{red}1&1\\ 1&1&1&1\\ \color{blue}1&1&1&1\\ 1&1&1&1 \end{bmatrix} \end{array}$$

Here the red $1$ indicates that there is an edge from $v_1$ to $v_3$, and the blue $1$ shows an edge from $v_3$ to $v_1$. In fact, you can see that all of the off-diagonal entries come in symmetric pairs, so the graph is not directed. (It’s the complete graph on $4$ vertices, plus a loop at each vertex.)

For the first one we have to work a little harder. For $j<N$ we have

$$A_{ij}=\delta_{i,j+1}=\begin{cases} 1,&\text{if }i=j+1\\ 0,&\text{otherwise}\;, \end{cases}\tag{1}$$

and we have $A_{iN}=0$ for all $i$. That last clause means that the last column of the adjacency matrix is all $0$, and it turns out that $(1)$ puts $1$s on the first subdiagonal, the diagonal immediately under the main diagonal: those are the positions whose row numbers are $1$ more than their column numbers. If $N=4$, for instance, we have $A_{21}=A_{32}=A_{43}=1$, and every other entry in the matrix is $0$. Thus, the matrix is

$$\begin{array}{cc} &v_1\;\;v_2\;\;v_3\;\;v_4\\ \begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}&\begin{bmatrix} 0&0&0&0\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0 \end{bmatrix} \end{array}$$

There are no $1$s that are symmetrically placed on opposite sides of the main diagonal, so there are no vertices $v_i$ and $v_j$ with an edge from $v_i$ to $v_j$ and also an edge from $v_j$ to $v_i$; thus, this graph is directed. Can you sketch and identify it? It has a very simple shape.

Now just generalize from $4$ to $N$. The degree distributions can easily be found once you identify the graphs. Alternatively, note that if the graph is directed, the row for $v_i$ shows edges leaving $v_i$, and the column for $v_i$ shows edges entering $v_i$, and a very similar idea gives you the degrees if the graph is undirected.