linear-algebra--33-miniatures.tex

\begin{comment}  % latex-focus

  \section{Matousek -- 33 Miniatures}

  \subsection{Fibonacci - matrix multiplication}\label{fibonacci-matrix-multiplication}

  \begin{definition*}
    The Fibonacci sequence $0, 1, 1, 2, 3, 5, 8, ...$ is defined by
    \begin{align*}
    x_0 &= 0\\
    x_1 &= 1\\
    x_{n} &= x_{n-1} + x_{n-2}, ~~~~~~~ n \geq 2.
  \end{align*}
\end{definition*}

\begin{remark*}
  The sequence can be generated by taking $\vecMM{x_1}{x_0} = \vecMM{1}{0}$ as the initial state and multiplying
  repeatedly by $A = \matMMxNN{1}{1}
  {1}{0}$, yielding the sequence
  \begin{align*}
    \vecMM{1}{0}, \vecMM{1}{1}, \vecMM{2}{1}, \vecMM{3}{2}, \vecMM{5}{3}, \vecMM{8}{5}, ....
  \end{align*}
  Thus $\vecMM{x_{n+1}}{x_n} = A^n\vecMM{1}{0}$.\footnote{The book describes a trick for
    efficiently raising a matrix $A$ to an integer power $n$ involving using the binary expansion
    of $n$ to determine the computations to perform. So $\log_2(n)$ matrix multiplications rather
    than $n$.}
\end{remark*}

\newpage
\subsection{Fibonacci - sequence space}

Let $V$ be the vector space containing all sequences of real numbers
$u_0, u_1, \ldots$.

% \begin{proof}
%   This is a vector space since:
%   \begin{enumerate}
%   \item It's an Abelian group under addition (the zero sequence is the additive identity, inverse
%     is obtained by negating each element, addition is associative and commutative)
%   \item Closed under scalar multiplication since $\lambda u_0, \lambda u_1, ... \in V$.
%   \end{enumerate}
% \end{proof}

Let $W$ be the subspace of $V$ containing sequences such that $u_{n+2} = u_{n+1} + u_n$ for all
$n \geq 0$.

% \begin{proof}
%   $W$ is a subspace because:
%   \begin{enumerate}
%   \item $W$ contains the zero sequence.
%   \item Let $(u)_{n\geq 0}, (v)_{n\geq 0} \in W$. Then
%     $$(u + v)_{n+2} = u_{n+1} + u_n + v_{n + 1} + v_n = (u + v)_{n+1} + (u + v)_n,$$ and
%     $$(\lambda u)_{n+2} = \lambda u_{n+1} + \lambda u_n = (\lambda u)_{n+1} + (\lambda u)_n.$$
%   \end{enumerate}
% \end{proof}

\begin{claim*}
  A basis for $W$ is
  \begin{align*}
    e_1 &= 0, 1, 1, 2, 3, 5, 8, \ldots\\
    e_2 &= 1, 0, 1, 1, 2, 3, 5, \ldots.
  \end{align*}
\end{claim*}
\begin{proof} We need to show that $e_1$ and $e_2$ are linearly independent and spanning.
  Note that every sequence $u \in W$ is determined by the first two values $(u_0, u_1)$.
  Define the projection $P: W \to \R^2$ by $p(u) := (u_0, u_1)$. Note that $P$ is linear \footnote{
    \begin{align*}
      P(\lambda u) &= (\lambda u_0, \lambda u_1) = \lambda P(u)\\
      P(u + v)     &= (u_0 + v_0, u_1 + v_1) = (u_0, u_1) + (v_0, v_1) = P(u) + P(v).
    \end{align*}
  }, injective and invertible.
  Let $i = (0, 1) \in \R^2$ and $j = (1, 0) \in \R^2$.
  Therefore $P^\1(i), P^\1(j) = e_1, e_2$ is a basis for $W$, by theorem (\ref{transformed-basis-is-a-basis}).
\end{proof}

