Archive

Posts Tagged ‘math1081’

MATH1081 and MATH1231 Cheat Sheets

March 19, 2009 Leave a comment

Just cross posting my cheat sheets from MATH1081 and MATH1231. PDF and LaTeX source (WordPress.com won’t allow .tex uploads) are provided. These are from 08s2, at UNSW. I’ve released them into the public domain, if that is not legally possibly in Australia then lobby your parliament representative.

math1081.pdf

math1231-alg.pdf

math1231-calc.pdf

MATH1081 LaTeX Source

%This work is hereby released into the Public Domain. To view a copy of the public domain dedication, visit http://creativecommons.org/licenses/publicdomain/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

\documentclass[a4paper,10pt]{article}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\setlength\parindent{0mm}
\usepackage{fullpage}
\usepackage{array}
\usepackage[all]{xy}

\usepackage[pdftex,
            pdfauthor={Andrew Harvey},
            pdftitle={MATH1081 Cheat sheet 2008},
            pdfsubject={},
            pdfkeywords={}]{hyperref}

\begin{document}

\section*{Enumeration}
\subsection*{Counting Methods}
Let $\#(n)$ denote the number of ways of doing $n$ things. Then,
$$\#(A\; \mbox{and}\; B) = \#(A) \times \#(B)$$
$$\#(A\; \mbox{or}\; B) = \#(A) + \#(B)$$

($n$ items, $r$ choices)\\
Ordered selection with repetition, $n^r$.\\

Ordered selection without repetition, $P(n,r) = \frac{n!}{(n-r)!}$.\\

Unordered selection without repetition, $C(n,r) = \frac{P(n,r)}{r!}$.\\

$|A \cup B| = |A| + |B| - |A \cap B|$\\

Ordered selection with repeition; WOOLLOOMOOLOO problem.\\

Unordered selection with repetition; dots and lines,
$$\binom{n+r-1}{n-1}$$

Pigeonhole principle. If you have n holes and more than n objects, then there must be at least 1 hole with more than 1 object.

\section*{Recurrences}
\subsection*{Formal Languages}
$\lambda$ represents the \textit{empty word}.
$w$ is just a variable (it is not part of the language)

\subsection*{First Order Homogeneous Case}
The recurrence,\\
\begin{center}$a_n = ra_{n-1}$ with $a_0=A$\\\end{center}
has solution\\
$$a_n=Ar^n.$$

\subsection*{Second Order Recurrences}
$$a_n + pa_{n-1} + qa_{n-2} = 0$$
has characteristic,
$$r^2 + pr + q = 0$$
If $\alpha$ and $\beta$ are the solutions to the characteristic equation, and if they are real and $\alpha \ne \beta$ then,
$$a_n = A\alpha^n + B\beta^n.$$
If $\alpha = \beta$ then,
$$a_n = A\alpha^n + Bn\beta^n.$$

\subsection*{Guesses for a particular solution}
\begin{tabular}{c|c}%{m{width} | m{width}}
 LHS & Guess \\ \hline
$3$ & c \\
$3n$ & $cn + d$\\
$3\times 2^n$ & $c2^n$\\
$3n2^2$ & $(cn+d)2^n$\\
$(-3)^n$ & $c(-3)^n$\\
\end{tabular}

\end{document}

MATH1231-ALG LaTeX Source

%This work is hereby released into the Public Domain. To view a copy of the public domain dedication, visit http://creativecommons.org/licenses/publicdomain/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

\documentclass[a4paper,10pt]{article}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\setlength\parindent{0mm}
\usepackage{fullpage}

\usepackage[pdftex,
            pdfauthor={Andrew Harvey},
            pdftitle={MATH1231 Algebra Cheat sheet 2008},
            pdfsubject={},
            pdfkeywords={},
            pdfstartview=FitB]{hyperref}

\begin{document}

\section*{Vector Spaces}
\subsection*{Vector Spaces}
Vector Space - 10 rules to satisfy, including \begin{small}\textit{(Where $V$ is a vector space.)}\end{small}
\begin{itemize}
\item Closure under addition. If $\mathbf{u}, \mathbf{v} \in V$ then $\mathbf{u} + \mathbf{v} \in V$
\item Existence of zero. $\mathbf{0} \in V$
\item Closure under scalar multiplication. If $\mathbf{u} \in V$ then $\lambda \mathbf{u} \in V$, where $\lambda \in \mathbb{R}$
\end{itemize}

\subsection*{Subspaces}
Subspace Theorem:\\
  A subset $S$ of a vectorspace $V$ is a subspace if:
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item $S$ contains the zero vector.
\item If $\mathbf{u}, \mathbf{v} \in S$ then $\mathbf{u} + \mathbf{v} \in S$ and $\lambda \mathbf{u} \in S$ for all scalars $\lambda$.
\end{enumerate}

