\documentclass{article}
\usepackage[affil-it]{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=false,pdfborder={0 0 0}}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\begin{document}
\title{Adjacency Matrix}
\author{Rikki}
\affil{Affiliation not available}
\date{\today}
\maketitle
The adjacency matrix is used in discrete mathematics to represent~the
number of ways in which we can walk from one vertex to another within a
graph. Any graph can be shown in an adjacency matrix where both the rows
and columns are labeled with our graph vertices. We denote each entry as
\(\left(i,j\right)\)~which counts the number of adjacent edges between the
\(i^{th}\)~row and \(j^{th}\)~column. We also say
that~\(a_{i,j}\)~represents the number in row~\(i\),
column~\(j.\)~The adjacency matrix is made up of~graph
vertices that are either a~\(0\)~or~\(1.\)~To
decide which entry to write in the matrix, we use
a~\(0\)~if vertex~\(i\)~is not adjacent to
vertex~\(j\)~and we use a~\(1\)~if
vertex~\(i\)~is adjacent to vertex~\(j.\)\\
For example,~\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/Screen-Shot-2016-04-04-at-3.52.17-PM/Screen-Shot-2016-04-04-at-3.52.17-PM}
\end{center}
\end{figure}
Notice, that both vertices~\(1\)~and \(3\)~are
each adjacent to
vertices~\(2\)~and~\(4.\)~Vertices~\(2\)~and
\(4\)~are each adjacent to
vertices~\(1\)~and~\(3.\)~With that being said,
we can write out our adjacency matrix as follows:~\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/Screen-Shot-2016-04-04-at-4.04.01-PM/Screen-Shot-2016-04-04-at-4.04.01-PM}
\caption{{Notice that our adjacency matrix is symmetric with \(0\)'s
on the diagonal. All adjacency matrices will be adjacent if the given
graph in undirected. ~ ~ ~ ~~%
}}
\end{center}
\end{figure}
We can use our adjacency matrix to count the number of ways to walk
along a graph. To find the number of length \(L\)~walks
from \(i\)~to \(j\), we have to take our
matrix \(A\)~and raise it to the \(L^{th}\)~power,
\(A^L\), and find the entry that is in the
\(\left(i,j\right)\)~position to find the solution. From our adjacent
matrix above, we can calculate how many length \(1\)~walks
there are from vertices~\(1\)~to~\(4.\)~Looking
at the entry for~\(\left(1,4\right)\)~we see a~\(1.\)~Thus,
there is only one way to walk this path of length~\(1.\)~\\
\textbf{Suggested Exam Problem:} From the adjacency matrix above, how
many length~\selectlanguage{english}\(8\)~walks are there from
vertices~\selectlanguage{english}\(1\)~to~\selectlanguage{english}\(4\)?\\
References:\\
Adjacency Matrix. Retrieved
from~\url{http://mathworld.wolfram.com/AdjacencyMatrix.html}\\
Benjamin, A. T. (2009).~\emph{Discrete Mathematics}. The Great Courses.
Print.
\selectlanguage{english}
\FloatBarrier
\end{document}