Now we look for a different basis of $W$. Specifically, we have an inspiration: we seek sequences
$u \in W$ of the form $u_n = \tau^n$ for some $\tau$. Thus $\tau$ must satisfy
$\tau^{n+2} = \tau^{n+1} + \tau^n$ for all $n \geq 0$. We solve this for $n=0$.  We have
$\tau^2 = \tau + 1$, therefore $\tau_1 = \frac{1 + \sqrt{5}}{2}$ and
$\tau_2 = \frac{1 - \sqrt{5}}{2}$.

Define two new sequences $e'_1 = \tau_1^0, \tau_1^1, \ldots$ and
$e'_2 = \tau_2^0, \tau_2^1, \ldots$.

\begin{claim*}
  $e'_1, e'_2$ is another basis for $W$.
\end{claim*}

\begin{proof}
  We need only they are linearly independent. If they are, then they span $W$ since $W$ is
  2-dimensional.
  So suppose $\lambda_1e'_1 + \lambda_2e'_2 = 0$. Then, from considering the first two elements, we
  have
  $\begin{cases}
    \lambda_1 + \lambda_2 = 0\\
    \lambda_1\tau_1 + \lambda_2\tau_2 = 0.
  \end{cases}$
  Therefore $\lambda_1(\tau_1 - \tau_2) = 0$, so $\lambda_1 = \lambda_2 = 0$, as required.
\end{proof}

Therefore for all $u \in W$ there exist $\lambda_1, \lambda_2$ such that
$u = \lambda_1e'_1 + \lambda_2e'_2$.

In particular, there exist $\lambda_1, \lambda_2$ such that
$e_1 = 0, 1, 1, 2, 3, 5, 8, \ldots = \lambda_1e'_1 + \lambda_2e'_2$.

We can use the first two elements of the sequence to solve for $\lambda_1$ and $\lambda_2$. We have
$\begin{cases}
  0 = \lambda_1 + \lambda_2\\
  1 = \lambda_1\tau_1 + \lambda_2\tau_2
\end{cases}$, therefore $\lambda_1 = \frac{1}{\tau_1 - \tau_2} = \frac{1}{\sqrt{5}}$ and
$\lambda_2 = \frac{-1}{\sqrt{5}}$.

The $n$-th element of the Fibonacci sequence is therefore
\begin{align*}
  \lambda_1\tau_1^n + \lambda_2\tau_2^n =
  \frac{1}{\sqrt{5}}
  \(
  \(\frac{1 + \sqrt{5}}{2}\)^n -
  \(\frac{1 - \sqrt{5}}{2}\)^n
  \).
\end{align*}

\newpage
\subsection*{Fibonacci - eigenbasis}

(Not in book.)

Recall from (\ref{fibonacci-matrix-multiplication}) that the Fibonacci sequence can be generated by
taking $\vecMM{1}{0}$ as the initial state and multiplying repeatedly by
$A = \matMMxNN{1}{1} {1}{0}$. Thus $\vecMM{x_{n+1}}{x_n} = A^n\vecMM{1}{0}$.

We can compute the matrix power via ``diagonalization'': i.e., in a basis defined by two
eigenvectors the matrix of the linear transformation is diagonal and thus the matrix power can be
computed trivially.

$|A| \neq 0$ therefore $A$ is full rank and has two linearly independent eigenvectors. Let these be
$\vecMM{v_{11}}{v_{21}}$ and $\vecMM{v_{12}}{v_{22}}$ and let $\tau_1, \tau_2$ be associated
eigenvectors. Define $V := \matMMxNN{v_{11}}{v_{12}}{v_{21}}{v_{22}}$ and
$T := \matMMxNN{\tau_1}{0}{0}{\tau_2}$. Then
\begin{align*}
  A^n = V^\1T^nV.
\end{align*}

The characteristic polynomial of $A$ is $\tau^2 - \tau - 1 = 0$, therefore the eigenvalues are
$\tau_1 = \frac{1 + \sqrt{5}}{2}$ and $\tau_2 = \frac{1 - \sqrt{5}}{2}$.

Let $v(\tau) = \vecMM{v_1}{1}$ be an eigenvector associated with eigenvalue $\tau$. (Since there is
a line of eigenvectors for each eigenvalue, we make an arbitrary choice of $v_2 = 1$ to find
particular eigenvectors.)