\subsection*{Column Space}
The column space of a matrix $A$ is defined as the span of the columns of $A$, written $\mbox{col}(A)$.

\subsection*{Linear Independence}
Let $S = \{\mathbf{v_1}, \mathbf{v_2}, \dots, \mathbf{v_n}\}$ be a set of vectors.
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item If we can find scalars $\alpha_1 + \alpha_2 + \dots + \alpha_n$ not all zero such that
\begin{center}$\alpha_1\mathbf{v_1} + \alpha_2\mathbf{v_2} + \dots + \alpha_n\mathbf{v_n} = 0$\end{center}
then we call $S$ a linearly dependent set and that the vectors in $S$ are linearly dependent.

\item If the only solution of
\begin{center}$\alpha_1\mathbf{v_1} + \alpha_2\mathbf{v_2} + \dots + \alpha_n\mathbf{v_n} = 0$\end{center}
is $\alpha_1 = \alpha_2 = \dots = \alpha_n = 0$ then $S$ is called a linearly independent set and that the vectors in $S$ are linearly independent.
\end{enumerate}

\subsection*{Basis}
A set $B$ of vectors in a vectorspace $V$ is called a basis if
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item $B$ is linearly independent, and
\item $V = \mbox{span}(B)$.
\end{enumerate}

An orthonormal basis is formed where all the basis vectors are unit length and are mutually orthogonal (the dot product of any two is zero).

\subsection*{Dimension}
The dimension of a vectorspace $V$, written dim($V$) is the number of basis vectors.

\section*{Linear Transformations}
\subsection*{Linear Map}
A function $T$ which maps from a vectorspace $V$ to a vectorspace $W$ is said to be linear if, for all vectors $\mathbf{u}, \mathbf{v} \in V$ and for any scalar $\lambda$,
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$,
\item $T(\lambda\mathbf{u}) = \lambda T(\mathbf{u})$.
\end{enumerate}

The columns of the transformation matrix are simply the images of the standard basis vectors.

\subsection*{The Kernel}
$\mbox{im}(T) = \mbox{col}(A)$\\
The kernel of a linear map $T : V \to W$, written ker($T$), consists of the set of vectors $\mathbf{v} \in V$ such that $T(\mathbf{v}) = \mathbf{0}$.\\
If A is the matrix representation of a linear map $T$, then the kernel of $A$ is the solution set of $A\mathbf{x} = \mathbf{0}$.

\subsection*{Rank-Nullity}
The dimension of the image of a linear map $T$ is called the rank of $T$, written rank($T$). (Maximum number of linearly independent columns of A)\\

The dimension of the kernel of a linear map $T$ is called the nullity of $T$, written nullity($T$). (Number of parameters in the solution set of $A\mathbf{x}=\mathbf{0}$)\\

If $T$ is a linear map from $V$ to $W$ then
$$\mbox{rank}(T) + \mbox{nullity}(T) = \mbox{dim}(V)$$

\section*{Eigenvectors and Eigenvalues}
If $A$ is a square matrix, $\mathbf{v} \ne 0$ and $\lambda$ is a scalar such that,
$$A\mathbf{v} = \lambda\mathbf{v}$$
then $\mathbf{v}$ is an eigenvector of $A$ with eigenvalue $\lambda$.\\
\begin{comment}
\begin{equation*}
A\mathbf{v} = \lambda\mathbf{v}
\implies (A-\lambda I)\mathbf{v} = \mathbf{0}

A-\lambda I \mbox{has no inverse (otherwise } \mathbf{v} = \mathbf{0} \mbox{)}
\mbox{so set det}(A-\lambda I) = 0
 \mbox{this finds the eigenvectors}

\mbox{Also since}
(A-\lambda I)\mathbf{v} = \mathbf{0}
\mathbf{v} \in \mbox{ker}(A-\lambda I)
\mbox{this gives eigenvectors.}
\end{equation*}
\end{comment}
Eigenvalues: Set $\mbox{det}(A-\lambda I) = 0$ and solve for $\lambda.$\\
Eigenvectors: For each value of $\lambda$ find the kernel of $(A-\lambda I)$.

\subsection*{Diagonalisation}
If $A$ has $n$ (independent) eigenvectors then put,\\
$P = (\mathbf{v_1}|\mathbf{v_2}|...|\mathbf{v_n})$ (eigenvectors $\mathbf{v}$)\\
and\\
$D =
\begin{pmatrix}
  \lambda_1 &        & 0         \\
            & \ddots &           \\
  0         &        & \lambda_n
