\documentclass[]{article}
\usepackage{amsmath,amstext,amssymb}
\usepackage{theorem}

\title{Two alternative prooves of PS3.4} 
\author{6.402}
\date{September 29, 2001}
\begin{document}
\maketitle
\appendix
\begin{description}
\item [Proof using matrix representation of relations] 
%\begin{proof}
Let $M_{R}$ be the boolean matrix associated with Relation $R$. It is easy to verify that $$\text{$R$ is symmetric} \Leftrightarrow \text{$M_R$ is symmetric}.$$ Since $S=R^*=\bigcup_{n=1}^{\infty}R^n$, the corresponding boolean matrix of $S$ is $$M_{S}=\bigcup_{n=1}^{\infty}M_{R}^n,$$ where matrix multiplications are redefined by replacing $\ast$ and $+$ in the ordinary case with $\land$ and $\lor$ respectively. In order to prove that $S$ is symmetric we only need to show  that $M_S$ is symmetric.  Following the fact that if $M_1$ and $M_2$ are two symmetric matrices then both $M_1^n$ and $M_1+M_2$ are symmetric, we know that $M_S$ is symmetric. Therefore, $S$ is symmetric. \\
The following two results are used in the above proof:
\begin{enumerate}
\item If $M$ is a symmetric matrix then $M^n$ is also symmetric. \\
Proof by induction: $$P(n):\ M^n\ \text{is symmetric where}\ n\in \mathbb{Z}^+ .$$
\begin{itemize}
\item {\bf Base Case:} Since $M$ is symmetric, $P(1)$ is true.
\item {\bf The Inductive Step:} Assume that $P(n)$ is true, that is, $(M^n)^T=M^n$, we need to show $P(n+1)$ is true. We know that $M^{n+1}=M^n\ast M$ and $(M^{n+1})^T=M^T\ast (M^{n})^T$. From the induction hypothesis, it follows that $(M^{n+1})^T=M^T\ast (M^{n})^T=M\ast M^n=M^{n+1}$. Therefore, $M^{n+1}$ is symmetric. This shows that $\forall n \in \mathbb{Z}^+$, $P(n)\longrightarrow P(n+1)$ and completes the proof by induction. 
\end{itemize}
\item If $M_n$ are $m \times m$ symmetric matrices then $M=\sum_{n=1}^{\infty} M_n$ is also a $m \times m$ symmetric matrix.\\
This is true because
$$M[i,j]=\sum_{n=1}^{\infty}M_n[i,j]=\sum_{n=1}^{\infty}M_n[j,i]=M[j,i].$$
\end{enumerate}
%\end{proof}

\item [Proof using graph representation of relations] 
%\begin{proof}
Let $G_R$ be the directed graph defined by $(A,R)$. Since $R$ is symmetric, if $(a,b)$ is an edge of $G_R$ then $(b,a)$ must also be an edge of $G_R$. From the definition of $R^*$ we know that if $(a,b)\in R^*$ then there exists a path $$(a,x_1),(x_1,x_2),\dots,(x_{m-1},x_m),(x_m,b)$$ between $a$ and $b$ in $G_R$. Since $R$ is symmetric,  
$$(b,x_{m}),(x_{m},x_{m-1}),\dots,(x_2,x_1),(x_1,a)$$ must also be a path in $G_R$. Therefore, by the definition of $R^*$ again we know that $(b,a)\in R^*$. It follows that $R^*$ is symmetric, that is, $S$ is symmetric.
%\end{proof}
\end{description}

\end{document}