We have
\begin{align*}
  \(A - \tau I\)v &= 0\\
  \matMMxNN{1 - \tau}{1}
           {1}       {-\tau} \vecMM{v_1}{v_2} &= 0\\
  &\begin{cases}
    v_1(1 - \tau) + v_2 = 0~~~~~&(1)\\
    v_1 - \tau v_2 = 0~~~~~&(2)
  \end{cases}
\end{align*}
From (2) therefore $v(\tau) = \vecMM{\tau}{1}$ and the eigenvectors are the columns of
$V := \matMMxNN{\tau_1}{\tau_2}{1}{1}$.

Note that $\tau_1\tau_2 = -4$ therefore $\tau_2 = \frac{-4}{\tau_1}$.
% $\frac{\tau_1}{\tau_2} = \frac{\tau_1^2}{\tau_1\tau_2} = -\frac{\tau_1^2}{4}$.

Therefore
\begin{align*}
  A^n &= V^\1T^nV\\
      &= \frac{1}{\tau_1 - \tau_2}
        \matMMxNN
        {1}
        {-\tau_2}
        {-1}
        {\tau_1}
        \matMMxNN
        {\tau_1^n}
        {0}
        {0}
        {\tau_2^n}
        \matMMxNN
        {\tau_1}
        {\tau_2}
        {1}
        {1}\\
      &= \frac{1}{\tau_1 + \frac{2^2}{\tau_1}}
        \matMMxNN
        {1}
        {\frac{2^2}{\tau_1}}
        {-1}
        {\tau_1}
        \matMMxNN
        {\tau_1^n}
        {0}
        {0}
        {\frac{-2^{2n}}{\tau_1^n}}
        \matMMxNN
        {\tau_1}
        {\frac{-2^2}
        {\tau_1}}
        {1}
        {1}\\
      &= \frac{1}{\tau_1 + \frac{2^2}{\tau_1}}
        \matMMxNN
        {1}
        {\frac{2^2}{\tau_1}}
        {-1}
        {\tau_1}
        \matMMxNN
        {\tau_1^{n+1}}
        {-2^2\tau_1^{n-1}}
        {\frac{-2^{2n}}{\tau_1^n}}
        {\frac{-2^{2n}}{\tau_1^n}}\\
      &= \frac{1}{\tau_1 + \frac{2^2}{\tau_1}}
        \matMMxNN
        {\tau_1^{n+1} -\frac{2^{2(n+1)}}{\tau_1^{n+1}}}
        {-2^2\tau_1^{n-1} - \frac{2^{2(n+1)}}{\tau_1^{n+1}}}
        {-\tau_1^{n+1} - \frac{2^{2n}}{\tau_1^{n-1}}}
        {2^2\tau_1^{n-1} - \frac{2^{2n}}{\tau_1^{n-1}}}\\
      &= \frac{1}{\tau_1^{n+2} + 2^2\tau_1^n}
        \matMMxNN
        {\tau_1^{2(n+1)} - 2^{2(n+1)}}
        {-2^2\tau_1^{2n} - 2^{2(n+1)}}
        {-\tau_1^{2(n+1)} - 2^{2n}\tau_1^2}
        {2^2\tau_1^{2n} - 2^{2n}\tau_1^2}\\
\end{align*}

Recall that $\vecMM{x_{n+1}}{x_n} = A^n\vecMM{1}{0}$. Therefore
\begin{align*}
  x_n = \frac
  {-\tau_1^{2(n+1)} - 2^{2n}\tau_1^2}
  {\tau_1^{n+2} + 2^2\tau_1^n}
\end{align*}