\end{pmatrix}
$ (eigenvalues $\lambda$)\\
\\
so then\\
$A^k = PD^kP^{-1}$, for each non-negative integer $k$.\\
\\
Remember that when $A =
\bigl( \begin{smallmatrix}
  a&b\\ c&d
\end{smallmatrix} \bigr)$, $A^{-1} = \frac{1}{det(A)}
\begin{pmatrix}
d & -b\\
-c & a\end{pmatrix}$

\subsection*{Systems of Differential Equations}
The system
$\begin{cases}
	\frac{dx}{dt} = 4x + y\\
	\frac{dy}{dt} = x + 4y
\end{cases}$
 can be written $\mathbf{x}'(t) = \begin{pmatrix} 4 & 1\\1 & 4\end{pmatrix}\mathbf{x}(t)$ where $\mathbf{x}(t) = \binom{x(t)}{y(t)}.$

We can guess the solution to be $\mathbf{x}(t) = \alpha \mathbf{v} e^{\lambda t}$ (and add for all the eigenvalues). Where $\mathbf{v} $ and $ \lambda$ are the eigenvectors and eigenvalues respectively.

\section*{Probability and Statistics}

\subsection*{Probability}
Two events $A$ and $B$ are mutually exclusive if $A \cap B = \emptyset$.
$$P(A^c) = 1 - P(A)$$
$$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

\subsection*{Independence}
Two events $A$ and $B$ are physically independent of each other if the probability that one of them occurs is not influenced by the occurrence or non occurrence of the other. These two events are statistically independent if, $$P(A \cap B) = P(A).P(B).$$

\subsection*{Conditional Probability}
Probability of $A$ given $B$ is given by,
$$P(A|B) = \frac{P(A \cap B)}{P(B)}$$

\subsection*{Bayes Rule}

\subsection*{Discrete Random Variables}
$$p_k = P(X=k) \qquad \mbox{(} \{p_k\}\mbox{ is the probability distribution)}$$
where, $X$ is a discrete random variable, and $P(X=k)$ is the probability that $X=k$.\\

For $\{p_k\}$ to be a probability distribution,
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item $p_k \ge 0$ for $k = 0, 1, 2, \dots$
\item $p_0 + p_1 + \dots = 1$
\end{enumerate}

\subsection*{Mean and Variance}
$E(X)$ denotes the mean or expected value of X.\\
%$$E(X) = \sum_{i=1}^{k} p_i x_i \qquad  $$
$$E(X) = \sum_{\mbox{all }k} kp_k$$

$$\mbox{Var}(X) = E(X^2) - E(X)^2 \qquad \mbox{where } E(X^2) = \sum_{\mbox{all } k} k^2 p_k$$

\subsection*{Binomial Distribution}
If we perform a binomial experiment (i.e. 2 outcomes) $n$ times, and each time there is a probability $p$ of success then,
$$P(X=k) = \binom{n}{k} p^k (1-p)^{n-k},\qquad \mbox{for } 0\le k \le n \mbox{ and 0 otherwise}.$$

\subsection*{Geometric Distribution}
$$P(X=k) = p(1-p)^{k-1}, \;\; k = 1, 2, \dots$$
\end{document}

MATH1231-CACL LaTeX Source

%This work is hereby released into the Public Domain. To view a copy of the public domain dedication, visit http://creativecommons.org/licenses/publicdomain/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

\documentclass[a4paper,10pt]{article}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\setlength\parindent{0mm}
\usepackage{fullpage}
\usepackage[all]{xy}

\usepackage[pdftex,
pdfauthor={Andrew Harvey},
pdftitle={MATH1231 Calculus Cheat sheet 2008},
pdfsubject={},
pdfkeywords={},
pdfstartview=FitB]{hyperref}

\begin{document}
\section*{Functions of Several Variables}
\subsection*{Sketching}
\begin{itemize}
\item Level Curves
\item Sections
\end{itemize}

\subsection*{Partial Derivatives}
$$\frac{\partial^2 f}{\partial y \partial x} = \frac{\partial^2 f}{\partial x \partial y}$$
on every open set on which $f$ and the partials,\\
$$\frac{\partial f}{x}, \frac{\partial f}{y}, \frac{\partial^2 f}{\partial y \partial x}, \frac{\partial^2 f}{\partial x \partial y}$$
are continuous.

\subsection*{Normal Vector}
$$\mathbf{n} = \pm
\begin{pmatrix}
\frac{\partial f(x_0, y_0)}{\partial x}\\
\frac{\partial f(x_0, y_0)}{\partial y}\\
-1\\
\end{pmatrix}
$$

\subsection*{Error Estimation}
$$f(x_0 + \Delta x, y_0 + \Delta y) \approx f(x_0, y_0) + \left[ \frac{\partial f}{\partial x} (x_0, y_0)\right] \Delta x + \left[ \frac{\partial f}{\partial y} (x_0, y_0)\right] \Delta y$$

