        \problemdata       % Takes 5 *mandatory* arguments
        {adjmat-props}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS4-6, F99 tut} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).


\begin{problem}
%-----------------------------------------------
% source: used by Albert in Fall 99, occasional tutorial
% topics: relations, adj matrices, paths, graphs

Let $A$ be the adjacency matrix for a digraph $G$ with $n$
vertices.  Note that $A$ is a zero-one valued $n \times n$ matrix.  In
this problem we use the Boolean ``OR'' operation, $\vee$, instead of
``+'' when multiplying zero-one valued matrices (this is called
``boolean'' matrix product).

\problempart

For $k \geq 1$, let $A^k$ be the $k$th {\em Boolean} power
of $A$.  Prove that ${A^k}_{ij} = 1$ iff there is a directed path of
length $k$ from the $i$th to the $j$th vertex of $G$.

  \solution{%
    We prove this by induction on $k$.
%    Let $P(n)$ be the predicate that ${A^n}_{ij} = 1$ iff there is a
%    directed path of length $n$ from the $i$th to the $j$th vertex
%    of $G$.  We prove that $P(n)$ holds for all $n\geq 1$ by induction
%    on $n$.

    {\bf Inductive Hypothesis:} $P(k): {A^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex
    of $G$.
 

    {\bf Base Case:} $k = 1$.  By the definition of an adjacent matrix
    A, $A_{ij} = 1$ iff there is a directed edge (directed path of
    length $k = 1$) from the $i$th to the $j$th vertex of $G$.
 

    {\bf Inductive Step:} Assume $P(k)$ to prove $P(k+1)$. We know,
    \[
        {A^{k+1}}_{ij} = \bigvee_{l \in G} ({A^k}_{il} \wedge A_{lj})
    \]

Now we consider both directions for the iff.


[$\Leftarrow$]
Suppose there is a directed path of length $k+1$ from the $i$th to the
$j$th vertex of $G$.  This path looks like $i, i_1, i_2, \dots i_k, j$.
Then consider $l = i_k$.  ${A^k}_{il} = 1$ (inductive hypothesis).
${A}_{lj} = 1$ (there is an edge from $i_k$ to $j$), under the Case 1
assumption.  Therefore,
\[
({A^k}_{il} \wedge A_{lj}) = 1
\]
which implies
\[
{A^{k+1}}_{ij} = 1.
\]

[$\Rightarrow$] 
Suppose that ${A^{k+1}}_{ij} = 1$. 
Then $\exists\; l \in V_G : ({A^k}_{il} \wedge A_{lj}) = 1$.  Thus there
is an edge from $l$ to $j$ and there is path of length $k$ from $i$ to
$l$(by the inductive hypothesis) which looks like $i, i_1, i_2, \dots
i_{k-1}, l$.  Thus, there is a path of length $k+1$ from $i$ to $j$
which hits $l$ on the $k$th step and then has the $k+1$st edge from
$l$ to $j$.  This path follows the vertices: $i, i_1, i_2, \dots
i_{k-1}, l, j$.

Q.E.D.
}


\problempart Let $B = A \vee I$ where $I$ is the $n \times n$ identity
matrix.  Prove that ${B^k}_{ij} = 1$ iff there is a directed path of
length $\leq k$ from the $i$th to the $j$th vertex of $G$.

  \solution{%
    From part~(a), it can be seen that ${B^k}_{ij} = 1$ iff there is a
    directed path of length $k$ from the $i$th to the $j$th vertex of
    $G'$, where $G'$ is the graph described by the adjacency matrix
    $B$.  Since $G'$ is just $G$ with self loops, a path exists
    between $i$ and $j$ in $G'$ iff a path exists between $i$ and $j$
    in $G$ (all vertices have paths of length $0$ to themselves).

    For any such path between $i$ and $j$ in $G'$, either it uses a
    self-loop edge or it does not.  If it does not, then the
    equivalent path in $G$ will have the same length.  If it does,
    then there is a shorter path in $G$ which can be obtained by not
    using the self loop.  So if there is a path of length $k$ between
    $i$ and $j$ in $G'$ then there is a path of length $\leq k$
    between $i$ and $j$ in $G$.

    If there is a path of length $\leq k$ between $i$ and $j$ in $G$,
    then it can be made to be of length $k$ by using self loops to
    lengthen the path.  Thus there is a path in $G'$ of length $k$ iff
    there is a path in $G$ of length $\leq k$.  Since ${B^k}_{ij} = 1$
    iff there is a path of length $k$ between $i$ and $j$ in $G'$ then
    ${B^k}_{ij} = 1$ iff there is a path of length $\leq k$ between
    $i$ and $j$ in $G$.%
    }%
  

\problempart Conclude that ${B^n}_{ij} = 1$ iff there is a directed
path from the $i$th to the $j$th vertex.

\solution{
If ${B^n}_{ij} = 1$ then there is a directed path from the $i$th to
the $j$th vertex.  If ${B^n}_{ij} = 0$ then there is no path of length
$\leq n$ from the $i$th to the $j$th vertex.  There must also be no path of
length $>n$ from the $i$th to the $j$th vertex.  If there were, then the
path must cross through some vertices twice, since the length of the path is
$>n$.  For those vertices through which the path passes twice, eliminate
the loops so that the path uses no vertex more than once.  This means the
path must be of length $\leq n$, which reaches a contradiction, since we know
that there are no paths from $i$ to $j$ of length $\leq n$.  Therefore, if
${B^n}_{ij} = 0$ there is no path from $i$ to $j$ at all.\\
}

\problempart If $A$ is the matrix for a relation $R$, show that $B^n$
is equal to the reflexive and transitive closure of $R$.

\solution{It is easy to see that the reflexive and transitive
closure of $R$ is $R^*\cup\Delta$, where $R^*$ is the connectivity
relation for $R$ (Rosen, p.~399--400), and $\Delta$ is the diagonal
relation on the set of vertices.

Now, to show that $B^n$ is the matrix of $R^*\cup\Delta$, it suffices
to show that 
$$
\text{for every two vertices $i$, $j$:} \quad
B^n_{ij} = 1 \iff (i,j)\in R^*\cup\Delta.
$$
The case where $i=j$ is easy: By definition of $\Delta$,
$(i,i)\in\Delta$, hence $(i,i)\in R^*\cup\Delta$; and, since there
exists a path (of length~0) from $i$ to $i$, $B^n_{ii}=1$,
by~(c). Therefore, the equivalence holds. 

For the case where $i\neq j$: If $B^n_{ij}=1$, then, by~(c), there is
a path from $i$ to $j$, which is of length at least~1 (because $i\neq
j$). Hence $(i,j)\in R^*$, so $(i,j)\in R^*\cup\Delta$,
too. Conversely, suppose $(i,j)\in R^*\cup\Delta$. Then, since $i\neq
j$, it has to be the case that $(i,j)\in R^*$, hence there exists a
path from $i$ to $j$. Which, by~(c), implies that $B^n_{ij}=1$.

Therefore, the equivalence holds in all cases, which implies $B^n$ is
indeed the matrix of $R^*\cup\Delta$.
}

\end{problem}