% \begin{align*}
%   A^n &= V^\1T^nV\\
%       &= \frac{1}{\tau_1 - \tau_2}
%         \matMMxNN{1}{-\tau_2}
%                  {-1}{\tau_1}
%         \matMMxNN{\tau_1^n}{0}
%                  {0}{\tau_2^n}
%         \matMMxNN{\tau_1}{\tau_2}
%                  {1}{1}\\
%       &= \frac{1}{\tau_1 - \tau_2}
%         \matMMxNN{1}{-\tau_2}
%                  {-1}{\tau_1}
%         \matMMxNN{\tau_1^{n+1}}{\tau_1^n\tau_2}
%                  {\tau_2^n}{\tau_2^n}\\
%       &= \frac{1}{\tau_1 - \tau_2}
%         \matMMxNN{\tau_1^{n+1} - \tau_2^{n+1}}{\tau_1^n\tau_2 - \tau_2^{n+1}}
%                  {-\tau_1^{n+1} + \tau_1\tau_2^n}{-\tau_1^n\tau_2 + \tau_1\tau_2^n}
% \end{align*}


% \begin{align*}
%   (2, 3):~~~~~~~ \sqrt{1 - v_2^2} &= \tau v_2\\
%   1 &= v_2^2(\tau^2 + 1)\\
%   v_2 &= \sqrt{\frac{1}{\tau^2 + 1}}\\
%   v_2 &= \sqrt{\frac{2}{5 \pm \sqrt 5}}\\
%   (2): ~~~~~~~v_1 = \tau v_2 &= \frac{1 \pm \sqrt 5}{2}\sqrt{\frac{2}{5 \pm \sqrt 5}}\\
%   v_1 &= \frac{1 \pm \sqrt 5}{\sqrt 2 \sqrt{5 \pm \sqrt 5}}\\
%   (1): ~~~~~~~v_1\(\frac{-1 \mp \sqrt{5}}{2}\) &= -\sqrt{\frac{2}{5 \pm \sqrt 5}}\\
%               v_1 &= \frac{-2}{-1 \mp \sqrt{5}}\sqrt{\frac{2}{5 \pm \sqrt 5}}\\
% \end{align*}

%   \tau v_2(1 - \tau) + v_2 &= 0\\
%   v_2(\tau - \tau^2 + 1) &= 0

\newpage
\subsection{Fibonacci - generating function}

\begin{definition*}[Fibonacci sequence]
  The Fibonacci sequence is defined by $a_0 = 1, a_1 = 1, a_n = a_{n-1} + a_{n-2}$.
\end{definition*}

\begin{definition*}[Generating function] The generating function of the sequence
  $(a_n)_{n=0}^\infty$ is $\sum_{n=0}^\infty a_nx^n$.
\end{definition*}

\begin{theorem*}
  The $n$-th Fibonacci number is...
\end{theorem*}

\begin{proof}
  The generating function of the Fibonacci sequence is
  \begin{align*}
    f(x) &= a_0 + a_1x + \sum_{n=2}^\infty a_nx^n\\
         &= 1 + x + \sum_{n=2}^\infty (a_{n-2} + a_{n-1})x^n\\