\subsection*{Chain Rules}
Example, $z = f(x,y)\ \mbox{with}\ x = x(t), y = y(t)$
\begin{displaymath}
\xymatrix{
& f \ar[dl] \ar[dr] &   \\
x \ar[d] &                   & y \ar[d]\\
t        &                   & t}
\end{displaymath}

$$\frac{df}{dt} = \frac{\partial f}{\partial x} \cdot \frac{dx}{dt} + \frac{\partial f}{\partial y} \cdot \frac{dy}{dt}$$

\section*{Integration}
\subsection*{Integration by Parts}
Integrate the chain rule,
$$u(x)v(x) = \int u'(x)v(x)\; dx + \int v'(x)u(x)\; dx$$

\subsection*{Integration of Trig Functions}
For $\int \sin^2 x\; dx$ and $\int \cos^2 x\; dx$ remember that,\\
$$\cos 2x = \cos^2 x - \sin^2 x$$
%$$\sin 2x = 2\sin x \cos x$$

Integrals of the form $\int \cos^m x \sin^n x\; dx$, when $m$ or $n$ are odd, you can factorise using $\cos^2 x + \sin^x = 1$  and then using,
$$\int \sin^k x \cos x\; dx = \frac{1}{k+1} \sin^{k+1} x + C$$
$$\int \cos^k x \sin x\; dx = \frac{-1}{k+1} \cos^{k+1} x + C$$

\subsection*{Reduction Formulae}
...

\subsection*{Partial Fractions}
Example, assume
$$\frac{2x-1}{(x+3)(x+2)^2} = \frac{A}{x+3} + \frac{Bx + C}{(x+2)^2}$$
\begin{comment}
\begin{enumerate}
\renewcommand{\labelenumi}{\roman{enumi})}
\item $\frac{2x-1}{x+2} = A + \frac{B(x+3)}{x+2}$ subs $x=-3 \to A=7$
\item $\frac{2x-1}{x+3} = \frac{A(x+2)}{x+3} + B$ subs $x=-2 \to B=-5$
\end{enumerate}
\end{comment}
Now multiply both sides by $(x+2)(x+3)$ and equate coefficients.

