\documentclass[11pt]{article}


\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in



\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\input epsf
\usepackage [usenames,dvipsnames]{color}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\pa}{\partial}
\renewcommand{\P}{\mathcal P}
\newcommand{\cL}{\mathcal L}
\renewcommand{\O}{\Omega}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}
\usepackage{graphicx}
\usepackage{tikz}
\oddsidemargin=-0.0cm
\evensidemargin=-0.0cm
\topmargin=-0.0cm
\textwidth=7in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\def\ds{\displaystyle}
\def\ul{\underline}
\def\mb{\mathbf}


\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}



\title{$Ax=b$ and $Ax=0$}
\pagestyle{myheadings}
%\author{October 1, 2015}
\date{}
\def\ds{\displaystyle}
\def\ul{\underline}

\begin{document}
\maketitle



\begin{theorem}
Let $A$ be a square $n\times n$ matrix. Then $Ax=b$ has a unique solution if and
only if the only solution of $Ax=0$ is $x=0$.   Let $A=[A_1, A_2,
\dots, A_n]$. A rephrasing of this
is (in the square case) $Ax=b$ has a unique solution exactly when
$\{A_1, A_2, \dots, A_n\}$ is a linearly independent set.
\end{theorem}

\begin{proof}
First, if $Ax=b$ has a unique solution (call it $x_1$), then $Ay=0$ can't have  nonero
solution.  For if we have $Ay=0$ with $y\ne 0$ then $x_1+y$ would
give a new solution of $Ax=b$. 

So assume the only solution of $Ax=0$ is $x=0$. Consider the equations

\begin{align*}
a_{11}x_1 &+a_{12}x_2 + \dots +a_{1n}x_n &=0\\
a_{21}x_1 &+ a_{22}x_2 + \dots +a_{2n} x_n &=0\\
\vdots& &=0\\
a_{n1}x_1 & +a_{n2}x_2 + \dots + a_{nn}x_n &=0
\end{align*}

The coefficients of $x_1$ cannot all be $0$ or else  $x_1=1,
x_2=0,\dots, x_n=0$ would be a non zero solution of $Ax=0$.  By
rearranging the equations we may assume $a_{11} \ne 0$ and subtract
multiples of the first equation from the rest to produce a new set of
equivalent equations


\begin{align*}
a_{11}x_1 &+a_{12}x_2 + \dots +a_{1n}x_n &=0\\
&+ a_{22}x_2 + \dots +a_{2n} x_n &=0\\
\vdots& &=0\\
 & +a_{n2}x_2 + \dots + a_{nn}x_n &=0,
\end{align*}
where I have used the same letters $a_{ij}$ to represent the new
equivalent equations (which still only have $x=0$ as solution).
Proceeding in a similar manner (perhaps by interchanging some rows) we
get a set of equivalent equations (new notation) of the form

\[
Ux=
\begin{bmatrix}
    u_{11}       & u_{12} & u_{13} & \dots & u_{1n} \\
0     & u_{22} & u_{23} & \dots & u_{2n} \\
    \hdotsfor{5} \\
   0      & 0 & 0& \dots & u_{nn}
\end{bmatrix}
\begin{bmatrix}
x_1\\x_2\\ \vdots \\ x_n
\end{bmatrix}
=
\begin{bmatrix}
0\\0\\\vdots\\0
\end{bmatrix}
\]
where every $u_{kk} \ne 0$. Now if we perform the identical steps on
the system $Ax=b$ we find an equivalent set of equations of the form
\[ Ux=
\begin{bmatrix}
    u_{11}       & u_{12} & u_{13} & \dots & u_{1n} \\
0     & u_{22} & u_{23} & \dots & u_{2n} \\
    \hdotsfor{5} \\
   0      & 0 & 0& \dots & u_{nn}
\end{bmatrix}
\begin{bmatrix}
x_1\\x_2\\ \vdots \\ x_n
\end{bmatrix}
=
\begin{bmatrix}
c_1\\c_2\\\vdots\\c_n
\end{bmatrix}
\]
Where the $c_k$ are the result of applying the same operations on the
$b_k$.  This is a summary of Gauss elimination.  The final set of
equations $Ux=c$ has a unique solution and this solution is the unique
solution of $Ax=b$.  
\end{proof}





%\bibliographystyle{amsplain}
%\bibliography{header}

\end{document}
