by simply looking at the graph. In this problem we will see that linear algebra can be used to decide if a graph contains a triangle.

$($a$)$ The adjacency matriz A of a graph G with n nodes is a nn matrix defined as follows. The rows and columns of A are indexed by the node labels $1,...,$n and the $($i$,$ j$)-$entry of A is $1$ if the pair $($i$,$j$)$ is an edge in G and $0$ otherwise. $($An example can be seen in Problem $2\mathrm{.}4$A on page $76$ in Strang's book. See also Chapter $3$ of the lecture notes.$)$

Write down the adjacency matrix of the graph G shown above.

$($b$)$ Let B$=$ A $^2*$ where A is the adjacency matrix of G$.$ The entry b ij in B is the dot product of two vectors sitting in A$.$ Which vectors are they? In our example, how is b$\_\{23\}$ formed?

$($c$)$ For three nodes i $*,$ k from G$.$ argue that a ik a kj is $1$ exactly when k is a common neighbor of i and j$.$

$($d$)$ Using the above, what does b ij count?

$($e$)$ The nodes i$,$ j$.$k form a triangle if and only if i and jare neighbors and k is a common neighbor of i and j$.$ If i$,$ j$,$ k is a triangle what property must a ij and b ij have?

$($f$)$ Putting all this together can you construct an algorithm that takes as input two indices $1,1,$ and determines whether or not there exists a triangle with the edge between i and jas one of the sides. Justify your algorithm. Think of an algorithm that uses A and B$.$ If you use only A you will likely have a less efficient algorithm. You don't need to write computer code, just writing out the steps in words is enough.

$($g$)($optional$)$ If you know about running times of algorithms, do you see how fast this algorithm runs? Is it faster than checking all triples of nodes in G$?$