%         &= 1 + x + \sum_{n=2}^\infty a_{n-2}x^n + \sum_{n=2}^\infty a_{n-1}x^n\\
         &= 1 + x + x^2\sum_{n=2}^\infty a_{n-2}x^{n-2} + x\sum_{n=2}^\infty a_{n-1}x^{n-1}\\
         &= 1 + x + x^2f(x) + x\(f(x) - 1\)\\
         &= 1 + f(x)(x^2 + x),
  \end{align*}
  so
  \begin{align*}
    f(x) &= \frac{1}{1 - x - x^2}\\
         &= \frac{1}{\(x - \frac{1 + \sqrt 5}{2}\)\(x - \frac{1 - \sqrt 5}{2}\)}\\
         &= \frac{4}{(2x - 1 - \sqrt 5)(2x - 1 + \sqrt 5)}.
  \end{align*}
  \newpage
  Performing a partial fraction decomposition,
  \begin{align*}
    \frac{4}{(2x - 1 - \sqrt 5)(2x - 1 + \sqrt 5)}
    &= \frac{A}{2x - 1 - \sqrt 5} + \frac{B}{2x - 1 + \sqrt 5}\\
    4 &= x(2A + 2B) - (A + B) + \sqrt{5}(A - B)\\
    \begin{cases}
      A + B = 0\\
      A - B = \frac{4}{\sqrt 5}
    \end{cases}
  \end{align*}
  so $A = \frac{1}{\sqrt 5}$, $B = -\frac{1}{\sqrt 5}$ and the generating function is
  \begin{align*}
    f(x) &= \frac{1}{\sqrt 5}\(\frac{1}{2x - 1 - \sqrt 5} + \frac{1}{2x - 1 + \sqrt 5}\).
  \end{align*}
  Taking derivatives,
  \begin{align*}
    \sqrt{5}f'(x)     &= -\frac{2}{(2x - 1 - \sqrt{5})^2} - \frac{2}{(2x - 1 + \sqrt{5})^2}\\
    \sqrt{5}f''(x)    &= \frac{4}{(2x - 1 - \sqrt{5})^3} + \frac{4}{(2x - 1 + \sqrt{5})^3}\\
    \sqrt{5}f^{(n)}(x) &= (-1)^n\(\frac{2^n}{(2x - 1 - \sqrt{5})^{n+1}} + \frac{2^n}{(2x - 1 + \sqrt{5})^{n+1}}\)\\
    \sqrt{5}f^{(n)}(x) &= (-2)^n\(\frac{1}{(2x - 1 - \sqrt{5})^{n+1}} + \frac{1}{(2x - 1 + \sqrt{5})^{n+1}}\),
  \end{align*}
  and so the Maclaurin expansion of $f(x)$ is
  \begin{align*}
    \sqrt{5}f(x) = \sum_{n=0}^\infty \frac{(-2)^n}{n!(2x - 1 - \sqrt{5})^{n+1}}x^n
  \end{align*}
\end{proof}



\newpage
\subsection{The Clubs of Oddtown}

Oddtown has two rules about clubs:
\begin{itemize}
\item Every club must have an {\it odd} number of members.
\item The number of members in the intersection of any two distinct clubs must be {\it even}.
\end{itemize}

\begin{theorem}
  Under these rules, the number of clubs is less than the number of members.
\end{theorem}

\begin{proof}
  Let $m$ be the number of clubs and $n$ be the number of members.

  Let $A = (a_{ij})$ be a matrix over the finite field $F_2$, where $a_{ij} =
  \begin{cases}
    1 ~~~~ \text{if person $j$ is a member of club $i$},\\
    0 ~~~~ \text{otherwise}.
  \end{cases}
  $

  Thus rows correspond to clubs, and the $(i,j)$-th entry of $AA^T$ is 1 if the intersection of club
  $i$ and club $j$ is odd, and 0 if even.

  Therefore the rules imply that $AA^T = I_m$. I.e. the rank of $AA^T$ is $m$.

  But the rank of a product of matrices cannot be larger than the minimum rank of any one factor, so
  $m \leq n$.
\end{proof}

\end{comment}  % latex-focus
\subsection{Same-size intersections}

\begin{theorem*}[Generalized Fisher inequality]~\\
  Let $S$ be a set of $n$ elements, and let $C_1, C_2, ..., C_m$ be distinct and non-empty subsets of
  $S$. Further, suppose that every intersection $C_i \cap C_j, i \neq j$, is the same size. Then $n \geq m$.
\end{theorem*}

Informally: if you have $n$ objects you can't form more than $n$ subsets such that the subsets have
same-size intersections.

Note that there are $2^n - 1$ non-empty subsets.

\begin{example*}~\\
  \begin{enumerate}
  \item If $S$ is empty then there is no such collection of subsets.
  \item If $|S| = 1$ then there is one subset and there are no intersections, so they are all the same
    size. We see than $m = n$.
  \item If $|S| = 2$ then there are 3 non-empty subsets: $\{1\}, \{2\}, \{1, 2\}$. We can do $m=2$
    but we cannot do $m=3$. Thus $m = n$.
  \item If $|S| = 3$ then there are 7 non-empty subsets.
\begin{verbatim}
  1
  2
  3
  12
  13
  23
  123
  \end{verbatim}
    The claim is that we cannot find a same-sized-intersection collection of size more than 3.
  \end{enumerate}
\end{example*}


\begin{comment}  % latex-focus

\end{comment}  % latex-focus