%\batchmode
\documentclass[12pt]{article}
\topmargin -0.5in
\pagestyle{empty}
\oddsidemargin 0pt
\textwidth 6.7in
\textheight 9.5in
\newcommand{\bigfrac}[2]{\frac{\textstyle #1}{\textstyle #2}}
   	\def\bbd#1{\leavevmode\setbox0=\hbox{#1}%
   	\kern-.025em\copy0 \kern-\wd0
   	\kern .05em\copy0 \kern-\wd0
  	\kern-.025em\raise.0433em\box0
  	}
   	\def\nexto{\kern -0.54em}
    	\def\DN{ \mbox{\rm {I\ \nexto N}} }
    	\def\DZ{ \mbox{\rm Z \kern -0.82em Z} }
    	\def\DC{ \mbox{\rm\hbox{C \kern-0.8em\raise0.2ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DQ{ \mbox{\rm\hbox{Q \kern-0.85em\raise0.25ex
    	\hbox{\vrule height5.4pt width0.7pt} \kern0.45em}} }
    	\def\DP{ \mbox{\rm\hbox{P\kern-0.75em
	\hbox{\vrule height9pt width0.7pt} \kern0.45em}} }

\newcommand{\mat}[2]{\left( \begin{array}{*{#1}{c}}#2\end{array}\right)}
\newcommand{\matr}[2]{\left( \begin{array}{*{#1}{r}}#2\end{array}\right)}
\newcommand{\dat}[2]{\left| \begin{array}{*{#1}{c}}#2\end{array}\right|}
	


\begin{document}

	\begin{center}
{\bf $\stackrel{\mbox{MA330}}{Sathaye}$
\hfill Note on the Brouncker-Wallis algorithm \hfill  \ \  }
	\end{center}
\hfill \rule{6in}{0.01in}\hfill

We present a convenient method to compute continued fraction expansion
of a number which satisifies a quadratic equation. The calculations are
similar to the euclidean algorithm but is organized as a change of basis
calculation for a quadratic form or equivalently a symmetric matrix.

People with experience in Linear algebra should investigate the
connections.

\begin{enumerate}
\item 
We start with the root of a quadratic equation $aX^2+2bX+c=0$. We shall
associate a $2 \times 2 $ symmetric matrix $\matr{2}{a & b \\ b & c}$.
We will augment a $2 \times 2 $ identity matrix to it on the left to
help us keep track of the change of basis.

We will illustrate the calculations and explain the method at the same
time. So, let us consider the root $\sqrt{7}$ which satisfies the
quadratic equation $x^2-7=0$.

Thus our starting matrix shall be:
$$M_0~=~\left(
\begin{array}{rr|rr}
1 & 0 & 1 & 0 \\ 
0 & 1 & 0 & -7
\end{array}
\right)
.$$

\item The second part of this matrix is related to the quadratic
equation and we change it to a quadratic form in $x,y$ as 
$f(x,y)=x^2-7y^2$.
We calculate $f(1,1) = 1-7=-6$. 

When the evaluation is negative, evaluate $f(t,1)$ for
$t=1,2,\cdots$ until the last value which keeps the same sign, i.e.
keeps the answer negative in this case.

Thus we have $f(1,1)=-6, f(2,1)=4-7=-3,f(3,1)=9-7=2>0$.
So we set $t=2$ and make the transformation $x \rightarrow
x+2y,y\rightarrow y$.

We can do it by hand as $f(x+2y,y)=x^2+4xy-3y^2$. But we want to do it
mechanically and also keep track of the changes. So here are the steps.

We perform the row operation $R_2+2R_1$ i.e. add $2$ times the first row
to the second. At the same time to keep the last part symmetric we make
similar transformation on it, which is $C_4+2C_3$.

Here are the steps:

$$
\left(
\begin{array}{rr|rr}
1 & 0 & 1 & 0 \\ 
0 & 1 & 0 & -7
\end{array}
\right)
\longrightarrow
\left(
\begin{array}{rr|rr}
1 & 0 & 1 & 0 \\ 
2 & 1 & 2 & -7
\end{array}
\right)
\longrightarrow
\left(
\begin{array}{rr|rr}
1 & 0 & 1 & 2 \\ 
2 & 1 & 2 & -3
\end{array}
\right)
~=~ M_1.$$

\item Read off the new quadratic form $f(x,y)=x^2+4xy-3y^2$. 
(Note that it is the exact same answers that we got by hand.)
Now $f(1,1)=1+4-3=2>1$.

In this case, the rule is to try $f(1,t)$ for $t=1,2,\cdots$ as long as
the answer stays positive.

Thus we have $f(1,1)=2,f(1,2)=1+8-12=-3<0$. So we set $t=1$ and make the
transformation $x \rightarrow
x,y\rightarrow y+x$.

Done by hand, this makes $x^2+4x(y+x)-3(y+x)^2 = 2x^2 -2xy - 3y^2$.

The matrix transformations are similar but in reverse, namely $R_1+R_2$
and $C_3+C_4$.

We get:
$$M_1 ~=~ 
\left(
\begin{array}{rr|rr}
1 & 0 & 1 & 2 \\ 
2 & 1 & 2 & -3
\end{array}
\right)
\longrightarrow
\left(
\begin{array}{rr|rr}
3 & 1 & 3 & -1 \\ 
2 & 1 & 2 & -3
\end{array}
\right)
\longrightarrow
\left(
\begin{array}{rr|rr}
3 & 1 & 2 & -1 \\ 
2 & 1 & -1 & -3
\end{array}
\right)
~=~M_2
$$

\item We show the next few steps without detailed explanations.
$$\mbox{ Using $t=1$ we get }
M_3 ~=~
\left(
\begin{array}{rr|rr}
3 & 1 & 2 & 1 \\ 
5 & 2 & 1 & -3
\end{array}
\right)
$$

$$\mbox{ Using $t=1$ again, we get }
M_4 ~=~
\left(
\begin{array}{rr|rr}
8 & 3 & 1 & -2 \\ 
5 & 2 & -2 & -3
\end{array}
\right)
$$
\item The quadratic form is now $f(x,y)=x^2-4xy-3y^2$. Also note that
$8^2-7(3^2) = 64 - 63 =1$. Similarly $5^2 - 7(2^2) = -3$. Thus the
evaluations of the form $x^2-7y^2$ for the pairs in the first two
columns are always recorded in the diagonal of the second matrix. The
reader should verify this. Indeed, this is the point of keeping the first
part of our display!

We thus have our solution of $x^2-7y^2=1$.

If we continue our process, something nice happens.

\item The next step is the transformation $x \rightarrow
x+4y,y\rightarrow y$. since for $f(x,y) = x^2-4xy-3y^2$ we get
$f(1,1)=-6,f(2,1)=-7,f(3,1)=-6,f(4,1)=-3,f(5,1)=2>0$. So we set $t=4$.

The changed matrix is:
$$
M_5 ~=~
\left(
\begin{array}{rr|rr}
8 & 3 & 1 & 2 \\ 
37 & 14 & 2 & -3
\end{array}
\right)
$$

\item
Note that $M_5$ and $M_1$ have the same second parts, so the quadratic
form has repeated!
Thus any further steps shall be periodic from now on.

Also, if we keep track of the values of $t$ in each step, we get the
continued fraction expansion of $\sqrt{7}$. In our case, the values are:
$2,1,1,1,4$ with the last $4$ being repeated!
verify this by what you already know.

Indeed, we could have just saved these values and could reconstruct the
first part of our matrix starting from the identity. Study this!




\end{enumerate}

\vspace*{\fill}
\end{document}