\section*{ODE's}
\subsection*{Separable ODE}
Separate then integrate.

\subsection*{Linear ODE}
The ODE:
$$ \frac{dy}{dx} + f(x)y=g(x) $$
has solution,
$$ y(x) = \frac{1}{u(x)}\left [ \int u(x)g(x)\ dx + C \right] $$
where,
$$ u(x) := e^{\int f(x)\ dx} $$

\subsection*{Exact ODE}
The ODE:
$$ \frac{dy}{dx} = -\frac{M(x,y)}{N(x,y)} $$
or as,
$$ M(x,y)dx + N(x,y)dy = 0 $$
is exact when,
$$ \frac{\partial M}{\partial y} = \frac{\partial N}{\partial x} $$

Assume solution is of the form,
$$ F(x,y) = c $$
with,
$$ M = \frac{\partial F}{\partial x} \qquad N = \frac{\partial F}{\partial y}$$

Integrate to find two equations equal to $F(x,y)$, then compare and find solution from assumed form.

\subsection*{Second Order ODE's}
The ODE:
$$ay'' + ay' + by = f(x)$$
For the homogeneous case ($f(x) = 0$)\\
the characteristic equation will be $a\lambda^2 + b\lambda + c = 0$

If the characteristic equation has,\\
Two Distinct Real roots, (replace the $\lambda$'s with the solutions to the characteristic eqn.)
$$ y = Ae^{\lambda x} + Be^{\lambda x}$$

Repeated Real roots,
$$ y = Ae^{\lambda x} + Bxe^{\lambda x}$$

Complex roots,
$$ y = e^{\alpha x}(A\cos \beta x + B\sin \beta x)$$

where,
$$\lambda = \alpha \pm \beta i$$

For the For the homogeneous case,
$$y = y_h + y_p$$
$$y = \mbox{solution to homogeneous case} + \mbox{particular solution}$$

Guess something that is in the same form as the RHS.\\
If $f(x) = P(x)\cos ax \mbox{(or sin)}$ a guess for $y_p$ is $Q_1(x)\cos ax + Q_2(x)\sin ax$

\section*{Taylor Series}
\subsection*{Taylor Polynomials}
For a differentiable function $f$ the Taylor polynomial of order $n$ at $x=a$ is,
$$P_n(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \dots + \frac{f^{\left( n\right) }(a)}{n!}(x-a)^n$$

\subsection*{Taylor's Theorem}
$$f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \dots + \frac{f^{\left( n\right) }(a)}{n!}(x-a)^n + R_n(x)$$

where,\\
$$R_n(x) = \frac{f^{\left( n+1\right) }(c)}{(n+1)!}(x-a)^{n+1}$$

\subsection*{Sequences}
$$\lim_{x \to \infty} f(x) = L \implies \lim_{n \to \infty}a_n = L$$
essentially says that when evaluating limits functions and sequences are identical.

A sequence diverges when $\displaystyle \lim_{n \to \infty}a_n = \pm \infty$ or $\displaystyle \lim_{n \to \infty}a_n$ does not exist.

\subsection*{Infinite Series}
\subsubsection*{Telscoping Series}
Most of the terms cancel out.

\subsubsection*{$n$-th term test (shows divergence)}
$\displaystyle \sum_{n=1}^{\infty} a_n$ diverges if $\displaystyle \lim_{n \to \infty}{a_n}$ fails to exist or is non-zero.

\subsubsection*{Integral Test}
Draw a picture. Use when you can easily find the integral.

\subsubsection*{$p$- series}
The infinite series $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^p}$ converges if $p>1$ and diverges otherwise.

\subsubsection*{Comparison Test}
Compare to a p-series.

\subsubsection*{Limit form of Comparison Test}
Look at $\displaystyle \lim_{n \to \infty}{\frac{a_n}{b_n}}\;$ where $b_n$ is usually a p-series.\\
If $=c>0$, then $\sum a_n$ and $\sum b_n$ both converge or both diverge.\\
If $=0$ and $\sum b_n$ converges, then $\sum a_n$ converges.\\
If $=\infty$ and $\sum b_n$ diverges, then $\sum a_n$ diverges.

\subsubsection*{Ratio Test}
$$\lim_{n \to \infty} \frac{a_{n+1}}{a_n} = \rho$$

The series converges if $\rho < 1$,\\
the series diverges if $\rho > 1$ or $\rho$ is infinite,\\
and the test is inconclusive if $\rho = 1$.

\subsubsection*{Alternating Series Test}
The series,
$$\sum_{n=1}^{\infty} (-1)^{n+1} u_n = u_1 - u_2 + u_3 - u_4 + \dots$$
converges if,
\begin{enumerate}
\item The $u_n$'s are all $>0$,
\item $u_n \ge u_{n+1}$ for all $n \ge N$ for some integer $N$, and
\item $u_n \rightarrow 0$.
\end{enumerate}

\subsubsection*{Absolute Convergence}
If $\displaystyle \sum_{n=1}^{\infty} |a_n|$ converges, then $\displaystyle \sum_{n=1}^{\infty} a_n$ converges.

\subsection*{Taylor Series}
Taylor Polynomials consist of adding a finite number of things together, whereas Taylor Series is an infinite sum.\\
The Maclaurin series is the Taylor series at $x=0$.
\subsection*{Power Series}

\section*{More Calculus}
\subsection*{Average Value of a Function}
$$\frac{\displaystyle \int_a^b f(x)\ dx}{b-a}$$

\subsection*{Arc Length}
\begin{center}
Arc length over $\displaystyle[a,b] = \int_a^b \sqrt{1+f'(x)^2}\ dx$\\
\end{center}
$$s = \int_a^b \sqrt{x'(t)^2 + y'(t)^2}\ dt \qquad \mbox{(parametric)}$$

\subsection*{Speed}
$$\frac{ds}{dt} = \sqrt{x'(t)^2 + y'(t)^2}$$

\subsection*{Surface Area of Revolution}
$$2\pi \int_a^b f(x) \sqrt{1+f'(x)^2}\ dx$$
$$2\pi \int_a^b y(t) \sqrt{x'(t)^2 + y'(t)^2}\ dt \qquad \mbox{(parametric)}$$
\end{document}
Advertisements
Categories: mathematics, unswcourse Tags: ,

An Introduction to Hypercubes.

October 21, 2008 1 comment

Point, Line Segment, Square, Cube. But what comes next, what is the equivalent object in higher dimensions? Well it is called a hypercube or n-cube, although the 4-cube has the special name tesseract.

Construction Methods

Before I go on to explain about the elements of hypercubes, let me show you some pictures of some hypercubes. I guess this also raises the question how can you construct these objects. One method is to start with a point. Then stretch it out in one dimension to get a line segment. Then take this line and stretch it out in another dimension perpendicular to the previous one, to get a square. Then take that square and stretch it out in another dimension perpendicular to the previous two to get a cube. This is when your visualisation may hit a wall. Its very hard to then visualise taking this cube and stretching it in another dimension perpendicular to the previous three. However mathematically, this is easy and this is one approach to constructing hypercubes.

We place a point in R3.

We place a point in R3.

...and then stretch the point in one dimension to make a line...

...and then stretch the point in one dimension to make a line...

...and then we stretch that line in a direction perpendicular to the previous time...

...and then we stretch that line in a direction perpendicular to the previous time...

...and finally stretch that plane in a direction perpendicular the the previous two times.

...and finally stretch that plane in a direction perpendicular the the previous two times.

However there is more mathematical and analytical method. You most probably know that these n-cubes have certain elements to them, namely vertices (points), edges (lines), faces (planes), and then in the next dimension up, cells and then in general n-faces. These elements are summed up nicely here. Firstly we take a field of say \mathbb{R}^n. Next we construct the vertices of the n-cube. Basically we are taking all the n dimensional vectors which have all the combinations of 0’s and 1’s for each entry of the vector. More mathematically,
There is a vertex described by each vector \begin{pmatrix}a_1\\ a_2\\ \vdots\\ a_n\end{pmatrix} where a_i \in \{0, 1\}.
There is an edge between vertices \begin{pmatrix}a_1\\ a_2\\ \vdots\\ a_n\end{pmatrix} and \begin{pmatrix}b_1\\ b_2\\ \vdots\\ b_n\end{pmatrix} if and only if a_j \ne b_j for exactly one j \in \{1, \dots, n\}.
\qquad \qquad \vdots
There is an m-face between (or though) vertices \begin{pmatrix}a_1\\ a_2\\ \vdots\\ a_n\end{pmatrix} and \begin{pmatrix}b_1\\ b_2\\ \vdots\\ b_n\end{pmatrix} and … and \begin{pmatrix}m_1\\ m_2\\ \vdots\\ m_n\end{pmatrix} if and only if a_j \ne b_j \ne \dots \ne m_j for exactly (m - 1), \;\; j \in \{1, \dots, n\}.

Basically this means we list the vertices just as if were were counting in base 2. And then we can group these vertices into different groups based on the n-face level and (if we think of the vertices of a bit string) how many bits we have to change to make two vertices bit streams the same. This approach is very interesting because the concept of grouping these vertices relates strongly to hypergraphs.

Another way to think about it is as follows. Edges, from the set of all edges (i.e. joining each vertex with every other vertex), are the ones that are perpendicular to one of the standard basis vectors. This generalises to n-faces; from the set of all n-faces (i.e. all ways of grouping vertices into groups of n) are those that the object constructed is parallel to the span of any set of n of the standard basis vectors.

When you think about it, a lot of things that you can say about the square or cube generalise. For instance you can think of a square being surrounded by 4 lines, and cube by 6 surfaces, a tesseract by 8 cells, etc.

Visualisation Methods

Now that we have some idea how to describe and build n-cubes, the next question is how do we draw them. There are numerous methods and I can’t explain them all in this post (such as slicing and stereographic projection, as well as other forms of projection (I’ll leave these for another blog article)). But another question is also what aspects do we draw and how do we highlight them. For instance it may seem trivial in two dimensions to ask do I place a dot at each vertex and use just 4 solid lines for the edges. But in higher dimensions we have to think about how do we show the different cells and n-faces.

Firstly, how can we draw or project these n dimensional objects in a lower dimensional world (ultimately we want to see them in 2D or 3D as this is the only space we can draw in). This first method is basically the exact same approach that most people would have first learnt back in primary school. Although, I do not think it makes the most sense or makes visualisation easiest. Basically this method is just the take a dot and perform a series of stretches on it that I described earlier, although most people wouldn’t think this is what they were doing. Nor would we usually start with a dot, we would normally start with the square. Although we will, so we start with this.

0-cube, showing verticies.

0-cube.

We would now draw a line along some axis from that dot, and place another dot at the end of this line.

1-cube, showing verticies and edges.

1-cube, showing vertices and edges.

Now from each of the dots we have, we would draw another line along some other axis and again draw a dot at the end of each of those two lines. We would then connect the newly formed dots.

2-cube, showing verticies and edges.

2-cube, showing vertices and edges.

Now, we just keep repeating this process where by each time we are drawing another dimension. So we take each of these four dots and draw lines from them in the direction of another axis, placing a dot at the end of each of these lines, and joining each of the dots that came from other dots that were adjacent, with a line.

3-cube, showing vertices and edges.

Now for 4D and beyond we basically keep the process going, just choosing really anywhere from the new axis, so long as it passes though the origin.

4-cube, showing verticies and edges.

4-cube, showing vertices and edges.

If we do a little bit of work we can see that this map is given by the matrix,

\begin{pmatrix}1&0&r_1\cos \theta&-r_2\cos\phi\\ 0&1&r_1\sin\theta&r_2\sin\phi \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix}

where \theta is the angle of the projected z axis from the x axis, and \phi is the angle of the projected w axis from the negative x axis. Also r1 and r2 are the scales of the third and fourth respective receding axis (it makes it “look” more realistic when we use a number less than 1) This is just an extension of oblique projection for 3D to 2D.

Now this method seems very primitive, and a much better approach is to use all the dimensions we have. We live in a three dimensional world, so why just constrict our drawings to two dimensions! Basically, an alternate approach to draw an n-cube in three dimensional space would be to draw n lines all passing though a single point. Although it is not necessary to make all these lines as spread out as possible, we will try to. (This actually presents another interesting idea of how do we equally distribute n points on a sphere. For instance we can try to make it so that all the angles between any two of the points and the origin are equal. But I will leave this for another blog article later.) We then treat each of these lines as one dimension from there we can easily draw, or at least represent an n-dimensional point in 3D space. Now obviously we can have two different points in 4D that map to the same 3D point, but that is always going to happen no matter what map we use. The following set of 4 vectors are the projected axis we will use as a basis.

\left \{ \mathbf{e_1}, \mathbf{e_2}, \mathbf{e_3}, \mathbf{e_4} \right \} = \left \{ \begin{pmatrix}1\\1\\1 \end{pmatrix}, \begin{pmatrix}-1\\-1\\1 \end{pmatrix}, \begin{pmatrix}-1\\1\\-1 \end{pmatrix}, \begin{pmatrix}1\\-1\\-1 \end{pmatrix} \right \}

Now I won’t say how I got these (actually I took them from Wikipedia, they are just the vertices of a 3-simplex) but all of the vectors share a common angle between any two and the origin.

Now if we draw in our tesseract, highlighting the cells with different colours (not this became problematic with some faces and edges as they are a common boundary for two different faces, so you cannot really make them one colour or the other) we get something like this,

Tesseract projected onto R3. The cells are shown in different colours, the purple lines show the four axis.

Tesseract projected onto R3. The cells are shown in different colours, the purple lines show the four axis.

The projection matrix for this projection is then simply (from the vectors that each of the standard basis maps to),

\begin{pmatrix}1&-1&-1&1\\ 1&-1&1&-1\\ 1&1&-1&-1 \end{pmatrix}

Now if we compare this to our original drawing (note I’m not talking about the projection used, but rather the presentation of the drawings, i.e. the colour.) I think you will see that the second one is clearer and try’s to show where the cells and faces are, not just the vertices and edges. Note also the second one is in 3D so you can rotate around it. Looking at the first one though, you will notice it doesn’t show where the faces or cells are. Remember that we have more than just vertices, edges and faces. We have cells, and n-faces. These are essentially just different groupings of the vertices. But how can we show these. Now the most mathematical way would be to just list all the different groupings. This is okay, but I like to see things in a visual sense. So another way would just show different elements. Like you draw all the vertices on one overhead, edges on another, and so on. Then when you put all these overheads on top of each other we get the full image, but we can also look at just one at a time to see things more clearly. This would be particularly more useful for the higher dimensional objects and higher dimensional elements. We can also use different colours to show the different elements. For example in the square, we can see that the line around surrounding it is 4 lines, but in higher dimensions its not so easy, so we can colour the different parts to the element differently. (When I say part I mean the 4 edges of a square are 4 different parts. Whereas the edges are all one element, but are a different element to the vertices.)

Some Interesting Properties

Once you start defining hypercubes there are many interesting properties that we can investigate. For this section lets just assume that we have the standard hypercube of side length 1. Now we can trivially see that the area, volume, etc. for the respective hypercube will always be 1. As described above each time we add another dimension and sweep the object out into that dimension we effectively multiply this hypervolume by 1. So for an n-cube, the hypervolume of it will be 1^n. When I say hypervolume I mean the one that makes sense for that dimension. E.g. in 2D, area, in 3D, volume, and so on.

The next obvious question to ask is what is the perimeter, surface area, cell volume, …, n-face hypervolume of the respective n-cube? It gets a little confusing as you have to think about what exactly you are finding. Is it a length, an area, a volume? Well it will just be an (n – 1) volume. Eg. in 2D we are finding a length (the perimeter), in 3D, an area (surface area), and so on so that each time we increase the dimension of the n-cube we increase the units we are measuring in. Well if we just start listing the sequence (starting with a square), 4, 6… we notice this is just the number of (n – 1) degree elements. Namely, the number of edge, faces, cells, etc.

This leads me in the obvious question of how can I calculate the number of m-elements of the n-cube?

Well instead of me just going to the formula, which you can find on Wikipedia anyway, I will go though my lines of thinking when I first tried to work this out. Number of vertices is easy, each component of the n-vector can be either a 0 or a 1. So for each component there is 2 possibilities, but we have n of them, so it is just 2x2x2… n times, or 2n. Now originally when I tried to work out the number of edges, I started listing them and saw that I could construct the recurrence… Although with the help of graph theory it is very simple. In graph theory the handshaking theorem says \displaystyle 2\left |E \right| = \sum_{v \in V} \mbox{deg}(v). Where \left | E \right | means the number of edges, and \mbox{deg}(V) means the degree of vertex V, which means the number of edges connected two it. Now if we think of an edge being a group of two vertices where you only make one entry of the vector change to get from one vector to the other, then we can see that there are exactly n way of doing this. We can either change the 1st entry of the vector, or the 2nd, or the …., or the nth. Thus each vertex has of the n-cube graph will have degree n. So as we have 2n vertices and each vertex has degree n, then the sum of the vertex degrees will be n2n. Hence by the handshaking theorem, |E| = \frac{1}{2} n 2^n = n 2^{n-1}. I am not exactly sure how to generalise this further. I will leave it for another article. However, the formula is 2^{n-m} \binom{n}{m}.

(I shall try to write more at a later date.)

References:

Proof

August 30, 2008 Leave a comment

Many of the courses I have studied so far (such as HSC Mathematics and 1st year MATH1131 and MATH1231 [UNSW]) require some form of mathematical proofs to be used. However in these courses they don’t really teach us about proof’s, rather they tend to say here is the generic proof to use, memorise it and write it out in the exam. They don’t always do this, but most of the time they have asked us to do a proof in an exam there is a similar example provided in the notes somewhere.

I have always found doing proof questions very hard and I think the main reason is that they never actually taught us them! Lucky for me I’m doing MATH1081 which has a section all about proof and I must say, I’ve learnt a lot of very important and interesting things from this course.

A lot of the time when I saw proofs I would think to myself, that is not a proof! Mainly either because it was so obvious that you can just see its true, or because the proof says its true because of such and such reason, with no explanation as to why such and such reason was also true.

However now that I’ve been taught proofs, things are starting to make sense. Proofs are actually quite simply, they are there just to convince the reader that some result is true based on some agreed upon facts. Proofs just build on things to provide new results based on those results already known. It is quite acceptable to not prove certain things in a proof because they themselves have proofs and if you were to include these proofs every time you find a new result you would have to publish a whole new book with a couple extra pages stuck on the back.

This whole idea of having proof’s based on axioms/postulates is very interesting. In Euclid’s Elements, Euclid first writes down a series of definitions so that he has something to base his postulates and theorems on. Without first accepting these basic facts nothing can be proved. Some people say that these axioms are obviously true, I tend to disagree. Rather than viewing them are true or false I think it would be more appropriate to not label them as either. They are merely axioms on which you base deductions. I also think you should not just consider things that are based on these axioms. It would of course be very interesting to investigate the mathematics if you have some very weird axioms that most would say are obviously false. Again I would say its not a matter of this fact being true and this being false, rather here is a statement and here is what you can deduce from that statement.

Back to the idea of what is considered a proof, I think my lecturer has explained it well. A proof is merely a argument, something which aims to convince the reader that the statement which you are proving is in fact true based on those agreed upon facts. You simply show how to obtain the result from simpler things which one also accepts to be true.

Another concept which came up was the use of diagrams in proofs. When we studied sets and we had a question which said prove A is a subset of B, I always thought that the easiest way to show this was to draw a Venn diagram and show that A is always inside B. Then again you could always argue that you are just drawing a diagram of the result you are trying to prove!

From an education perspective, I think the very lack of teaching mathematical proof all the way up until math1081 and yet expecting us to understand proofs is completely stupid. If we ever want to have a deeper understanding of the things we learn and know why they work, then we should be taught the fundamentals first!

Now, I’m sure I’ve said some things which are probably not entirely correct. I accept that, I’m not an expert in maths, so don’t expect me to.

Update (18th Oct 2008):
I just read this in a maths text book,

If x+3=5,
then (x+3) + (-3) = 5 + (-3);
hence x + (3 + (-3)) = 5 - 3 = 2;
hence x + 0 = 2;
hence x = 2.

They go on to say,

“Naturally, such elaborate solutions are of interest only until you become convinced that they can always be supplied. In practice, it is usually just a waste of time to solve and equation by indicating so explicitly the reliance on (the laws of elementary algebra).”[1]

I think this is the best example of what my troubles were in understanding the whole concept of proof. I guess the largest challenge that I face now is in examinations how do I know what level of maths I can assume the examiner agrees upon, and how much I actually have to prove.

References:
[1] Spivak, M. (1973). Calculus. Addison-Wesley. pp 4-5.