Mathematics for Signal Processing $a^2 +b^2 = c^2$¶

General Topics¶

Logic and Sets¶

Logic¶

Let $A$ and $B$ be statements.

The negation of $A$ is the statement (not $A$).

The both of $A$ and $B$ is the statement ($A$ and $B$).

The either of $A$ and $B$ is the statement ($A$ or $B$).
The statement ($A$ or $B$) does not contradict ($A$ and $B$).
Every statement is is assumed to be either true or false.
No statement can be both true and false.
The statements “$A$ and $B$ or $C$” and “$A$ or $B$ and $C$” are ambiguous.
We therefore write “$A$ and either $B$ or $C$” and “either $A$ or both $B$ and $C$”.

Implication¶

Let $A$ and $B$ be statements.

The implication statement “if $A$ is satisfied, then $B$ is satisfied” or, equivalently, “$A$ implies $B$” is written as $A \Rightarrow B$.
$A \Leftrightarrow B$ is equivalent to $[(A \Rightarrow B) \text{ and } (A \Leftarrow B)]$
$A \Leftarrow B$ means $B \Rightarrow A$.

Tautology¶

A tautology is a statement which is true regardless of whether the component statements are true or false.
E.g. the statement “($A$ and $B$) implies $A$)” is a tautology.

Contradiction¶

A contradiction is a statement that is false regardless of whether the component statements are true or false.

Implication contd.¶

Suppose that $A \Leftrightarrow B$.

Then, $A$ is satisfied if and only if $B$ is satisfied.

The implication $A \Rightarrow B$ (the “only if” part) is necessity.

$B \Rightarrow A$ (the “if” part) is sufficiency.

The converse statement of $A \Rightarrow B$ is $B \Rightarrow A$.

The statement $A \Rightarrow B$ is equivalent to its contrapositive statement $(\text{not } B) \Rightarrow (\text{not } A)$.

Statements¶

A theorem is a significant statement.

A proposition is a theorem of less significance.

The primary role of a lemma is to support the proof of a theorem or proposition.

A corollary is a consequence of a theorem or proposition.

A fact is either a theorem or a proposition or a lemma or a corollary.
Theorems, propositions, lemmas, corollaries, and facts are provably true statements.
Suppose that $A' \Rightarrow A \Rightarrow B \Rightarrow B'$.
Then, $A' \Rightarrow B'$ is a corollary of $A \Rightarrow B$.

Let $A$, $B$, and $C$ be statements, and assume that $A \Rightarrow B$.
Then, $A \Rightarrow B$ is a strengthening of the statement $(A \text{ and } C) \Rightarrow B$.

If in addition $A \Rightarrow C$, then the statement $(A \text{ and } C) \Rightarrow B$ has a redundant assumption.

Sets¶

A set is a collection of elements.

Let $\mathcal{X} \triangleq = \{x,y,z\}$ be a set. Then

\[x \in \mathcal{X}\]

means that $x$ is an element of $\mathcal{X}$.
If $w$ is not an element of $\mathcal{X}$, then we write:

\[w \notin \mathcal{X}\]

The set with no elements, denoted by $\phi$, is the empty set.

If $\mathcal{X} \neq \phi$, then $\mathcal{X}$ is nonempty.

Cardinality¶

A set cannot have repeated elements. e.g. $\{x,x\} = \{x\}$.

A multiset is a collection of elements that allows for repetition.
The multiset consisting of two copies of $x$ is written as ${x,x}_{ms}$.
We do not assume that the listed elements $x,y$ of the conventional set $\{x,y\}$ are distinct.

The number of distinct elements of the set $\mathcal{S}$ or not-necessarily-distinct elements of the multiset $\mathcal{S}$ is the cardinality of $\mathcal{S}$, which is denoted by $\text{card}(\mathcal{S})$ or $\left|\mathcal{S}\right|$.

Statements¶

There are two basic types of mathematical statements involving quantifiers.

An existential statement is of the form:

there exists $x \in \mathcal{X}$ such that statement $Z$ is satisfied.

A universal statement has the structure

for all $x \in \mathcal{X}$, it follows that statement $Z$ is satisfied.

or equivalently

statement $Z$ is satisfied $\forall x \in \mathcal{X}$.

Operations¶

Let $\mathcal{X}$ and $\mathcal{Y}$ be sets.

The intersection of $\mathcal{X}$ and $\mathcal{Y}$ is the set of common elements of $\mathcal{X}$ and $\mathcal{Y}$ given by

\[\mathcal{X} \cap \mathcal{Y} \triangleq \{x : x \in \mathcal{X} \wedge x \in \mathcal{Y} \} = \{x : x \in \mathcal{Y} \wedge x \in \mathcal{X} \} = \mathcal{Y} \cap \mathcal{X}\]

Levels of measurement¶

a.k.a. Scales of measure
Developed by Stanley Smith Stevens

Measurements in science use following scales

Nominal scale
Ordinal scale
Interval scale
Ratio scale

Examples of different scale types

Scale type	Example
Nominal	Rocks as igneous, sedimentary, metamorphic; first names
Ordinal	Rank-ordering data: Result of horse race, Mohs scale of mineral hardness
Interval	temperature with the Celsius scale,
Ratio	Mass, length, time, plane angle, energy and electric charge

Mathematical features of different scale types

Scale type	Permissible statistics	Admissible scale transformation	Mathematical structure
Nominal	Mode,Chi-squared	One-to-one (equality)	Standard set (unordered)
Ordinal	Median,percentile	Monotonically increasing (order <)	Totally ordered set
Interval	Mean,std,correlation,regression	Positive linear (affine)	Affine line
Ratio	All above+geometric mean,log etc	Positive similarities	1-D vector space

We can notice, that understanding of scale is important in appropriate choice of statistical measures for data analysis.

Nominal scale¶

Nominal measures offer names or labels for certain characteristics
Objects are classified using labels
- Rocks as igneous, sedimentary, metamorphic
- A group of people classified based on their first name
Valid operations
- Equivalence
- Set memberships

Categorical variables¶

Variables assessed on a nominal scale are called categorical variables.
Binary variables (or Bernoulli variables) : only two possible categories
- Yes or no
- success or failure
Multi-way variables

Categorical distribution¶

A categorical distribution is a probability distribution that describes the result of a random event that can take one of K possible outcomes, with the probability of each outcome separately specified.

There is not necessarily an underlying ordering of these outcomes.
Numerical labels are attached for convenience.

Statistics¶

Central tendency is given by its mode [e.g. most common name]
Mean is not defined [what would be average name in a set of people?]
Median is not defined [There is no ordering in the labels]

Ordinal scale¶

Rank ordering data puts the data on ordinal scale
Order of measurements is described.
Relative size or degree of difference between measured items is not described.

Examples

Result of a horse race, where the horses are ordered based on which one arrived 1st, second, or third, etc..
Names arranged in alphabetical order
- We can say which name comes first which later in this order.
- But there is no meaning of difference between names.
Psychometric measurements [like IQ etc.]
Food quality : exceptional, great, good, average, bad, poor

Statistics¶

Central tendency specified using mean or median
Mean cannot be defined

Order isomorphism¶

An ordinal scale defines a total preorder of objects
Scale values may be sorted on a single line with no ambiguities
Numbers may be assigned to scale values
Any transformation of numbers using a monotonically increasing function doesn’t change the order, hence retains validity.
This is known as order isomorphism.

Interval scale¶

Quantitative attributes are measurable on interval scale
Difference between levels is meaningful.
Difference can be multiplied to exceed or equal another difference.
Ratio between numbers of this scale is not meaningful
Multiplication and division cannot be done directly.
Ratio between differences is meaningful.
Choice or origin is arbitrary and not meaningful. [e.g. 0 degree Celsius]

Statistics¶

Central tendency can be represented by mode, median, mean all.
Statistical dispersion can be measured using, standard deviation, quantiles etc.
Studentized range or coefficient of variation is not supported.
Moments are not useful since origin is arbitrary. Central moments make sense.

Ratio scale¶

Measurement is the estimation of ratio between magnitude of a continuous quantity and a unit magnitude of same kind.
A zero value is supported.

Examples

Mass, length, time, plane angle, energy and electric charge
Kelvin temperature

Statistics¶

Since all mathematical operations are supported, hence all statistical measures are available.
Mode, median, arithmetic mean
Geometric mean, harmonic mean
Range, standard deviation
Studentized range, coefficient of variation

References¶

Change log

Last Modified: $Id: measurements.rst 249 2012-08-05 06:17:57Z shailesh $

Convergence¶

Pointwise convergence¶

Suppose $\{f_n\}$ be a sequence of functions sharing the same domain $X$ and codomain $Y$.

The sequence $\{f_n\}$ converges pointwise to $f$, written as:

\[\lim_{n \to \infty} f_n = f\]

if and only if

\[\lim_{n \to \infty} f_n(x) = f(x) \quad \forall x \in X\]

Uniform convergence¶

A sequence $\{f_n\}$ converges uniformly to $f$, if the speed of convergence of $\{f_n(x)\}$ to $f(x)$ doesn’t depend upon $x$.

Consider the sequence $a_n = \sup_x|f_n(x) - f(x)|$ where the supremum is taken over all $x \in X$. $\{f_n\}$ converges uniformly to $f$ if and only if $a_n \to 0$.

Uniform convergence is stronger than pointwise convergence.
Every uniformly convergent sequence is pointwise convergent.

Almost everywhere convergence¶

In measure theory, the concept of almost everywhere convergence of a sequence of measurable functions defined on a measurable space is discussed. It means pointwise convergence almost everywhere (i.e. the measure of points at which convergence doesn’t happen is zero).

Absolute convergence¶

An infinite series of numbers is said to converge absolutely if the sum of absolute values of the summand is finite.

$\sum_{-\infty}^{+\infty}a_n$ is said to converge absolutely if $\sum_{-\infty}^{+\infty}|a_n| < \infty$.

This can also be defined for a one sided series $\sum_{0}^{+\infty}a_n$.

Similarly an improper integral of a function $\int_{-\infty}^{\infty} f(x)dx$ is said to converge absolutely if $\int_{-\infty}^{\infty} |f(x)|dx < \infty$; i.e. the integral of the absolute value of the integrand is finite.

Any absolutely convergent series is convergent.

Change log

Last Modified: $Id: convergence.rst 249 2012-08-05 06:17:57Z shailesh $

Algebra¶

Algebraic structures¶

Introduction¶

An algebra is a set S (called the carrier) together with zero or more operations, each of which is a function from $S^k \rightarrow S$ for some k. The value k is the number of arguments to the operation and is called “arity” of the operation. Typical operations are unary (one argument) or binary (two arguments).

0-ary operations: identity element, etc.. Also called constants
unary operations: negation
binary operations: addition, multiplication etc.

Various standard algebras are abstractions which allow us to reason about different situations at the same time. They are like base classes in an object oriented type hierarchy that provide minimum features common to all classes that inherit from them without specifying any details.

Our proofs and algorithms don’t require the detailed structure of say $\mathbb{Q}$, $\mathbb{R}$, or $\mathbb{Z}$, but in fact can work in any algebra of the appropriate type.

Typical properties of operations

Closure: $x \in S \cap y \in S \Rightarrow x + y \in S$.
Associativity: $x+(y+z) = (x+y)+z$
Identity: $0+x=x+0=x$
Inverse: $x+(-x)=(-x)+x=0$
Commutativity: $x+y=y+x$
Distributivity: $x(y+z)=xy+xz; (y+z)x = yx+zx$
Multiplicative Associativity : $(xy)z = x(yz)$
Multiplicative Identity: $1x = x1 = x$
Multiplicative Commutativity: $xy=yx$
Multiplicative Inverse : $xx^{-1}=x^{-1}x=1$

Hierarchy of algebraic structures

digraph G { graph[ overlap=false splines=true rankdir=BT ] compound=true; fontsize = 10; node [ fontsize = 10 shape = "record" color=gray fontcolor= blue ] edge [ fontsize = 8 ] subgraph{ Set [ label="{Set|no operations}" ] } subgraph cluster_one_op_one_set{ label="One set with one binary operation" node [ ] Magma[ label="{Magma|closure}" URL="http://en.wikipedia.org/wiki/Magma_(algebra)" ] Semigroup [ label="{Semigroup|associativity}" URL="http://en.wikipedia.org/wiki/Semigroup" ] Monoid [ label="{Monoid}" URL="http://en.wikipedia.org/wiki/Monoid" ] Group [ label="{Group|inverse}" URL="http://en.wikipedia.org/wiki/Group_(mathematics)" ] CommutativeGroup [ label="{Abelian Group|commutativity}" URL="http://en.wikipedia.org/wiki/Abelian_Group" ] Quasigroup [ label="{Quasigroup|inverse}" URL="http://en.wikipedia.org/wiki/Quasigroup" ] Unital [ label="{Unital|identity}" URL="http://en.wikipedia.org/wiki/Unital_algebra" ] Loop [ label="{Loop}" URL="http://en.wikipedia.org/wiki/Loop_(algebra)#Loop" ] Semicategory [ label="{Semicategory|associativity}" URL="http://en.wikipedia.org/wiki/Category_(mathematics)" ] Category [ label="{Category|identity}" URL="http://en.wikipedia.org/wiki/Category_(mathematics)" ] Groupoid [ label="{Groupoid|inverse}" URL="http://en.wikipedia.org/wiki/Groupoid" ] { rank=same; Magma;Semicategory; } Semigroup -> Magma; Quasigroup -> Magma; Unital -> Magma; Loop -> Unital; Loop -> Quasigroup; Monoid -> Semigroup; Monoid -> Unital; Group -> Monoid; Group -> Loop; CommutativeGroup -> Group; Category->Semicategory; Groupoid -> Category; Group -> Groupoid; } subgraph cluster_one_set_two_ops{ label="One set with two operations" Ring [ label="{Ring (S,+,*)|Abelian Group(+)\nMonoid(*)|distributivity}" URL="http://en.wikipedia.org/wiki/Ring_(mathematics)" ] CommutativeRing [ label="{Commutative Ring|commutative(*)}" URL="http://en.wikipedia.org/wiki/Commutative_ring" ] IntegralDomain [ label="{Integral Domain|no zero divisors}" URL="http://en.wikipedia.org/wiki/Integral_domain" ] Field [ label="{Field|S - \{0\}(Commutiative Group under *)}" URL="http://en.wikipedia.org/wiki/Field_(mathematics)" ] CommutativeRing->Ring; IntegralDomain->CommutativeRing; Field->IntegralDomain; } subgraph cluster_two_set_two_ops{ label="Two sets with two operations" VectorSpace[ label="{Vector Space\n(A over B)| Abelian Group (A)\n Field (B)}" URL="http://en.wikipedia.org/wiki/Vector_space" ] Module[ label="{Module\n(A over B)| Abelian Group (A)\n Ring (B)}" URL="http://en.wikipedia.org/wiki/Module_(mathematics)" ] RModule[ label="{R Module\n(A over B)| Abelian Group (A)\nCommutative Ring (B)}" URL="http://en.wikipedia.org/wiki/Module_(mathematics)" ] //GroupOps [ // label="{Group with operators\n(G with B))}" //] RModule->Module; VectorSpace->RModule; } subgraph cluster_two_set_three_ops{ label="Two sets with three ops" AlgebraOverRing [ label="{Algebra over ring\n(A over B)| bilinear product on A}" URL="http://en.wikipedia.org/wiki/Algebra_(ring_theory)" ] AlgebraOverField [ label="{Algebra over field\n(A over B)}" URL="http://en.wikipedia.org/wiki/Algebra_over_a_field" ] AlgebraOverField->AlgebraOverRing; AlgebraOverRing->RModule; AlgebraOverField->VectorSpace; } { edge [style = dotted, color=blue] Magma->Set; Semicategory->Set; Ring->CommutativeGroup; Ring->Monoid; Module->CommutativeGroup; VectorSpace->CommutativeGroup; //GroupOps->Group; //GroupOps->Set; } { // connections for 2nd sets edge [style=dotted, color=green] Module->Ring; RModule->CommutativeRing; VectorSpace->Field; } }

Single binary operation algebraic structures¶

Let S be a set and . be a binary operation defined over it.

Magma¶

S is closed under .

Magma is also known as groupoid at times. But category theory gives a different interpretation to the term groupoid.

Example: binary tree whose leaves are elements of some set A.

Semigroup¶

S is closed under .
Operator . is associative.

Examples:

Let A be a set, and S be a set of functions from A to A. Then (S, .) is a semigroup, where . is the composition operation defined by $(f . g)(x) = f(g(x))$.
Let $\mathbb{Z}^+$ be the positive integers. Then $(\mathbb{Z}^+, +)$ is a semigroup.

Monoid¶

A semigroup (S, .) is a monoid if it has an identity element.

$e.x = x.e = x$

If there is an identity element, then it is unique.

A semigroup can be turned into a monoid by adding a new identity element (if it doesn’t have one already).

Group¶

A monoid (S,.) is a group if for each a and b in S, there are solutions x and y to the equations $ax=b$ and $ya=b$. This implies existence of inverse. Also it can be shown that left inverse and right inverse are equal.

Examples

Let $S={x}$ and let $x*x=x$. Then $(S,*)$ is a group with identity x and $x^{-1}=x$.
$\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{Z}$ are groups with the binary operation +, but not with the binary operation $*$.

Abelian Group¶

If a group is commutative which means that $xy=yx \forall x,y \in S$, then it is an abelian group.

Operations on algebras¶

Subalgebras¶

A subalgebra of an algebra A is obtained by taking a subset S’ of the carrier that is closed under all operations of the algebra. Any axioms satisfied by the parent algebra are inherited by its subalgebras.

A subalgebra generated by a particular element or a set of elements is the the smallest algebra of a given algebra that includes the specified elements. These elements are called generators.

Homomorphism¶

A function from the carrier of A to the carrier of B is a homomorphism written $f:A\rightarrow B$, if for any n-ary operation g, $g(f(x_1), ..., f(x_n)) = f(g(x_1, ..., x_n))$, where g on the left side is B’s version of g and g on the right side is A’s version of g. If the operation holds for a particular operation g, then f is said to preserve g. A homomorphism preserves all operations.

Image of f is defined as $f(A) = \{f(x) | x \in A\}$.
Let $f:A\rightarrow B$ be an algebra homomorphism. Then f(A) is a subalgebra of B.

Two operation algebraic structures¶

For more details see

Change log

Last Modified: $Id: overview.rst 249 2012-08-05 06:17:57Z shailesh $

Linear Algebra¶

Contents:

Introduction¶

These notes are compiled from my study of linear algebra.

Definitions and theorems are covered but their proofs are skipped.
Useful examples are covered in short.
For further details, please refer to real books.

References¶

[HoffmanKunzLinAlg]

Hitch hiker’s guide¶

Defining a vector space¶

Choose the field F over which vector space will be defined.
Choose the set of objects V which will become vector space.
Define the addition operation s.t.
- Set is closed under addition
- Commutativity holds
- Associativity holds
- Additive identity exists
- Additive inverse exists
Define the scalar multiplication (from a constant $c \in F$) s.t.
- Scalar multiplication with 1 leads to no change
- Distributive laws hold
- Associative law holds over two multiplicands $c_1, c_2$
Be Happy!

Linear Equations¶

Vector Spaces¶

Definition

A vector space (or linear space) consists of the following:

a field $F$ of scalars;
a set $V$ of objects, called vectors;
a rule (or operation), called vector addition, which associates with each pair of vectors $\alpha, \beta \in V$ a vector $\alpha + \beta \in V$, called the sum of $\alpha$ and $\beta$, in such a way that
- addition is commutative, $\alpha + \beta = \beta + \alpha$;
- addition is associative, $\alpha + (\beta + \gamma) = (\alpha + \beta) + \gamma$;
- there is a unique vector $0 \in V$, called the zero vector, such that $\alpha + 0 = \alpha \quad \forall \alpha \in V$;
- for each vector $\alpha \in V$, there is a unique vector $-\alpha \in V$ such that $\alpha + (-\alpha) = 0$;
a rule (or operation), called scalar multiplication, which associates with each scalar $c \in F$ and vector $\alpha \in V$ a vector $c\alpha \in V$ in such a way that
- $1\alpha = \alpha \quad \forall \alpha \in V$;
- $(c_1 c_2)\alpha = c_1 (c_2 \alpha)$;
- $c (\alpha + \beta) = c\alpha + c\beta$;
- $(c_1 + c_2) \alpha = c_1 \alpha + c_2 \alpha$.

Example 1

The n-tuple space, $F^n$

Example 2

The space of $m\times n$ matrices $F^{m \times n}$

Example 3

The space of functions from a set $S$ to a field $F$.

Example 4

The space of polynomial functions over field $F$.

\[f(x) = c_0 + c_1 x + \dots + c_n x^n\]

Example 5

Field of complex numbers $C$ as a vector space over the field $R$ of real numbers.

Remarks

$0\alpha = 0$.
If $c \neq 0$ and $c \alpha = 0$, then $\alpha = 0$.
$(-1)\alpha = -\alpha$.

Definition

A vector $\beta \in V$ is said to be a linear combination of the vectors $\alpha_1, \dots, \alpha_n \in V$ provided there exist scalars $c_1, \dots c_n \in F$ such that

\[\begin{split}\beta &= c_1 \alpha_1 + \dots + c_n \alpha_n\\ &= \sum_{i=1}^{n}c_i \alpha_i\end{split}\]

Subspaces¶

Definition

Let $V$ be a vector space over the field $F$. A subspace of $V$ is a subset $W \subset V$ which is itself a vector space over $F$ with the operations of vector addition and scalar multiplication on $V$.

Theorem 1

A non-empty subset $W$ of $V$ is a subspace of $V$ if and only if for each pair of vectors $\alpha, \beta$ in $W$, and each scalar $c$ in $F$, the vector $c\alpha + \beta$ is again in $W$.

Example 6

If $V$ is a vector space, $V$ is a subspace of $V$.
The subset $\{0\}$ is a subspace of $V$ called the zero subspace of $V$.
In $F^n$, the set of n-tuples $(x_1, \dots, x_n)$ with $x_1 = 0$ is a subspace of $F^n$. The set of n-tuples with $x_1 = 1 + x_2$ is not a subspace.
The space of polynomial functions over the field $F$ is a subspace of the space of all functions from $F$ into $F$.
An $n \times n$ (square) matrix $A$ over the field $F$ is symmetric if $A_{i j} = A_{j i} \forall i,j$. The symmetric matrices form a subspace of the space of all $n \times n$ matrices over $F$.
An $n \times n$ matrix $A$ over the field $C$ of complex numbers is Hermitian if

\[A_{j k} = \overline{A_{k j}} \quad \forall j,k.\]

The set of Hermitian matrices is not a subspace of the space of all $n \times n$ matrices over $C$.

Example 7

The solution space of a system of homogeneous linear equations.

Let $A$ be an $m\times n$ matrix over field $F$.
The set of all $n \times 1$ (column) matrices over $F$ such that $AX = 0$ is a subspace of of the space of all $n \times 1$ matrices over $F$.

Lemma

If $A$ is an $m \times n$ matrix over $F$ and $B,C$ are $n \times p$ matrices over $F$, then

\[A (dB + C) = d(AB) + AC \quad \forall d \in F.\]

Theorem 2

Let $V$ be a vector space over the field $F$. The intersection of any collection of subspaces of $V$ is a subspace of $V$.

Definition

Let $S$ be a set of vectors in a vector space $V$. The subspace spanned by $S$ is defined to be the intersection $W$ of all subspaces of $V$ which contain $S$. When $S$ is a finite set of vectors, $S = \{\alpha_1, \dots, \alpha_n\}$, we shall simply call $W$ the subspace spanned by the vectors $\alpha_1, \dots \alpha_n$.

Theorem 3

The subspace spanned by a non-empty subset $S$ of a vector space $V$ is a set of all linear combinations of vectors in $S$.

Definition

If $S_1, S_2, \dots, S_k$ are subsets of a vector space $V$, the set of all sums

\[\alpha_1 + \alpha_2 + \dots + \alpha_k\]

of vectors $\alpha_i \in S_i$ is called the sum of the subsets $S_1, S_2, \dots, S_k$ and is denoted by

\[S_1 + S_2 + \dots + S_k\]

or by

\[\sum_{i=1}^{k} S_i\]

If $W_1, W_2, \dots, W_k$ are subspaces of $V$, then the sum

\[W = W_1 + W_2 + \dots + W_k\]

is easily seen to be a subspace of $V$ which contains each of the subspaces $W_i$. $W$ is the subspace spanned by the union of $W_1, W_2, \dots, W_k$.

Example 10

Let $A$ be an $m \times n$ matrix over a field $F$. The row vectors of $A$ are the vectors in $F^n$ given by $\alpha_i = (A_{i1}, \dots , A_{in}), i = 1,\dots,m$. The subspace of $F^n$ spanned by the row vectors of $A$ is called the row space of $A$.

Example 11

Let $V$ be the space of all polynomial functions over $F$. Let $S$ be the subset of $V$ consisting of the polynomial functions $f_0, f_1, f_2,\dots$ defined by:

\[f_n(x) = x^n, \quad n = 0,1,2,\dots\]

Then $V$ is the subspace spanned by the set $S$.

Bases and dimensions¶

Definition

Let $V$ be a vector space over $F$. A subset $S$ of $V$ is said to be linearly dependent (or simply dependent) if there exist distinct vectors $\alpha_1, \alpha_2, \dots, \alpha_n$ in $S$ and scalars $c_1, c_2, \dots, c_n$ in $F$, not all of which are 0, such that:

\[c_1 \alpha_1 + c_2 \alpha_2 + \dots + c_n \alpha_n = 0\]

A set which is not linearly dependent is called linearly independent. If the set S contains only finitely many vectors $\alpha_1, \alpha_2, \dots, \alpha_n$, we sometimes say that $\alpha_1, \alpha_2, \dots, \alpha_n$ are dependent (or independent) instead of saying $S$ is dependent (or independent).

Any set which contains a linearly dependent set is linearly dependent.
Any subset of a linearly independent set is linearly independent.
Any set which contains the 0 vector is linearly dependent.
A set $S$ of vectors is linearly independent if and only if each finite subset of $S$ is linearly independent, i.e. if and only if for any distinct vectors $\alpha_1, \alpha_2, \dots, \alpha_n \in S$, $c_1 \alpha_1 + c_2 \alpha_2 + \dots + c_n \alpha_n = 0$ implies that each $c_i = 0$.

Definition

Let $V$ be a vector space. A basis for $V$ is a linearly independent set of vectors in $V$ which spans the space $V$. The space $V$ is finite -dimensional if it has a finite basis.

Example 13

Let $F$ be a field and in $F^n$ let $S$ be the subset consisting of vectors $\epsilon_1, \epsilon_2, \dots, \epsilon_n$ defined by:

\[\begin{split}\epsilon_1 &= (1,0,0,\dots, 0)\\ \epsilon_2 &= (0,1,0,\dots, 0)\\ &\dots\\ \epsilon_n &= (0,0,0,\dots, 1)\end{split}\]

Lets $x_1, x_2, \dots, x_n$ be scalars in $F$ and put

\[\alpha = x_1 \epsilon_1 + x_2 \epsilon_2 + \dots + x_n \epsilon_n\]

Then

\[\alpha = (x_1, x_2, \dots, x_n)\]

This shows that $\epsilon_1, \epsilon_2, \dots, \epsilon_n$ span $F^n$. Since $\alpha = 0$ if and only if $x_1 = x_2 = \dots = x_n = 0$, the vectors $\epsilon_1, \epsilon_2, \dots, \epsilon_n$ are linearly independent. The set $S = \{\epsilon_1, \epsilon_2, \dots, \epsilon_n\}$ is accordingly a basis for $F^n$. We shall call particular basis the standard basis of $F^n$.

Example 14

Let $P$ be an invertible $n \times n$ matrix with entries in the field $F$.
Then $P_1, \dots, P_n$, the columns of $P$, form a basis for the space of column matrices, $F^{n\times 1}$.
If $X$ is a column matrix, then

\[PX= x_1P_1 + \dots + x_n P_n\]

Since $PX = 0$ has only the trivial solution $X = 0$, it follows that $\{P_1, \dots, P_n\}$ is a linearly independent set.
Why does it span $F^{n \times 1}$ ?
Let $Y$ be any column matrix.
If $X = P^{-1} Y$, then $Y = PX$, i.e.

\[Y = x_1 P_1 + \dots + x_n P_n.\]
So $\{P_1, \dots, P_n\}$ is a basis for $F^{n \times 1}$.

Example 15

TBD

Example 16

Polynomial functions infinite basis

Let $F$ be a subfield of complex numbers and let $V$ be the space of polynomial functions over $F$.

\[f(x) = c_0 + c_1 x + \dots + c_n x^n.\]
Let $f_k(x) = x^k, k = 0,1,2,\dots$
The infinite set $\{f_0, f_1, \dots\}$ is a basis for $V$.
The set spans $V$, because the function $f$ above can be expressed as:

\[f = c_0 f_0 + c_1 f_1 + \dots + c_n f_n.\]
The set $\{f_0, f_1, \dots\}$ is independent if every finite subset of it is independent.
Consider set $\{f_0, f_1, \dots, f_n\}$.
Suppose that:

\[c_0f_0 + c_1f_1 + \dots + c_n f_n = 0\]

i.e.

\[c_0 + c_1 x + c_n x^n = 0 \quad \forall x \in F.\]
It means: every $x \in F$ is a root of the polynomial $f(x) = c_0 + c_1 x + c_n x^n$.
A polynomial of degree $n$ cannot have more than $n$ distinct roots.
Hence $c_0 = c_1 = \dots = c_n = 0$.
Hence the set $\{f_0, f_1, \dots, f_n\}$ is linearly independent.

Is the vector space $V$ infinite dimensional?

Assume that $V$ has a finite basis.
Suppose polynomials $\{g_1, \dots, g_r\}$ form the basis.
There will be a largest power of $x$ which appears in one of the $g_i$.
If the power is $k$, then clearly $f_{k+1}(x) = x^{k+1}$ is not in the span of $\{g_1, \dots, g_r\}$.
Hence $V$ is not finite dimensional.

Theorem 4

Let $V$ be a vector space which is spanned by a finite set of vectors $\beta_1, \beta_2, \dots \beta_m$. Then any independent set of vectors in $V$ is finite and contains no more than $m$ elements.

Corollary 1

If $V$ is a finite-dimensional vector space, then any two bases of $V$ have the same (finite) number of elements.

Definition

The dimension of a finite-dimensional vector space $V$ is defined as the number of elements in a basis for $V$. This is denoted by $\dim V$.

Corollary 2

Let $V$ be a finite-dimensional vector space and let $n = \dim V$. Then

any subset of $V$ which contains more than $n$ vectors is linearly dependent.
No subset of $V$ which contains less than $n$ vectors can span $V$.

Lemma

Let $S$ be a linearly independent subset of a vector space $V$. Suppose $\beta$ is a vector in $V$ which is not in the subspace spanned by $S$. Then the set obtained by adjoining $\beta$ to $S$ is linearly independent.

Example 17

TBD

Theorem 5

If $W$ is a subspace of a finite-dimensional vector space $V$, every linearly independent subset of $W$ is finite and is part of a (finite) basis for $W$.

Corollary 1

If $W$ is a proper subspace of a finite-dimensional vector space $V$, then $W$ is finite dimensional and $\dim W < \dim V$.

Corollary 2

In a finite dimensional vector space $V$ every non-empty linearly independent set of vectors is part of a basis.

Corollary 3

Let $A$ be an $n \times n$ matrix over a field $F$, and suppose the row vectors of $A$ form a linearly independent set of vectors in $F^n$. Then $A$ is invertible.

Theorem 6

If $W_1$ and $W_2$ are finite-dimensional subspaces of a vector space $V$, then $W_1 + W_2$ is finite-dimensional and

\[\dim W_1 + \dim W_2 = dim (W_1 \cap W_2) + dim (W_1 + W_2)\]

Coordinates¶

A basis $\mathfrak{B}$ in an n-dimensional space $V$ enables one to introduce coordinates in $V$ analogous to the ‘natural coordinates’ $x_i$ of a vector $\alpha = (x_1, \dots, x_n)$ in the space $F^n$.

Definition

IF $V$ is a finite-dimensional vector space, an ordered basis for $V$ is a finite sequence of vectors which is linearly independent and spans $V$.

If $\alpha_1, \dots, \alpha_n$ is an ordered basis for $V$, then the set $\{\alpha_1, \dots, \alpha_n\}$ is a basis for $V$.
Ordered basis is a set together with a specified ordering.
We shall abuse the notation and say that:

\[\mathfrak{B} = \{\alpha_1, \dots, \alpha_n\}\]

is an ordered basis for $V$.
Given $\alpha \in V$, there is a unique n-tuple $x = (x_1, x_2, \dots, x_n)$ such that:

\[\alpha = \sum_{i=1}^{n} x_i \alpha_i\]
We shall call $x_i$ the ith coordinate of $\alpha$ relative to the ordered basis $\mathfrak{B}$.
If

\[\beta = \sum_{i=1}^{n} y_i \alpha_i\]
then

\[\alpha + \beta = \sum_{i=1}^{n} (x_i + y_i) \alpha_i\]
The ith coordinate of $(\alpha + \beta)$ in the ordered basis is $(x_i + y_i)$.
Similarly ith coordinate of $c\alpha$ is $c x_i$.
Every n-tuple $x = (x_1, x_2, \dots, x_n)$ in $F^n$ is the n-tuple of coordinates of some vector in $V$ namely the vector:

\[\sum_{i=1}^{n} x_i \alpha_i\]
Each ordered basis for $V$ determines a one-one correspondence

\[\alpha \mapsto (x_1, \dots, x_n)\]

between the set of all vectors in $V$ and the set of all n-tuples in $F^n$.

Definition

Coordinate matrix of $\alpha$ relative to the ordered basis $\mathfrak{B}$:

\[\begin{split}X = \left[\begin{array} {c} x_1\\ \vdots \\ x_n \end{array}\right]\end{split}\]

To indicate the dependence of this coordinate matrix on the basis, we shall use the symbol

\[[\alpha]_{\mathfrak{B}}\]

Theorem 7

Let $V$ be an n-dimensional vector space over the field $F$, and let $\mathfrak{B}$, and $\mathfrak{B}'$ be two ordered bases of $V$. Then there is a unique, necessarily invertible, $n \times n$ matrix $P$ with entries in $F$ such that

$[\alpha]_{\mathfrak{B}} = P [\alpha]_{\mathfrak{B}'}$
$[\alpha]_{\mathfrak{B}'} = P^{-1} [\alpha]_{\mathfrak{B}}$

for every vector $\alpha$ in $V$. The columns of $P$ are given by

\[P_j = [\alpha'_j]_{\mathfrak{B}}\]

where

\[ \begin{align}\begin{aligned}\mathfrak{B} = \{ \alpha_1, \dots, \alpha_n \}\\\mathfrak{B}' = \{ \alpha'_1, \dots, \alpha'_n \}\end{aligned}\end{align} \]

Thus $P$ represents the basis vectors in $\mathfrak{B}'$ in terms of basis vectors in $\mathfrak{B}$.

Theorem 8

Suppose $P$ is an $n \times n$ invertible matrix over $F$. Let $V$ be an n-dimensional vector space over $F$, and let $\mathfrak{B}$ be an ordered basis of $V$. Then there is a unique ordered basis $\mathfrak{B}'$ of $V$ such that

$[\alpha]_{\mathfrak{B}} = P [\alpha]_{\mathfrak{B}'}$
$[\alpha]_{\mathfrak{B}'} = P^{-1} [\alpha]_{\mathfrak{B}}$

for every vector $\alpha$ in $V$.

Example 18

Let $F$ be a field and let

\[\alpha = (x_1, x_2, \dots, x_n)\]

be a vector in $F^n$. If $\mathfrak{B}$ is the standard ordered basis of $F^n$,

\[\mathfrak{B} = {\epsilon_1, \epsilon_2, \dots,\epsilon_n}\]

the coordinate matrix of the vector $\alpha$ in the basis $\mathfrak{B}$ is given by :

\[\begin{split}[\alpha]_{\mathfrak{B}} = \left[ \begin{array}{c} x_1\\x_2\\\vdots\\x_n \end{array} \right]\end{split}\]

Let $R$ be the field of real numbers and let $\theta$ be a fixed real number. The matrix

\[\begin{split}P = \left[ \begin{array}{rr}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{array} \right]\end{split}\]

is invertible with inverse:

\[\begin{split}P^{-1} = \left[ \begin{array}{rr}\cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{array} \right]\end{split}\]

Thus for each $\theta$, the set consisting of vectors $(\cos\theta, \sin\theta), (-\sin\theta,\cos\theta)$ is a basis for $R^2$; intuitively the basis may be described as the one obtained by rotating the standard basis through the angle $\theta$.

If $\alpha$ is the vector $(x_1, x_2)$ then,

\[\begin{split}[\alpha]_{\mathfrak{B}'} = P^{-1} [\alpha]_{\mathfrak{B}} = \left[ \begin{array}{rr}\cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{array} \right] \left[\begin{array}{c}x_1 \\ x_2 \end{array} \right]\end{split}\]

or

\[\begin{split}x'_1 &= x_1 \cos\theta + x_2 \sin\theta\\ x'_2 &= -x_1 \sin\theta + x_2 \cos\theta.\end{split}\]

Summary of row-equivalence¶

If $A$ is an $m \times n$ matrix over the field $F$ the row vectors of $A$ are the vectors $\alpha_1, \dots, \alpha_n$ in $F^n$ defined by:

\[\alpha_i = (A_{i 1}, \dots, A_{i n})\]
The row space of $A$ is the subspace of $F^n$ spanned by these vectors.

Definition

The row rank of $A$ is the dimension of the row space of $A$.

If $P$ is a $k \times m$ matrix over $F$, then the product $B = PA$ is a $k \times n$ matrix whose row vectors $\beta_1, \dots, \beta_n$ are linear combinations

\[\beta_i = P_{i 1} \alpha_1 + \dots + P_{i m} \alpha_m\]

of the row vectors of $A$.

Visualizing as a matrix multiplication:

\[\begin{split}\begin{bmatrix} \beta_1 \\ \vdots \\ \beta_k\end{bmatrix} = \begin{bmatrix} P_{1 1} & \ldots & P_{1 m} \\ \vdots & \ddots & \vdots \\ P_{k 1} & \ldots & P_{k m} \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \vdots \\ \alpha_m \end{bmatrix}\end{split}\]
The row space of $B$ is a subspace of row space of $A$.
If $P$ is an $m \times m$ invertible matrix, then $B$ is row-equivalent to $A$.
- $A = P^{-1} B$
- Thus row-space of $A$ is also a subspace of row space of $B$.

Theorem 9

Row-equivalent matrices have the same row space.

Theorem 10

Let $R$ be a non-zero row-reduced echelon matrix of $A$. Then the non-zero row vectors of $R$ form a basis for the row space of $A$.

Theorem 11

Let $m$ and $n$ be positive integers and let $F$ be a field. Suppose $W$ is a subspace of $F^n$ and $\dim W \leq m$. Then there is precisely one $m \times n$ row -reduced echelon matrix over $F$ which has $W$ as its row space.

Long proof here.

Corollary

Each $m \times n$ matrix $A$ is row-equivalent to one and only one row-reduced echelon matrix.

Corollary

Let $A$ and $B$ be $m \times n$ matrices over the field $F$. Then $A$ and $B$ are row equivalent if and only if they have the same row space.

If $A$ and $B$ are $m \times n$ matrices over the field $F$, the following statements are equivalent.

$A$ and $B$ are row-equivalent.
$A$ and $B$ have same row space.
$B = PA$, where $P$ is an invertible $m \times m$ matrix.

Computations concerning subspaces¶

Suppose we are given $m$ vectors $\alpha_1,\dots,\alpha_m$ in $F^n$. We consider the following questions

How does one determine if the vectors $\alpha_1,\dots,\alpha_m$ are linearly independent?
How does one find the dimension of the subspace $W$ spanned by these vectors?
Given $\beta \in F^n$, how does one determine whether $\beta$ is a linear combination of $\alpha_1,\dots,\alpha_m$, i.e., whether $\beta \in W$?
How can one give an explicit description of the subspace $W$?

Linear Transformations¶

Definition

Let $V$ and $W$ be vector spaces over the field $F$. A linear transformation from $V$ into $W$ is a function $T$ from $V$ into $W$ such that

\[T(c\alpha + \beta) = c(T(\alpha) + T\beta \quad \forall \alpha, \beta \in V, \forall c \in F\]

Polynomials¶

Determinants¶

Elementary Canonical Forms¶

Rational Jordan Forms¶

Inner Product Spaces¶

Operators on Inner Product Spaces¶

Bilinear Forms¶

Explorations¶

This section covers some ideas which I need to pursue further

HK p. 34, Sec. 2.1 Ex. 4

Let $V$ be the set of all pairs $(x,y)$ of real numbers, and let $F$ be the field of real numbers. Define

\[ \begin{align}\begin{aligned}(x,y) + (x_1, y_1) = (x + x_1, y + y_1)\\c(x,y) = (cx,y)\end{aligned}\end{align} \]

Verify that this is a vector space.
Whats the use of this system in engineering?

Matrix Algebra¶

Contents:

Introduction¶

Garden¶

This page is a collection of a variety of matrices used in different examples and contexts and their associated results.

Square Matrices¶

2x2 matrices¶

Simple examples

\[\begin{split}A &= \begin{bmatrix} 3 & 1 \\ 5 & 2 \end{bmatrix}\\ det(A) &= 1\\ A^{-1} &= \begin{bmatrix}2 & -1\\ -5 & 3 \end{bmatrix}\end{split}\]

3x3 matrices¶

\[\begin{split}A &= \begin{bmatrix} 1 & 3 & 2\\ 4 & 1 & 3\\ 2 & 5 & 2 \end{bmatrix}\\ minor(A) &= \begin{bmatrix} -13 & 2 & 18 \\ -4 & -2 & -1 \\ 7 & -5 & -11 \end{bmatrix}\\ cof(A) &= \begin{bmatrix} -13 & -2 & 18 \\ 4 & -2 & 1 \\ 7 & 5 & -11 \end{bmatrix}\\ adj(A) &= \begin{bmatrix} -13 & 4 & 7 \\ -2 & -2 & 5\\ 18 & 1 & -11 \end{bmatrix}\\ det(A) &= 17\\ A^{-1} &= \begin{bmatrix} -13/17 & 4/17 & 7/17 \\ -2/17 & -2/17 & 5/17\\ 18/17 & 1/17 & -11/17 \end{bmatrix}\end{split}\]

4x4 matrices¶

\[\begin{split}S &= \begin{bmatrix} 3 & 2 & 0 & 1\\ 4 & 0 & 1 & 2 \\ 3 & 0 & 2 & 1\\ 9 & 2 & 3 & 1 \end{bmatrix}\\ |S| &= 24\end{split}\]

Lets write this as

\[\begin{split}S &= \begin{bmatrix} A & B \\ C & D \end{bmatrix}\end{split}\]

Where

\[\begin{split}A &= \begin{bmatrix} 3 & 2 \\ 4 & 0 \end{bmatrix}\\ B &= \begin{bmatrix} 0 & 1 \\ 1 & 2 \end{bmatrix}\\ C &= \begin{bmatrix} 3 & 0 \\ 9 & 2 \end{bmatrix}\\ D &= \begin{bmatrix} 2 & 1 \\ 3 & 1 \end{bmatrix}\end{split}\]

We have:

\[|S| = |A| |D - CA^{-1}B|\]

\[\begin{split}|A| &= -8\\ A^{-1} &= \begin{bmatrix}0 & 1/4 \\ 1/2 & -3/8 \end{bmatrix}\\ CA^{-1} &= \begin{bmatrix} 0 & 3/4 \\ 1 & 3/2 \end{bmatrix}\\ CA^{-1}B &= \begin{bmatrix} 3/4 & 3/2 \\ 3/2& 4\end{bmatrix}\\ D - CA^{-1}B &= \begin{bmatrix} 5/4 & -1/2 \\ 3/2& -3\end{bmatrix}\\ |D - CA^{-1}B| &= -3\\ |S| &= |A||D - CA^{-1}B| = -8 \times -3 = 24\end{split}\]

Inverse

\[\begin{split}\begin{bmatrix} A & B \\ C & D \end{bmatrix} \begin{bmatrix} E & F \\ G & H \end{bmatrix} = I\end{split}\]

gives

\[\begin{split}E &= (A - BD^{-1}C)^{-1}\\ G &= -D^{-1}CE\\ H &= (D - CA^{-1}B)^{-1}\\ F &= -A^{-1}BH\end{split}\]

Algorithm:

$P = D^{-1}C$
$E = (A - BP)^{-1}$
$G = - P E$
$Q = A^{-1}B$
$H = (D - CQ)^{-1}$
$F=-Q H$

Special 2x2 matrices¶

Following are 2x2 matrices such that $A^2 = A$.

\[ \begin{align}\begin{aligned}\begin{split}\left[\begin{array}{cc}1 & 0 \\ 0 & 0\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}0 & 0 \\ 0 & 1\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}1 & 0 \\ 0 & 1\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}1 & 1 \\ 0 & 0\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}0 & 0 \\ 1 & 1\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}1 & 0 \\ 1 & 0\end{array}\right]\end{split}\\\begin{split}\left[\begin{array}{cc}0 & 1 \\ 0 & 1\end{array}\right]\end{split}\end{aligned}\end{align} \]

Flip matrix

\[\begin{split}\left[\begin{array}{cc}0 & 1 \\ 1 & 0\end{array}\right] \left[\begin{array}{cc}0 & 1 \\ 1 & 0\end{array}\right] = \left[\begin{array}{cc}1 & 0 \\ 0 & 1\end{array}\right]\end{split}\]

Polynomials¶

Contents:

Chebyshev polynomials¶

Cosines¶

We know that

\[\cos(\alpha + \beta) = \cos\alpha \cos\beta - \sin \alpha \sin\beta\]
Put $\alpha = n\theta$ and $\beta = \theta$

\[\cos((n+1)\theta) = \cos n\theta \cos\theta - \sin n\theta \sin \theta\]
Put $\alpha = n\theta$ and $\beta = -\theta$

\[\cos((n-1)\theta) = \cos n\theta \cos\theta + \sin n\theta \sin \theta\]
Adding

\[ \begin{align}\begin{aligned}\cos((n-1)\theta) + \cos((n+1)\theta) = 2\cos n\theta \cos\theta\\\cos((n+1)\theta) = 2\cos n\theta \cos\theta - \cos((n-1)\theta)\end{aligned}\end{align} \]
We claim that for each non-negative integer $n$, there exist integers $c_i$ s.t.

\[\cos n\theta = \sum_{i=0}^{n} c_i \cos^i (\theta)\]

Chebyshev polynomials¶

Essentially $\cos n\theta$ is a polynomial in $\cos \theta$.
For a fixed $n$ we define $n^{th}$ Chebyshev polynomial as:

\[cos(n\theta) = T_n(cos\theta))\]
Putting $x = \cos\theta$, $T_n(x)$ is a polynomial.

\[T_n(x) = \cos(n \arccos(x)) \quad \forall x \in [-1,1]\]
Basic Chebyshev polynomials:

\[\begin{split}&T_0(x) = \cos 0 \theta = 1 \\ &T_1(x) = \cos 1 \theta = x\end{split}\]
Recurrence relation:

\[\begin{split}&T_{n-1}(x) + T_{n+1}(x) = 2 T_1(x) T_n(x) = 2x T_n(x)\\ &T_{n+1}(x) = 2x T_n(x) - T_{n-1}(x)\end{split}\]

or

\[x T_n(x) = \frac{T_{n-1}(x) + T_{n+1}(x)}{2}\]

This has resemblance to space shift operator in algebraic signal processing.
Recurrence examples:

\[\begin{split}&T_2(x) = 2x T_1(x) - T_0(x) = 2x^2 - 1\\ &T_3(x) = 2 T_2(x) - T_1(x) = 2x(2x^2 -1) - x = 4x^3 - 3x\end{split}\]
Chebyshev polynomials upto 7th order

\[\begin{split}&T_0(x) = 1 \\ &T_1(x) = x \\ &T_2(x) = 2x^2 - 1\\ &T_3(x) = 4x^3 - 3x\\ &T_4(x) = 8x^4 - 8x^2 + 1\\ &T_5(x) = 16x^5 - 20x^3 + 5x\\ &T_6(x) = 32x^6 - 48x^4 + 18x^2 - 1\\ &T_7(x) = 64x^7 - 112x^5 + 56x^3 -7x\end{split}\]

Properties¶

Maximum value

\[\max_{-1\leq x \leq 1}T_n(x) = 1\]

Composition

\[T_m(T_n(x)) = T_{mn}(x)\]

Proof:

\[\cos(m \arccos(\cos(n \arccos(x)))) = \cos(mn \arccos(x))\]

Zeros

Zeros of $T_n(x)$ are given by:

\[x_k = \cos (\frac{(2k-1)\pi}{2n})\quad 1 \leq k \leq n\]

All the roots of $T_n(x)$ are real and lie in the interval $[-1,1]$.

Recurrence

\[T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x)\]

Thus:

\[T_{n}(x) = 2^{n-1}x^n + \mathbb{O}(x^{n-1})\]

Symmetry

Lets compute $T_{-1}(x)$.

\[\begin{split}&T_1(x) = 2 xT_0(x) - T_{-1}(x) \\ \implies &T_{-1}(x) = 2 xT_0(x) - T_1(x)\\ &= 2x - x = x = T_1(x)\end{split}\]
It can be shown that:

\[T_n(x) = T_{-n}(x)\]

The sequence of Chebyshev polynomials is symmetric.

Power form¶

Euler formula:

\[\cos \theta = \frac{e^{j\theta} + e^{-j\theta}}{2}\]

Define $u = e^{j\theta}$

\[x = \cos \theta = \frac{u^{1} + u^{-1}}{2}\]
Thus

\[T_n(x) = \cos n\theta = \frac{u^{n} + u^{-n}}{2}\]

Differential equation¶

Even/odd polynomials

\[T_n(-x) = (-1)^n T_n(x)\]

Even degree Chebyshev polynomials are even functions.
Odd degree Chevyshev polynomials are odd functions.

Differential equation

It can be shown that:

\[(1-x^2)T''_n(x) - xT'_n(x) + n^2T_n(x) = 0\]
Assume that $y = \sum_{k=0}^{n}t_k x^k$ is a solution to above differential equation. Then:

\[(n^2 - k^2)t_k + (k+1)(k+2)t_{k+2} = 0\]
We already know that $t_n = 2^{n-1}$
Solving further we get:

\[t_{n-2m} = (-1)^m 2^{n - 2m -1} \frac{n}{n - m} {n -m \choose m}\]

Orthogonality¶

The integral

\[\int_0^{\pi} \cos (m\theta) \cos (n\theta) d\theta\]

is zero unless $m=n$.

If $m=n$

If $m=n=0$, integral is $\pi$.
Otherwise, integral is $\pi/2$

Putting $x = \cos\theta$

\[\int_0^{\pi} \cos (m\theta) \cos (n\theta) d\theta = \int_{-1}^{1} T_m(x) T_n(x) \frac{dx}{\sqrt{1-x^2}}\]

Chebyshev polynomials are orthogonal over $[-1,1]$ w.r.t. weight $(1-x^2)^{-1/2}$
The sequence $\frac{1}{\pi}T_0, \frac{2}{\pi}T_1, \frac{2}{\pi}T_3,\dots$ is an orthonormal system.

Discrete orthogonality condition

Let $x_j$ be roots of $T_N$
The sum:

\[\sum_{k=1}^{N} T(mx_k) T(nx_k)\]
- Is zero if $m \neq n$
- $N$ if $m=n=0$
- $N/2$ otherwise

Chebyshev polynomials of different kinds¶

So far we have looked at Chebyshev polynomials of first kind.
Chebyshev polynomials are generated by the recurrence relation:

\[C_{n+1}(x) = 2xC_n(x) - C_{n-1}(x)\]
$C_0 = 1, C_1 = x$ generates the Chebyshev polynomials of first kind denoted by $T_n(x)$.
Chebyshev polynomials of second, third and forth kind are described below.

References¶

[CookChebyshevPolynomials]

Change log

Last Modified: $Id: chebyshev.rst 249 2012-08-05 06:17:57Z shailesh $

Numerical Linear Algebra¶

Contents:

Special Matrix Forms¶

For a matrix $A$, the diagonal elements are the elements $A_{ij}$ where $i=j$.
The off-diagonal elements are elements $A_{ij}$ such that $i \neq j$.
A diagonal is a list of entries $A_{ij}$ such that $i - j = k$ is a fixed integer.
The main diagonal or principal diagonal or primary diagonal or leading diagonal is the list of entries $A_{ij}$ where $i = j$.

Consider the matrix:

\[\begin{split}A &= \begin{bmatrix} 1 & 3 & 2\\ 4 & 1 & 3\\ 2 & 5 & 2 \end{bmatrix}\\\end{split}\]

Its main diagonal is $[1, 1, 2]$.
The diagonal for $k=1$ is $[4, 5]$.
The diagonal for $k=-1$ is $[3,3]$.

Definition

A diagonal matrix is a matrix whose off-diagonal elements are zero.

Definition

A banded matrix or a band matrix is a sparse matrix whose non-zero entries are confined to a diagonal band consisting of the main diagonal and zero or more diagonals on either side.

Definition

A bidiagonal matrix is a banded matrix with non-zero entries along the main diagonal and either the diagonal above the main diagonal or the diagonal below the main diagonal (but not both). There are exactly two non-zero diagonals.

Definition

An upper bidiagonal matrix is a bidiagonal matrix which has non-zero entries in the diagonal above the main diagonal.

Definition

A lower bidiagonal matrix is a bidiagonal matrix which has non-zero entries in the diagonal below the main diagonal.

Matrix Factorization¶

Contents:

Bidiagonalization¶

Special Linear Systems¶

Sparse Linear Systems¶

Group Theory¶

Symmetric Group $S_3$¶

Definition

If $\sigma: S \mapsto T$ and $\tau: T \mapsto U$, then the composition of $\sigma$ and $\tau$ (also called their product) is the mapping $\sigma \circ \tau: S \mapsto U$ defined by the means of $s(\sigma \circ \tau) = (s\sigma) \tau \quad \forall s \in S$.

Let $G = S_3$, the group of all 1-1 mappings of the set $\{x_1, x_2, x_3\}$ onto itself, under the product as specified above. G is a group of oder 6.
Any mapping $\sigma$ can be specified as:

\[\begin{split}\sigma : \begin{array}{l} x_1 \rightarrow x_i \\ x_2 \rightarrow x_j \\ x_3 \rightarrow x_k \end{array} \quad i,j,k \in \{1,2,3\}, i \neq j, j \neq k, k \neq i\end{split}\]

Simpler notation $\sigma : (x_1, x_2, x_3) \mapsto (x_i, x_j, x_k)$
Even simpler notation $\sigma : (1, 2, 3) \mapsto (i, j, k)$
Simplest notation $\sigma = (i,j,k)$
$S_3 = \{ (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)\}$
Define $e = (1,2,3)$, identity mapping
Define $\phi = (2,1,3)$
Define $\psi = (2,3,1)$

Derivations¶

$\phi^2 = \phi \cdot \phi = (2,1,3) \circ (2,1,3) = (1,2,3) = e$
Thus $\phi^{-1} = \phi$
$\psi^2 = \psi \cdot \psi = (2,3,1) \circ (2,3,1) = (3,1,2)$
$\psi^3 = \psi^2 \cdot \psi = (3,1,2) \circ (2,3,1) = (1,2,3) = e$
Thus $\psi^{-1} = \psi^2$
$\phi\psi = \phi \cdot \psi = (2,1,3) \circ (2,3,1) = (3,2,1)$
$\psi\phi = \psi \cdot \phi = (2,3,1) \circ (2,1,3) = (1,3,2)$
Thus $S_3 = \{ e, \phi, \psi, \phi\psi, \psi\phi, \psi^2 \}$

Elements of $S_3$

Element	Mapping	Inverse	Order
$e$	(1,2,3)	$e$	1
$\phi$	(2,1,3)	$\phi$	2
$\psi$	(2,3,1)	$\psi^2$	3
$\phi\psi$	(3,2,1)	$\phi\psi$	2
$\psi\phi$	(1,3,2)	$\psi\phi$	2
$\psi^2$	(3,1,2)	$\psi$	3

Resources¶

Online proofs¶

Theorem

If every element of a group is its self inverse, then that group is abelian.

http://www.proofwiki.org/wiki/All_Self-Inverse_then_Abelian

Theorem

If all elements of a group G (except e) have order 2, then G is abelian.

Theorem

Every group of prime order is cyclic.

http://planetmath.org/ProofThatEveryGroupOfPrimeOrderIsCyclic.html

Proposition

A group of even order has a non-identity element which is its own inverse. Or a group of even order contains an element of order 2.

http://planetmath.org/AGroupOfEvenOrderContainsAnElementOfOrder2.html

General problems¶

http://math.stackexchange.com/questions/128538/does-the-intersection-of-two-finite-index-subgroups-have-finite-index

Probability and Statistics¶

Introduction¶

Probability is the study of random events.
Statistics is the discipline of using data samples to support claims about populations.
Computation is a tool that is well suited to quantitative analysis.

Anecdotal evidence¶

Evidence based on unpublished data and usually personal (opinion).
Small number of observations
Selection bias

people who join a discussion might be more inclined towards a specific conclusion
Confirmation bias

People who believe the claim might be more likely to contribute examples that confirm it. People who doubt the claim are more likely to cite counter examples.
Inaccuracy

Personal stories, often misremembered, misrepresented, repeated inaccurately.

Statistical approach¶

Data collection
Descriptive statistics
Exploratory data analysis
Hypothesis testing
Estimation

Population

A group we are interested in studying [a group of people, animals, minerals etc.]

Cross sectional study

A study that collects data about a population at a particular point in time

Longitudinal study

A study that follows a population over time, collecting data from the same group repeatedly.

Respondent

A person who responds to a survey.

Cohort

A group of respondents.

Sample

The subset of population used to collect data.

Representative

A sample is representative if every member of the population has the same chance of being in the sample.

Oversampling

The technique of increasing the representation of a sub-population in order to avoid errors due to small sample sizes.

Record

A collection of information about a single person or other object of study.

Field

One of the named variables that makes up a record.

Table

A collection of records.

Raw data

Values collected and recorded with little or no checking, calculation or interpretation.

Recode

A value that is generated by calculation and other logic applied to raw data.

Summary statistic

The result of a computation that reduces a dataset to a single number (or a small set of numbers) that captures some characterisitc of the data.

Apparent effect

A measurement or summary statistic that suggests that something interesting is happening.

Statistically significant

Any apparent effect is statistically significant if it is unlikely to occur by chance.

Artifact

An apparent effect that is caused by bias, measurement error, or some other kind of error.

Change log

Last Modified: $Id: intro.rst 249 2012-08-05 06:17:57Z shailesh $

Descriptive Statistics¶

Mean¶

Sample mean is defined as:

\[\mu = \frac{1}{n} \sum_i x_i\]

Mean of a sample is the summary statistic computed with above formula.
Mean is one way to describe the central tendency of data.
Average is one of many summary statistics one might choose to describe the typical value or the central tendency of a sample.

Variance¶

Variance of a sample is defined by:

\[\sigma^2 = \frac{1}{n-1} \sum_i (x_i - \mu)^2\]

$x_i - \mu$ is called deviation from mean.
Square root of variance ($\sigma$) is called standard deviation.

Distribution¶

Summary statistics are concise but dangerous.
Histogram is a graph which shows the frequency or probability of each value.
Probability in this context is a frequency expressed as a fraction of the sample size.
Process of converting frequency to probability is called normalization.
Normalized histogram is called PMF or Probability Mass Function.
The most common value in a distribution is called its mode.
Mode is also a summary statistic. In certain cases, mode does a very good job of describing the typical value.
Outliers are the values which are far away from central tendency.
It is difficult to compare two histograms.

Outliers¶

Outliers are values far away from central tendency.

Relative Risk¶

Relative risk is a ratio of two probabilities.

Example

Probability that a first baby is born early is 18.2%.
Probability that other babies are born early is 16.8%.
Relative risk is 1.08%.
First babies are about 8% more likely to be early.

Conditional Probability¶

Conditional probability is a probability which depends on some condition.

Central tendency¶: A characteristic of a sample or population; intuitively, it is the most average value.
Spread¶: A characteristic of a sample or population; intuitively it describes how much variability there is.
Variance¶: A summary statistic often used to quantify spread.
Standard deviation¶: The square root of variance, also used as a measure of spread.
Frequency¶: The number of times a value appears in a sample.
Histogram¶: A mapping from values to frequencies or a graph that shows this mapping.
Probability¶: A frequency expressed as a fraction of the sample size.
Normalization¶: The process of dividing a frequency by a sample size to get a probability.
Distribution¶: A summary of the values that appear in a sample and the frequency, or probability of each.
PMF¶: Probability mass function: a representation of a distribution as a function that maps from values to probabilities.
Mode¶: Most frequent value in a sample.
Outlier¶: A value far from the central tendency.
Trim¶: To remove outliers from a dataset.
Bin¶: A range used to group nearby values.
Relative Risk¶: A ratio of two probabilities, often used to measure a difference between distributions
Conditional probability¶: A probability computed under the assumption that some condition holds.
Clinically significant¶: A result, a difference between groups, that is relevant in practice.

Reference¶

[ThinkStatsDowney]

Change log

Last Modified: $Id: descriptive.rst 249 2012-08-05 06:17:57Z shailesh $

Comulative Distribution Functions¶

Change log

Last Modified: $Id: cdf.rst 249 2012-08-05 06:17:57Z shailesh $

Continuous Distributions¶

Change log

Last Modified: $Id: continuous_distributions.rst 249 2012-08-05 06:17:57Z shailesh $

Probability¶

Change log

Last Modified: $Id: probability.rst 249 2012-08-05 06:17:57Z shailesh $

Operations on Distributions¶

Change log

Last Modified: $Id: distribution_operations.rst 249 2012-08-05 06:17:57Z shailesh $

Hypothesis Testing¶

Change log

Last Modified: $Id: hypothesis_testing.rst 249 2012-08-05 06:17:57Z shailesh $

Estimation¶

Change log

Last Modified: $Id: estimation.rst 249 2012-08-05 06:17:57Z shailesh $

Correlation¶

Change log

Last Modified: $Id: correlation.rst 249 2012-08-05 06:17:57Z shailesh $

Topology¶

Topological Spaces¶

Introduction¶

Definition

Let $X$ be a non-empty set. A set $\mathcal{T}$ of subsets of $X$ is said to be a topology on $X$ if:

$X$ and the empty set, $\phi$, belong to $\mathcal{T}$,
the union of any (finite or infinite) number of sets in $\mathcal{T}$ belongs to $\mathcal{T}$, and
the intersection of any two sets in $\mathcal{T}$ belongs to $\mathcal{T}$.

The pair $(X, \mathcal{T})$ is called a topological space.

Example

$X = \{a,b,c,d,e,f\}$ and $\mathcal{T} = \{X, \phi, \{a\}, \{c,d\}, \{a,c,d\}, \{b, c, d, e, f\}\}$.

Definition

Let $X$ be any non-empty set and let $\mathcal{T}$ be the collection of all subsets of $X$. Then $\mathcal{T}$ is called the discrete topology on the set $X$. The topological space $(X,\mathcal{T})$ is called a discrete space.

Definition

Let $X$ be any non-empty set and $\mathcal{T} = \{X,\phi\}$. Then $\mathcal{T}$ is called indiscrete topology and $(X, \mathcal{T})$ is said to be an indiscrete space.

Proposition

If $(X, \mathcal{T})$ is a topological space such that, for every $x \in X$, the singleton set $\{x\}$ is in $\mathcal{T}$, then $\mathcal{T}$ is the discrete topology.

Remark

The intersection of any finite number of members of $\mathcal{T}$ is a member of $\mathcal{T}$.

Definition

Let $\mathbb{N}$ be the set of all positive integers.

$\mathcal{T}_1$ consists of $\mathbb{N}, \phi$, and every set $\{1,2,\dots,n\}$ for $n$ any positive integer. This is called the initial segment topology.
$\mathcal{T}_2$ consists of $\mathbb{N}, \phi$, and every set $\{n,n+1,\dots\}$ for $n$ any positive integer. This is called the final segment topology.

Open Sets, Closed Sets, Clopen Sets¶

Definition

Let $(X, \mathcal{T})$ be any topological space. Then the members of $\mathcal{T}$ are said to be open sets.

Proposition

If $(X,\mathcal{T})$ is any topological space, then

$X$ and $\phi$ are open sets,
the union of any (finite or infinite) number of open sets is an open set, and
the intersection of any finite number of open sets is an open set.

The intersection of infinite number of open sets need not be open.

Definition

Let $(X,\mathcal{T})$ be a topological space. A subset $S$ of $X$ is said to be a closed set in $(X,\mathcal{T})$ if its compliment in $X$, namely $X\setminus S$, is open in $(X,\mathcal{T})$.

Proposition

If $(X,\mathcal{T})$ is any topological space, then

$\phi$ and $X$ are closed sets,
the intersection of any (finite or infinite) number of closed sets is a closed set and
the union of any finite number of closed sets is a closed set.

Example

$X = \{a,b,c,d,e,f\}$ and $\mathcal{T} = \{X, \phi, \{a\}, \{c,d\}, \{a,c,d\}, \{b, c, d, e, f\}\}$.
The closed sets are: $\phi, X, \{b,c,d,e,f\}, \{a,b,e,f\}, \{b,e,f\}, \{a\}$
$\{a\}$ is both open and closed.
$\{b,c\}$ is neither open nor closed.
$\{c,d\}$ is open but not closed.
$\{a,b,e,f\}$ is closed but not open.

Definition

A subset $S$ of a topological space $(X,\mathcal{T})$ is said to be clopen if it is both open and closed in $(X,\mathcal{T})$.

In every topological space $(X,\mathcal{T})$, both $X$ and $\phi$ are always clopen.
In a discrete space all subsets of $X$ are clopen.
In an indiscrete subspace the only clopen subsets are $X$ and $\phi$.

Finite-Closed Topology¶

Sometimes it is more natural to describe the topology by saying which sets are closed.

Definition

Let $X$ be any non-empty set. A topology $\mathcal{T}$ on $X$ is called the finite-closed topology or the cofinite topology if the closed subsets of $X$ are $X$ and all finite subsets of $X$; i.e., the open sets are $\phi$ and all subsets of $X$ which have finite complements.

Example

Let $\mathcal{T}$ be a finite-closed topology over $\mathbb{N}$.
$\{1\}, \{5,7,6\}, \{2,4,6,8\}$ are finite and hence closed.
Their complements are open sets.
Set of even positive integers is not a closed set (its infinite), hence its complement, the set of odd positive integers, is not an open set.
While all finite sets are closed, not all infinite sets are open.

Remark

Let $\mathcal{T}$ be the finite closed topology on a set $X$. If $X$ has at least 3 distinct clopen subsets, then $X$ is a finite set.

Functions and topologies¶

Definitions

Let $f$ be a function from a set $X$ into a set $Y$.

The function $f$ is said to be one-one or injective if $f(x_1)=f(x_2) \implies x_1 = x_2, \forall x_1,x_2\in X$.
The function $f$ is said to be onto or surjective if for each $y \in Y \quad\exists x \in X | f(x) = y$
The function $f$ is said to be bijective if it is both one-one and onto.

Definition

Let $f$ be a function from a set $X$ into a set $Y$. The function $f$ is said to have an inverse if there exists a function $g$ of $Y$ into $X$ such that $g(f(x))=x,\quad \forall x\in X$ and $f(g(y)) = y, \quad\forall y \in Y$. The function $g$ is called the inverse function of $f$.

Proposition

Let $f$ be a function from a set $X$ into a set $Y$.

The function $f$ has an inverse if and only if $f$ is bijective.
Let $g_1$ and $g_2$ be functions from $Y$ into $X$. If $g_1$ and $g_2$ are both inverse functions of $f$, then $g_1=g_2$, that is $g_1(y)=g_2(y) \forall y \in Y$.
Let $g$ be a function from $Y$ into $X$. Then $g$ is an inverse function of $f$ if and only if $f$ is an inverse function of $g$.

Definition

Let $f$ be a function from a set $X$ into a set $Y$. If $S$ is any subset of $Y$, then the set $f^{-1}(S)$ is defined by:

\[f^{-1}(S) = \{x : x \in X \text{ and } f(x) \in S\}\]

The subset $f^{-1}(S)$ of $X$ is said to be the inverse image of $S$.

Remark

Let $(Y, \mathcal{T})$ be a topological space and $X$ a non-empty set. Further, let $f$ be a function from $X$ into $Y$. Put $\mathcal{T}_1 = \{f^{-1}(S) : S \in \mathcal{T}\}$. Then $\mathcal{T}_1$ is a topology on $X$.

$T_0$ and $T_1$ spaces¶

Definition

A topological space $(X, \mathcal{T})$ is said to be a $T_1$-space if every singleton set $\{x\}$ is closed in it.

Definition

A topological space $(X,\mathcal{T})$ is said to be a $T_0$-space if for each pair of distinct points $a,b \in X$, either there exists an open set containing $a$ and not $b$ or there exists an open set containing $b$ and not $a$.

Every $T_1$-space is a $T_0$ space.

Sierpinski space

Let $X = \{0,1\}$
$\mathcal{T} = \{\phi, X, \{0\}\}$ is a $T_0$ space.
$\mathcal{T} = \{\phi, X, \{1\}\}$ is a $T_0$ space.
Both of above are known as Sierpinski spaces.
$\mathcal{T} = \{\phi, X, \{0\}, \{1\}\}$ is a $T_0$ space as well as a $T_1$ space.

Countable-closed topology¶

Definition

Let $X$ be any infinite set. The countable closed topology is defined to be the topology having as its closed sets $X$ and all countable subsets of $X$.

Unions and intersections¶

Let $\mathcal{T}_1$ and $\mathcal{T}_2$ be two topologies on $X$.

$\mathcal{T}_3 = \mathcal{T}_1 \cup \mathcal{T}_2$ need not be a topology on $X$.
$\mathcal{T}_4 = \mathcal{T}_1 \cap \mathcal{T}_2$ is a topology on $X$.
If $(X, \mathcal{T}_1)$ and $(X, \mathcal{T}_2)$ are $T_1$-spaces then $(X, \mathcal{T}_4)$ is also a $T_1$ space.
If $(X, \mathcal{T}_1)$ and $(X, \mathcal{T}_2)$ are $T_0$-spaces then $(X, \mathcal{T}_4)$ need not be a $T_0$ space.
Intersection of any finite number of topologies on $X$ is a topology on $X$.
If for each $i\in I$ for some index set $I$, each $\mathcal{T}_i$ is a topology on the set $X$, then $\mathcal{T} = \cap_{i \in I} \mathcal{T}_i$ is a topology on $X$.

Euclidean Topology¶

Let $\mathbb{R}$ denote the set of all real numbers.

Definition

A subset $S$ of $\mathbb{R}$ is said to be open in the euclidean topology on $\mathbb{R}$ if it has the following property:

(*) For each $x \in S \quad \exists a,b \in \mathbb{R} \text{ and } a < b| x \in (a,b) \subseteq S$.

When we refer to topological space $\mathbb{R}$ without specifying the topology, we mean $\mathbb{R}$ with euclidean topology.
Every open interval $(a,b)$ is an open set.
The open intervals $(r,\infty)$ and $(-\infty, r)$ are open sets $\forall r \in \mathbb{R}$.
While every open interval is an open set, not all open sets are intervals.
For each $c,d \in \mathbb{R}$, the closed interval $[c,d]$ is not an open set.
For each $a,b \in \mathbb{R}$, the closed interval $[a,b]$ is a closed set.
Each singleton set $\{a\}$ is closed in $\mathbb{R}$. Thus $\mathbb{R}$ is a $T_1$-space.
The set $\mathbb{Z}$ of all integers is a closed subset of $\mathbb{R}$.
The set $\mathbb{Q}$ of all rational numbers is neither a closed subset nor an open subset of $\mathbb{R}$.

Definition

Let $(X,\mathcal{T})$ be a topological space. A subset $S$ of $X$ is said to be an $F_{\sigma}$ -set if it is the union of a countable number of closed sets.

All open intervals $(a,b)$ and all closed intervals $[a,b]$ are $F_\sigma$ -sets in $\mathbb{R}$.

Definition

Let $(X,\mathcal{T})$ be a topological space. A subset $T$ of $X$ is said to be an $G_{\sigma}$ -set if it is the intersection of a countable number of open sets.

All open intervals $(a,b)$ and all closed intervals $[a,b]$ are $G_\sigma$ -sets in $\mathbb{R}$.
$\mathbb{Q}$ is an $F_{\sigma}$ set in $\mathbb{R}$ but not a $G_{\sigma}$ set.

Basis¶

Proposition

A subset $S$ of $\mathbb{R}$ is open if and only if it is union of open intervals.

Definition

Let $(X, \mathcal{T})$ be a topological space. A collection $\mathcal{B}$ of open subsets of $X$ is said to be a basis for the topology $\mathcal{T}$ if every open set is a union of the members of $\mathcal{B}$.

$\mathcal{B}$ generates the topology $\mathcal{T}$ in the following sense: if we are told what sets are members of $\mathcal{B}$, then we can determine the members of $\mathcal{T}$.

Example

Let $\mathcal{B} = \{(a,b) | a,b \in \mathbb{R}, a < b\}$. Then $\mathcal{B}$ is a basis for the euclidean topology on $\mathbb{R}$.

Remark

If $(X, \mathcal{T})$ is a topological space, then $\mathcal{B} = \mathcal{T}$ is a basis for the topology $\mathcal{T}$.

There can be many different bases for the same topology.
If $\mathcal{B}$ is a basis for a topology $\mathcal{T}$ on a set $X$ and $\mathcal{B}_1$ is a collection of subsets of $X$ such that $\mathcal{B} \subseteq \mathcal{B}_1 \subseteq \mathcal{T}$, then $\mathcal{B}_1$ is also a basis for $\mathcal{T}$.
Not any arbitrary collection of subsets of $X$ can generate a topology.

Proposition

Let $X$ be a non-empty set and let $\mathcal{B}$ be a collection of subsets of $X$. Then $\mathcal{B}$ is a basis for a topology on $X$ if and only if $\mathcal{B}$ has the following properties.

$X = \underset{B \in \mathcal{B}}{\cup} B$, and
for any $B_1, B_2 \in \mathcal{B}$, the set $B_1 \cap B_2$ is a union of members of $\mathcal{B}$.

It is often easier to describing a topology by writing down its basis rather than describe all its open sets.

Example

Let $\mathcal{B}$ be the collection of all “open rectangles” $\{\langle x,y\rangle: \langle x,y\rangle \in \mathbb{R}^2, a < x < b, c < y < d\}$ in the plane which have each side parallel to the X- or Y-axis.

Then $\mathcal{B}$ is a basis for a topology on the plane.

This topology is the euclidean topology of $\mathbb{R}^2$.
$\mathbb{R}^2$ means the plane, and if we refer to $\mathbb{R}^2$ as a topological space without explicitly specifying the topology, we mean euclidean topology.

Remark

Let $\mathbb{R}^n = \{\langle x_1, x_2, \dots, x_n \rangle : x_i \in \mathbb{R}, i = 1, \dots n \}$. Let $\mathcal{B}$ be the collection of all subsets $\{\langle x_1, x_2, \dots, x_n\rangle \in \mathbb{R}^n: a_i < x_i < b_i, i = 1,2,\dots, n\}$ with sides parallel to the axes. This collection $\mathcal{B}$ is a basis for the euclidean topology on $\mathbb{R}^n$.

Remark

Let $\mathcal{B}_1$ be a basis for a topology $\mathcal{T}_1$ on a set $X$ and $\mathcal{B}_2$ be a basis for a topology $\mathcal{T}_2$ on a set $Y$. The set $X\times Y$ consists of all ordered pairs $\langle x, y \rangle, x \in X, y \in Y$. Let $\mathcal{B}$ be the collection of subsets of $X\times Y$ consisting of all the sets $B_1 \times B_2: B_1 \in \mathcal{B}_1, B_2 \in \mathcal{B}_2$. Then $\mathcal{B}$ is a basis for a topology on $X \times Y$. The topology so defined is called the product topology on $X\times Y$.

Basis for a Given Topology¶

Sometimes we are given a topology $\mathcal{T}$ on $X$ and we want to verify whether $\mathcal{B}$ is a basis for this specific topology $\mathcal{T}$.

Proposition

Let $(X,\mathcal{T})$ be a topological space. A family $\mathcal{B}$ of open subsets of $X$ is a basis for $\mathcal{T}$ if and only if for any point $x \in U \text{ where } U \in \mathcal{T}$, there is a $B \in \mathcal{B}$ such that $x \in B \subseteq U$.

Proposition

Let $\mathcal{B}$ be a basis for a topology $\mathcal{T}$ on a set $X$. Then a subset $U \subseteq X$ is open if and only if for each $x \in U \exists B \in \mathcal{B} | x \in B \subseteq U$.

How do we check whether two bases define the same topology?

Proposition

Let $\mathcal{B}_1$ and $\mathcal{B}_2$ be bases for topologies $\mathcal{T}_1$ and $\mathcal{T}_2$, respectively, on a non-empty set $X$. Then $\mathcal{T}_1=\mathcal{T}_2$ if and only if

for each $B \in \mathcal{B}_1$ and each $x \in B$, there exists a $B' \in \mathcal{B}_2$ such that $x \in B' \subseteq B$, and
for each $B \in \mathcal{B}_2$ and each $x \in B$, there exists a $B' \in \mathcal{B}_1$ such that $x \in B' \subseteq B$.

Example

The set of all “open equilateral triangles” with base parallel to the X-axis is a basis for the euclidean topology on $\mathbb{R}^2$.

The set of all open disks forms a basis for the euclidean topology on $\mathbb{R}^2$.

Limit Points¶

On real line, we usually take advantage of the notion of “closeness” in the form of distance to compute limits of sequences.
In a general topological space we don’t have a “distance function”.
We define the notion of limit point without resorting to distances.
We will also introduce the notion of connectedness.
In $\mathbb{R}$, while the sets $[0,1]\cup[2,3]$ and $[4,6]$ both have length 2, but they are different in the sense of connectedness.

Limit Points and Closure¶

If $(X, \mathcal{T})$ is a topological space then it is usual to refer to the elements of the set $X$ as points.

Definition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. A point $x \in X$ is said to be a limit point (or accumulation point or cluster point) of A if every open set, $U$ containing $x$ contains a point of $A$ different from $x$.

Example

$X = \{a,b,c,d,e\}$
$\mathcal{T} = \{X, \phi, \{a\},\{c,d\},\{a,c,d\}, \{b,c,d,e\}\}$
$A = \{a,b,c\}$
Note that $A$ is neither an open set nor a closed set.
$b, d, e$ are limit points of $A$.
$a,c$ are not limit points of $A$.
The limit point need not belong to $A$. $d,e \notin A$.
Every point in $A$, need not be a limit point. $a,c\in A$ but they are not limit points.

Example

Let $(X, \mathcal{T})$ be a discrete space and $A \subseteq X$.
$A$ has no limit points since for each $x \in X$, we have the singleton set $\{x\} \in \mathcal{T}$ containing no point of $A$ different from $x$.

Example

Consider the subset $A = [a,b) \subseteq \mathbb{R}$.
Every element in $[a,b)$ is a limit point of $A$.
The point $b$ is also a limit point of $A$.

Example

A singleton set has no limit points.

How do we test whether a set is closed?

Proposition

Let $A$ be a subset of a topological space $(X,\mathcal{T})$. Then $A$ is closed in $(X,\mathcal{T})$ if and only if $A$ contains all of its limit points.

Example

The set $[a,b)$ is not closed in $\mathbb{R}$, since $b$ is a limit point and $b \notin [a,b)$.
The set $[a,b]$ is closed in $\mathbb{R}$, since all limit points belong to the set itself.
The set $(a,b)$ is not closed in $\mathbb{R}$, since $a$ is a limit point and $a \notin (a,b)$.
$[a,\infty)$ is a closed subset of $\mathbb{R}$.

Proposition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$ and $A'$ the set of all limit points of $A$. Then $A \cup A'$ is a closed set.

Definition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. Then the set $A \cup A'$ consisting of $A$ and all its limit points is called the closure of $A$ and is denoted by $\overline{A}$.

Example

$X = \{a,b,c,d,e\}$
$\mathcal{T} = \{X,\phi, \{a\}, \{c,d\}, \{a,c,d\} , \{b,c,d,e\} \}$
The only limit point of $\{b\}$ is $e$
$\overline{\{b\}} = \{b,e\}$.
The limit points of $\{a,c\}$ are $b,d,e$
Thus $\overline{\{a,c\}} = X$.

Remark

Every closed set containing $A$ must also contain the set $A'$. So $A \cup A' = \overline{A}$ is the smallest closed set containing $A$. This implies that $\overline{A}$ is the intersection of all closed sets containing $A$.

Example

$\overline{\mathbb{Q}} = \mathbb{R}$.

Definition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. Then $A$ is said to be dense in $X$ or everywhere dense in $X$ if $\overline{A} = X$.

Example

Let $(X, \mathcal{T})$ be a discrete space. Then the only dense subset of $X$ is $X$ itself.
Each subset is its own closure since every subset is both open and closed.

Proposition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. Then $A$ is dense in $X$ if and only if every non-empty open subset of $X$ intersects $A$ non-trivially (i.e. if $U \in \mathcal{T}, U \neq \phi$, then $A \cap U \neq \phi$)

Let $S$ and $T$ be non-empty subsets of a topological space $(X,\mathcal{T})$ with $S \subseteq T$.

If $p$ is a limit point of the set $S$, then $p$ is also a limit point of the set $T$.
Thus $\overline{S} \subseteq \overline{T}$.
If $S$ is dense in $X$, then $T$ is dense in $X$ too.

Neighborhoods¶

Definition

Let $(X, \mathcal{T})$ be a topological space, $N$ a subset of $X$ and $p$ a point in $N$. Then $N$ is said to be a neighborhood of the point $p$ if there exists an open set $U$ such that $p \in U \subseteq N$.

Example

The closed interval $[0,1]$ in $\mathbb{R}^2$ is a neighborhood of the point $\frac{1}{2}$ since $\frac{1}{2} \in (\frac{1}{4}, \frac{3}{4}) \subseteq [0,1]$.
The interval $(0,1]$ in $\mathbb{R}^2$ is a neighborhood of the point $\frac{1}{4}$ since $\frac{1}{4} \in (0, \frac{1}{2}) \subseteq (0,1]$. But $(0,1]$ is not a neighborhood of the point $1$.

Example

If $(X, \mathcal{T})$ is a topological space and $U \in \mathcal{T}$, then $U$ is a neighborhood of every point $p \in U$.
Every open interval $(a,b)$ is a neighborhood of every point it contains.
Let $N$ be a neighborhood of a point $p$. Then If $S$ is any subset of $X$ such that $N \subseteq S$, then $S$ is also a neighborhood of $p$.

Proposition

Let $A$ be a subset of a topological space $(X,\mathcal{T})$. A point $x \in X$ is a limit point of $A$ if and only if every neighborhood of $x$ contains a point of $A$ different from $x$.

Corollary

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. Then the set $A$ is closed if and only if for each $x \in X\setminus A$, there is a neighborhood $N$ of $x$ such that $N \subseteq X\setminus A$.

Corollary

Let $U$ be a subset of a topological space $(X,\mathcal{T})$. Then $U \in \mathcal{T}$ if and only if for each $x \in U$ there exists a neighborhood $N$ of $x$ such that $N \subseteq U$.

Corollary

Let $U$ be a subset of a topological space $(X,\mathcal{T})$. Then $U \in \mathcal{T}$ if and only if for each $x \in U$ there exists a $V \in \mathcal{T}$ such that $x \in V \subseteq U$.

A set is open if and only if it contains an open set about each of its points.

Definition

A topological space $(X,\mathcal{T})$ is said to be separable if it has a dense subset which is countable.

Example

$\mathbb{Q}$ is countable and a dense subset of $\mathbb{R}$. Hence $\mathbb{R}$ is separable.

Definition

Let $(X,\mathcal{T})$ be a topological space and $A$ any subset of $X$. The largest open set contained in $A$ is called the interior of $A$ and is denoted by $\text{Int}(A)$.

$\text{Int}([0,1]) = (0,1)$
$\text{Int}((3,4)) = (3,4)$
$\text{Int}({5}) = \phi$
If $A$ is open in $(X,\mathcal{T})$, then $Int(A) = A$

Connectedness¶

Let $S$ be any set of real numbers.

If there is an element $b \in S$ such that $x \leq b \forall x \in S$, then $b$ is called the greatest element of $S$.
If $S$ contains an element $a$ such that $a \leq x \forall x \in S$, then $a$ is called the least element of $S$.
A set $S$ of real numbers is called bounded above if there exists a real number $c$ such that $x \leq c \forall x \in S$, and $c$ is called an upper bound for $S$.
Similarly the terms bounded below and lower bound are defined.
A set which is bounded above and bounded below is called bounded.

Least Upper Bound Axiom

Let $S$ be a non-empty set of real numbers. If $S$ is bounded above, then it has a least upper bound.

The least upper bound, a.k.a. the supremum of $S$, denoted by $\sup(S)$ may or may not belong to $S$.
Any set of real numbers which is bounded below has a greatest lower bound which is also called the infimum and is denoted by $\inf(S)$.

Lemma

Let $S$ be a subset of $\mathbb{R}$ which is bounded above and let $p$ be the supremum of $S$. If $S$ is a closed subset of $\mathbb{R}$, then $p \in S$.

Proposition

Let $T$ be a clopen set of $\mathbb{R}$. Then either $T = \mathbb{R}$ or $T = \phi$.

Definition

Let $(X, \mathcal{T})$ be a topological space. Then it is said to be connected if the only clopen sets of $X$ are $X$ and $\phi$.

Proposition

The topological space $\mathbb{R}$ is connected.

Example

If $(X, \mathcal{T})$ is any discrete space with more than one element, then $(X, \mathcal{T})$ is not connected as each singleton set is clopen.
If $(X, \mathcal{T})$ is an indiscrete space, then it is connected as the only clopen sets are $X$ and $\phi$.

Remark

A topological space $(X, \mathcal{T})$ is not connected (that is disconnected) if and only if there are non-empty open sets $A$ and $B$ such that $A \cap B = \phi$ and $A \cup B = X$.

$\mathbb{R}^2$ and in general $\mathbb{R}^n$ are connected spaces.

Homeomorphisms¶

How do we identify that two topologies are equivalent?

Subspaces¶

Definition

Let $Y$ be a non-empty subset of a topological space $(X, \mathcal{T})$. The collection $\mathcal{T}_Y = \{O \cap Y : O \in \mathcal{T}\}$ of subsets of $Y$ is a topology on $Y$ called the subspace topology (or the relative topology or the induced topology). The topological space $(Y, \mathcal{T}_Y)$ is called to be a subspace of $(X,\mathcal{T})$.

Example

Let $X = \{a, b, c, d, e, f\}$
Let $\mathcal{T} = \{X, \phi, \{a\}, \{c,d\}, \{a,c,d\}, \{b,c,d,e,f\} \}$
And $Y = \{b,c,e\}$
Then the subspace topology on $Y$ is:

\[\mathcal{T}_Y = \{Y, \phi, \{c\}\}\]

Remark

Let $\mathcal{B}$ be a basis for the topology $\mathcal{T}$ on $X$. Let $Y$ be a subset of $X$. The the collection $\mathcal{B}_Y = \{ B \cap Y : B \in \mathcal{B} \}$ is a basis for the subspace topology $\mathcal{T}_Y$ on $Y$.

Example

Consider the subset $(1,2)$ of $\mathbb{R}$.
A basis for the induced topology on $(1,2)$ is the collection $\{(a,b) \cap (1,2) : a,b\in \mathbb{R}, a < b \}$; that is $\{ (a,b) : a, b \in \mathbb{R} , 1 \leq a < b \leq 2 \}$.

Example

Consider the subset $[1,2]$ of $\mathbb{R}$.
A basis for the induced topology on $[1,2]$ is the collection $\{(a,b) \cap [1,2] : a,b\in \mathbb{R}, a < b \}$; that is

\[\{(a,b): 1 \leq a < b \leq 2 \} \cup \{[1,b) : 1 < b \leq 2\} \cup \{ (a,2] : 1 \leq a < 2\} \cup \{ [1,2] \}\]
As we can see: some sets which are not open in $\mathbb{R}$ become open in the subspace topology.

Example

The topology induced on $\mathbb{Z}$ by the euclidean topology on $\mathbb{R}$ is the discrete topology.
Going forward whenever we refer to $(a,b), [a,b], [a,b), (-\infty, a), (-\infty, a], (a,\infty), [a, \infty)$ as topological spaces without explicitly stating the topology, we will mean the topology induced by the euclidean topology on $\mathbb{R}$.

Homeomorphisms¶

Example

$X = \{a,b,c,d,e\}$
$Y = \{g,h,i,j,k\}$
$\mathcal{T}_X = \{X,\phi, \{a\}, \{c,d\}, \{a,c,d\}, \{b,c,d,e\}\}$
$\mathcal{T}_Y = \{Y,\phi, \{g\}, \{i,j\}, \{g,i,j\}, \{h,i,j,k\}\}$
Intuitively, the two topologies look equivalent. The function:

\[\begin{split}&f : X \rightarrow Y \\ &f(a) = g, f(b) = h, f(c) = i, f(d) = j, f(e) = k\end{split}\]

provides the equivalence.

Definition

Let $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$ be topological spaces. Then they are said to be homeomorphic if there exists a function $f : X \rightarrow Y$ which has the following properties:

$f$ is one-one. $f(x_1) = f(x_2) \implies x_1 = x_2$.
$f$ is onto. $\forall y \in Y \exists x \in X | f(x) = y$.
$\forall U \in \mathcal{T}_2, \quad f^{-1} (U) \in \mathcal{T}_1$
$\forall V \in \mathcal{T}_1, \quad f(V) \in \mathcal{T}_2$

Further the map $f$ is said to be homeomorphism between $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$. We write $(X, \mathcal{T}_1) \cong (Y, \mathcal{T}_2)$.

Homeomorphism is a reflexive, symmetric, and transitive relation. Hence it is an equivalence relation.

Example

Every non empty open interval $(a,b)$ is homeomorphic to $(0,1)$.

\[f(x) = a(1-x) + bx\]

Every two non-empty open intervals $(a,b)$ and $(c,d)$ are homeomorphic.
$\mathbb{R}$ is homeomorphic to $(-1,1)$.

\[f(x) = \frac{x}{1 - |x|}\]

Thus every open interval $(a,b)$ is homeomorphic to $\mathbb{R}$.
It shows that length is not a topological property.
Similarly any two closed intervals $[a,b]$ and $[c,d]$ are homeomorphic.
Let $a, b \in \mathbb{R}$, then:

\[(-\infty,a] \cong (-\infty,b] \cong [a,\infty) \cong [b,\infty)\]

With $c,d,e,f \in \mathbb{R}$ and $c < d, e < f$, we have

\[[c,d) \cong [e,f) \cong (c,d] \cong (e,f]\]
$\mathbb{Z} \cong \mathbb{N}$
Any line in $\mathbb{R}^2$ given by $X = \{\langle x, y \rangle : y = mx + c\}$ is homeomorphic to $\mathbb{R}$.
Let $X_1$ and $X_2$ be the closed rectangular regions in $\mathbb{R}^2$ given by

\[\begin{split}&X_1 = \{ \langle x,y \rangle : |x| \leq a_1 , |y| \leq b_1 \} \\ &X_2 = \{ \langle x,y \rangle : |x| \leq a_2 , |y| \leq b_2 \}\end{split}\]

Then $X_1 \cong X_2$ w.r.t. their induced topologies
Similarly any two closed discs in $\mathbb{R}^2$ are homeomorphic.

Group of homeomorphisms

Let $(X,\mathcal{T})$ be any topological space and $G$ the set of all homeomorphisms of $X$ into itself. Then $G$ is a group under the operation of composition of functions.

Non-Homeomorphic Spaces¶

Proving that two topological spaces are not homeomorphic is often much harder as we have to show that no homeomorphism exists.

Example

We show that $(X, \mathcal{T}_1) = [0,2]$ is not homeomorphic to the subspace $(Y, \mathcal{T}_2) = [0,1] \cup [2,3]$.

$[0,1]$ and $[2,3]$ are clopen sets in $(Y, \mathcal{T}_2)$
Thus $(Y, \mathcal{T}_2)$ is not connected while $(X, \mathcal{T}_1)$ is connected.
If $X \cong Y$, w.r.t. a homeomorphism $f: (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ then there exists a clopen set $f^{-1}([0,1]) \in X$, a contradiction.
Hence $X \ncong Y$.

Proposition

Any topological space homeomorphic to a connected space is connected.

Properties preserved by homeomorphisms

Let $X \cong Y$, w.r.t. a homeomorphism $f: (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$

If one is a $T_0$-space, so is the other.
If one is a $T_1$-space, so is the other.
If one is a $T_2$-space or Hausdorff space, so is the other.
If one is a regular space, so is the other.
If one is a $T_3$-space, so is the other.
If one satisfies second axiom of countability, so does the other.
If one is a separable space, so is the other.
If one is connected, so is the other.
If one is a discrete space, so is the other.
If one is an indiscrete space, so is the other.
If one is a finite-closed topology, so is the other.
If one is a countable-closed topology, so is the other.
If one is countable so is the other.
If one is uncountable, so is the other.
If one is finite, so is the other with same cardinality.

We use above properties to verify if two topologies are homeomorphic or not.

Definition

A subset $S$ of $\mathbb{R}$ is said to be an interval if it has the following property: if $x \in S, z \in S$, and $y \in \mathbb{R}$ are such that $x < y < z$, then $y \in S$.

How is $(0,1) \ncong [0,1]$?

Remark

Let $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ be a homeomorphism. Let $a \in X$ so that $X \setminus \{a\}$ be a subspace of $X$ with an induced topology $\mathcal{T}_3$. Also $Y \setminus \{f(a)\}$ is a subspace of $Y$ with an induced topology $\mathcal{T}_4$. Then

\[(X\setminus \{a\}, \mathcal{T}_3) \cong (Y\setminus \{f(a)\}, \mathcal{T}_4)\]

Removing any element from an open interval makes it disconnected.
Removing the border element from a closed / semi-closed interval leaves it connected.

Corollary

If $a,b,c,d$ are real numbers with $a < b$ and $c < d$, then

$(a,b) \ncong [c,d)$
$(a,b) \ncong [c,d]$ and
$[a,b) \ncong [c,d]$

Definition

A property is said to be topological if it is preserved by homeomorphisms.

Continuous Mappings¶

In most branches of pure mathematics we study what in category theory are called “objects” and “arrows”.
In linear algebra the objects are vector spaces and the arrows are linear transformations.
In group theory, the objects are groups and the arrows are homomorphisms.
In set theory, the objects are sets and arrows are functions.
In topology, the objects are topological spaces. The arrows are continuous mappings.

Continuous Mappings¶

Motivation

A function $f: \mathbb{R} \rightarrow \mathbb{R}$ is called continuous if for each $a \in \mathbb{R}$ and each positive real number $\epsilon$, there exists a positive real number $\delta$ such that $|x - a| < \delta$ implies $|f(x) - f(a)| < \epsilon$.

We need to generalize this notion for arbitrary topological spaces without the notion of absolute value or subtraction.

Restating: $f: \mathbb{R} \rightarrow \mathbb{R}$ is continuous if and only if for each $a \in \mathbb{R}$ and each interval $(f(a) - \epsilon, f(a) + \epsilon)$ for $\epsilon > 0$, there exists $\delta > 0$ such that $f(x) \in (f(a) - \epsilon, f(a) + \epsilon)$ for all $x \in (a - \delta, a + \delta)$.

Lemma

Let $f$ be a function mapping $\mathbb{R}$ into itself. Then $f$ is continuous if and only if for each $a \in \mathbb{R}$ and each open set $U \ni f(a)$, there exists an open set $V$ containing $a$ such that $f(V) \subseteq U$.

Almost ready to generalize for topological spaces!

Lemma

Let $f$ be a mapping from a topological space $(X, \mathcal{T})$ into a topological space $(Y, \mathcal{T}')$. Then the following two conditions are equivalent:

for each $U \in \mathcal{T}', f^{-1}(U) \in \mathcal{T}$,
for each $a \in X$ and each $U \in \mathcal{T}'$ with $f(a) \in U$, there exists a $V \in \mathcal{T}$ such that $a \in V$ and $f(V) \subseteq U$.

$f: \mathbb{R} \rightarrow \mathbb{R}$ is continuous if and only if for each open subset $U$ of $\mathbb{R}$, $f^{-1}(U)$ is an open set.

Definition

Let $f$ be a mapping from a topological space $(X, \mathcal{T})$ into a topological space $(Y, \mathcal{T}')$. Then $f : (X, \mathcal{T}) \rightarrow (Y, \mathcal{T}')$ is said to be a continuous mapping if for each $U \in \mathcal{T}'$, $f^{-1}(U) \in \mathcal{T}$.

Example

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be given by $f(x) = c$ a constant. Let $U$ be any open set in $\mathbb{R}$. Clearly $f^{-1}(U) = \mathbb{R} \text{ if } c \in U$ and $\phi \text{ if } c \notin U$. In both cases, $f^{-1}(U)$ is open, hence $f$ is a continuous mapping.

Proposition

Let $f$ be a mapping of a topological space $(X, \mathcal{T})$ into a topological space $(Y, \mathcal{T}')$. Then $f$ is continuous if and only if for each $x \in X$ and each $U \in \mathcal{T}' | f(x) \in U$, there exists a $V \in \mathcal{T}$ such that $x \in V$ and $f(V) \subseteq U$.

Is continuity associative?

Proposition

Let $(X, \mathcal{T}_1)$, $(Y, \mathcal{T}_2)$ and $(Z, \mathcal{T}_3)$ be topological spaces. If $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ and $g : (Y, \mathcal{T}_2) \rightarrow (Z, \mathcal{T}_3)$ are continuous mappings, then the composition function $f \circ g : (X, \mathcal{T}_1)\rightarrow (Z, \mathcal{T}_3)$ is continuous.

The continuity can be described in terms of closed sets also.

Proposition

Let $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$ be topological spaces. Then $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ is continuous if and only if for every closed subset $S$ of $Y$, $f^{-1}(S)$ is a closed subset of $X$.

Are continuous mappings and homeomorphisms related?

Remark

If $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ is a homeomorphism then it is a continuous map. But every continous mapping doesn’t need to be a homeomorphism.

Which mappings are homeomorphisms?

Proposition

Let $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$ be topological spaces. Let $f$ be a function from $X$ into $Y$. Then $f$ is a homeomorphism if and only if

$f$ is continuous
$f$ is one-one and onto.
$f^{-1}$ is continuous.

What about subspaces? If $f$ is continuous on $X$ is it continuous on its subspaces too?

Proposition

Let $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$ be topological spaces. And $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ be a continuous mapping. Let $A$ be a subset of $X$ and let $\mathcal{T}_3$ be the induced topology on $A$. Further, let $g : (A, \mathcal{T}_3) \rightarrow (Y, \mathcal{T}_2)$ be a restriction of $f$ to $A$; that is, $g(x) = f(x) \quad \forall x \in A$. Then $g$ is continuous.

Definition

Let $\mathcal{T}_1$ and $\mathcal{T}_2$ be two topologies on $X$. Then $\mathcal{T}_1$ is said to be a finer topology than $\mathcal{T}_2$ (and $\mathcal{T}_2$ is said to be a coarser topology than $\mathcal{T}_1$) if $\mathcal{T}_1 \supseteq \mathcal{T}_2$.

Intermediate Value Theorem¶

Is continuity and connectivity related?

Proposition

Let $(X, \mathcal{T}_1)$ and $(Y, \mathcal{T}_2)$ be topological spaces and $f : (X, \mathcal{T}_1) \rightarrow (Y, \mathcal{T}_2)$ be surjective and continuous. If $(X, \mathcal{T}_1)$ is connected then $(Y, \mathcal{T}_2)$ is connected.

Any continuous image of a connected set is connected.
If $(X, \mathcal{T}_1)$ is connected and $(Y, \mathcal{T}_2)$ is disconnected, then there exists no mapping which is onto and continuous.
While there are infinite number of mappings from $\mathbb{R}$ onto $\mathbb{Q}$ or $\mathbb{Z}$, none of them are continuous.

But the notion of connectivity is too broad. Can we do something better?

Definition

A topological space $(X, \mathcal{T})$ is said to be path connected (or pathwise connected) if for each pair of distinct points $a,b \in X$ there exists a continuous mapping $f:[0,1] \rightarrow (X, \mathcal{T})$, such that $f(0) = a$ and $f(1) = b$. The mapping $f$ is said to be a path joining a to b.

Example

Every interval is path connected.
For each $n \geq 1, \mathbb{R}^n$ is path connected.

Proposition

Every path connected space is connected.

Not every connected space is path connected!

Example

Clearly $\mathbb{R}^2 \setminus \{\langle 0, 0 \rangle \}$ is path connected hence is connected. However, $\mathbb{R} \setminus \{a\}$ for any $a \in \mathbb{R}$ is disconnected. Hence $\mathbb{R} \ncong \mathbb{R}^2$.

Theorem

Weierstrass Intermediate Value Theorem Let $f: [a,b] \rightarrow \mathbb{R}$ be continuous and let $f(a) \neq f(b)$. Then for every number $p$ between $f(a)$ and $f(b)$ there is a point $c \in [a,b]$ such that $f(c) = p$.

Corollary

If $f: [a,b] \rightarrow \mathbb{R}$ is continuous and such that $f(a) > 0$ and $f(b) < 0$, then there exists an $x \in [a,b]$ such that $f(x) = 0$.

Corollary

Fixed Point Theorem Let $f$ be a continuous mapping of $[0,1]$ into $[0,1]$. Then there exists a $z \in [0,1]$ such that $f(z) = z$. The point $z$ is called a fixed point.

Metric Spaces¶

Most important class of topological spaces
Provide a rich source of examples
Most applications of topology to analysis are via metric spaces

Metric Spaces¶

Definition

Let $X$ be a non-empty set and $d$ a real-valued function defined on $X \times X$ such that for $a,b \in X$:

$d(a,b) \geq 0$ and $d(a,b) = 0 \iff a = b$;
$d(a,b) = d(b,a)$; and
$d(a,c) \leq d(a,b) + d(b,c)$, [the triangle inequality] $\forall a,b,c \in X$.

Then $d$ is said to be a metric on $X$, $(X,d)$ is called a metric space and $d(a,b)$ is referred to as the distance between $a$ and $b$.

Example

The function $d: \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}$ given by

\[d(a,b) = |a-b|, \quad a,b \in \mathbb{R}\]

is a metric on the set $\mathbb{R}$ known as the euclidean metric.
The function $d : \mathbb{R}^2 \times \mathbb{R}^2 \mapsto \mathbb{R}$ given by

\[d( \langle a_1, b_1 \rangle, \langle a_2,b_2 \rangle ) = \sqrt{ (a_1 - b_1)^2 + (a_2 - b_2)^2}\]

is a metric on $\mathbb{R}^2$.
Let $X$ be a non-empty set and $d$ the function from $X\times X$ into $\mathbb{R}$ defined by

\[\begin{split}d(a,b) = \left\{ \begin{array}{ll} 0 & \mbox{if $a = b$}\\ 1 & \mbox{if $a \neq b$} \end{array} \right.\end{split}\]

Then $d$ is a metric on $X$ and is called the discrete metric.

Function Spaces¶

Let $C[0,1]$ denote the set of continuous functions from $[0,1]$ into $\mathbb{R}$. A metric is defined on this set by

\[d(f,g) = \int_0^1 |f(x) - g(x)| dx\]

where $f,g$ are in $C[0,1]$.

$d(f,g)$ is precisely the area of the region which lies between the graphs of functions.
Now, Another metric is defined on $C[0,1]$ as follows:

\[d^*(f,g) = \text{sup}\{|f(x) - g(x)| : x \in [0,1] \}\]

Clearly $d^*(f,g)$ is just the largest vertical gap between the graphs of functions $f$ and $g$.
More metrics on $\mathbb{R}^2$:

\[\begin{split}&d( \langle a_1, b_1 \rangle, \langle a_2,b_2 \rangle ) = \max\{ |a_1 - b_1 | , | a_2 - b_2 | \}\\ &d( \langle a_1, b_1 \rangle, \langle a_2,b_2 \rangle ) = |a_1 - b_1 | + | a_2 - b_2 |\end{split}\]

Normed vector spaces¶

Let $V$ be a vector space over the field of real or complex numbers. A norm $\parallel \text{ } \parallel$ on $V$ is a map $V \mapsto \mathbb{R}$ such that for all $a,b \in V$ and $\alpha$ in the field:

$\parallel a \parallel \geq 0$ and $\parallel a \parallel = 0 \iff a = 0$,
$\parallel a + b \parallel \leq \parallel a \parallel + \parallel b \parallel$, and
$\parallel \alpha a \parallel = |\alpha | \parallel a \parallel$.

A normed vector space is a vector space with a norm.

Let $(V, \parallel \parallel)$ be any normed vector space. Then there is a corresponding metric, $d$, on the set $V$ given by $d(a,b) = \parallel a - b \parallel \quad \forall a,b \in V$.

Metric Spaces as Topological Spaces¶

Open balls

In a normed vector space, the open ball with center a and radius r is defined to be the set

\[B_r(a) = \{x : x \in V | \parallel x - a \parallel < r\}\]

Why not generalize?

Definition

Let $(X,d)$ be a metric space and $r$ any positive real number. Then the open ball about $a \in X$ of radius $r$ is the set

\[B_r(a) = \{x : x \in X | d(a,x) < r\}\]

Example

The shape of the open ball depends on the choice of metric.

$\mathbb{R}^2$ with euclidean metric

$d^*( \langle a_1, b_1 \rangle, \langle a_2,b_2 \rangle ) = \max\{ |a_1 - b_1 | , | a_2 - b_2 | \}$

$d_1( \langle a_1, b_1 \rangle, \langle a_2,b_2 \rangle ) = |a_1 - b_1 | + | a_2 - b_2 |$

What happens in the intersection of open balls?

Lemma

Let $(X,d)$ be a metric space and $a$ and $b$ points of $X$. Further let $\delta_1$ and $\delta_2$ be positive real numbers. If $c \in B_{\delta_1}(a) \cap B_{\delta_2}(b)$, then there exists a $\delta > 0$ such that $B_{\delta}(c) \subseteq B_{\delta_1}(a) \cap B_{\delta_2}(b)$

Do open balls look like open sets?

Corollary

Let $(X,d)$ be a metric space and $B_1$ and $B_2$ open balls in $(X, d)$. then $B_1 \cap B_2$ is union of open balls in $(X,d)$.

So we do have a basis!

Proposition

Let $(X,d)$ be a metric space. Then the collection of open balls in $(X,d)$ is a basis for a topology $\mathcal{T}$ on $X$.

$\mathcal{T}$ is referred to as the topology induced by metric d.

$(X, \mathcal{T})$ is called the induced topological space or the corresponding topological space or the associated topological space.

Example

If $d$ is the discrete metric on a set $X$, then for each $x \in X, B_{\frac{1}{2}}(x) = \{x\}$. So all singleton sets are open in topology $\mathcal{T}$ induced on $X$ by $d$. Thus $\mathcal{T}$ is the discrete topology.
The euclidean metric on $\mathbb{R}$ induces the euclidean topology on $\mathbb{R}$. Ditto for $\mathbb{R}^2$.
But the other metrics $d^*$ and $d_1$ also induce euclidean topology on $\mathbb{R}^2$.

Different metrics can induce same topology!

Definition

Metrics on a set $X$ are said to be equivalent if they induce the same topology on $X$.

So whats the relation between open balls and open sets?

Proposition

Let $(X, d)$ be a metric space and $\mathcal{T}$ the topology induced on $X$ by the metric $d$. Then a subset $U$ of $X$ is open in $(X, \mathcal{T})$ if and only if for each $x \in U$ there exists an $\epsilon > 0$ such that the open ball $B_{\epsilon}(a) \subseteq U$

Is every topology induced by a metric?

Metrizable Spaces¶

Definition

A topological space $(X, \mathcal{T})$ is said to be a Hausdorff space or a $T_2$-space if for each pair of distinct points $a$ and $b$ in $X$, there exist open sets $U$ and $V$ such that $a\in U, b\in V$, and $U\cap V = \phi$.

Proposition

Let $(X, d)$ be any metric space and $\mathcal{T}$ the topology induced on $X$ by $d$. Then $(X, \mathcal{T})$ is a Hausdorff space.

Any set with 2 or more elements which has the indiscrete topology is not a Hausdorff space.
$\mathbb{Z}$ with finite closed topology is not a Hausdorff space.

Definition

A space $(X, \mathcal{T})$ is said to be metrizable if there exists a metric $d$ on the set $X$ with the property that $\mathcal{T}$ is the topology induced by $d$.

Warning

Every Hausdorff space is not metrizable. Though every metrizable space is a Hausdorff space.

Every subspace of a metrizable space is metrizable.

Bounded Metrics¶

Definition

A metric space $(X, d)$ is said to be bounded, and $d$ is said to be a bounded metric if there exists a positive real number $M$ such that $d(x,y) < M$, for all $x,y \in X$.

Every metric is equivalent to a bounded metric.

l_p spaces¶

Let $l_1$ be the set of all sequences of real numbers

\[x = (x_1,x_2, \dots, x_n, \dots)\]

with the property that the series $\sum_{n=1}^{\infty}|x_n|$ is convergent. If we define

\[d_1(x,y) = \sum_{n=1}^{\infty}|x_n - y_n| \quad \forall x, y \in l_1\]

Then $(l_1, d_1)$ is a metric space.
Let $l_2$ be the set of all sequences of real numbers

\[x = (x_1,x_2, \dots, x_n, \dots)\]

with the property that the series $\sum_{n=1}^{\infty}x_n^2$ is convergent. If we define

\[d_2(x,y) = (\sum_{n=1}^{\infty}|x_n - y_n|^2)^{\frac{1}{2}} \quad \forall x, y \in l_2\]

Then $(l_2, d_2)$ is a metric space.
Let $l_{\infty}$ be the set of bounded sequences of real numbers $x = (x_1,x_2, \dots, x_n, \dots)$. If we define

\[d_{\infty}(x,y) = \sup\{|x_n - y_n| : n \in \mathbb{N} \} \quad \forall x, y \in l_{\infty}\]

Then $(l_{\infty}, d_{\infty})$ is a metric space.
Each of the above spaces is a normed vector space in a natural way.

Normal Space¶

Definition

A topological space $(X, \mathcal{T})$ is said to be a normal space if for each pair of disjoint closed sets $A$ and $B$, there exist open sets $U$ and $V$ such that $A\subseteq U, B \subseteq V$ and $U\cap V = \phi$.

Every metrizable space is a normal space.

Definition

Let $(X,d_1)$ and $(Y, d_2)$ be metric spaces. Then $(X,d_1)$ is said to be isometric to $(Y,d_2)$ if there exists a surjective mapping $f : (X,d_1) \mapsto (Y,d_2)$ such that for all $x_1, x_2 \in X$

\[d_1(x_1, x_2) = d_2(f(x_1), f(x_2))\]

Such a mapping is called isometry.

Every isometry is a homeomorphism of the corresponding topological spaces.

Locally Euclidean¶

Definition

A topological space $(X, \mathcal{T})$ is said to be locally euclidean if there exists a positive integer $n$ such that each point $x \in X$ has an open neighborhood homeomorphic to an open ball about $0 \in \mathbb{R}^n$ with the euclidean metric.

Every non-trivial interval $(a,b) \in \mathbb{R}$ is locally euclidean.
The unit circle in complex plane is locally euclidean.
Every topological space homeomorphic to $\mathbb{R}^n$ is locally euclidean.

Manifold¶

Definition

A Hausdorff locally euclidean space is said to be a topological manifold.

There are many different kinds of manifolds (when more structure is imposed).

Differentiable manifolds
Smooth manifolds
Riemannian manifolds
Cauchy-Riemannian manifolds (CR-manifolds)

Convergence of Sequences¶

Definition

Let $(X,d)$ be a metric space and $x_1, \dots, x_n, \dots$ a sequence of points in $X$. Then the sequence is said to converge to $x \in X$ if given any $\epsilon > 0$, there exists an integer $n_0$ such that for all $n > n_0, d(x,x_n) < \epsilon$. This is denoted by $x_n \to x$.

The sequence $y_1, y_2, \dots, y_n, \dots$ of points in $(X, \mathcal{T})$ is said to be convergent if there exists a point $y \in X$ such that $y_n \to y$.

Convergence is unique!

Proposition

Let $x_1, x_2, \dots, x_n, \dots$ be a sequence of points in a metric space $(X, d)$. Further, let $x$ and $y$ be points in $(X,d)$ such that $x_n \to x$ and $x_n \to y$. Then $x = y$.

Convergence describes topology!

Proposition

Let $(X,d)$ be a metric space. A subset $A$ of $X$ is closed in $(X,d)$ if and only if every convergent sequence of points in $A$ converges to a point in $A$.

(In other words, $A$ is closed in $(X,d)$ if and only if $a_n \to x$, where $x \in X$ and $a_n \in A$ for all $n$, implies $x \in A$.)

Naturally convergence also describes continuous functions!

Proposition

Let $(X,d)$ and $(Y,d_1)$ be metric spaces and $f$ a mapping of $X$ into $Y$. Let $\mathbf{\tau}$ and $\mathbf{\tau}_1$ be the topologies determined by $d$ and $d_1$, respectively. Then $f : (X, \mathbf{\tau})\mapsto (Y, \mathbf{\tau}_1)$ is continuous if and only if $x_n \to x \implies f(x_n) \to f(x);$ i.e., if $x_1, x_2,\dots, x_n, \dots$ is a sequence of points in $(X,d)$ converging to $x$, then the sequence of points $f(x_1), f(x_2),\dots, f(x_n), \dots$ in $(Y, d_1)$ converges to $f(x)$.

Corollary

$f : (X, \mathbf{\tau})\mapsto (Y, \mathbf{\tau}_1)$ (as above) is continuous if and only if for each $x_0 \in X$ and $\epsilon > 0$, there exists a $\delta > 0$ such that $x \in X$ and $d(x,x_0) < \delta \implies d_1(f(x), f(x_0)) < \epsilon$.

distance between sets

Definition

Let A and B be non-empty sets in a metric space $(X,d)$. Define

\[\rho(A,B) = \inf\{d(a,b) : a \in A, b \in B\}\]

Then $\rho(A,B)$ is referred to as the distance between sets A and B.

Completeness¶

Definition

A sequence $x_1, x_2, \dots, x_n, \dots$ of points in a metric space $(X,d)$ is said to be a Cauchy sequence if given any real number $\epsilon > 0$, there exists a positive number $n_0$, such that for all integers $m > n_0, n > n_0$, we have $d(x_m, x_n) < \epsilon$.

Every convergent sequence is a Cauchy sequence.

Proposition

Let $(X,d)$ be a metric space and $x_1, x_2, \dots, x_n \dots$ a sequence of points in $(X,d)$. If there exists a point $a \in X$, such that the sequence converges to $a$, i.e. $x_n \to a$, then the sequence is a Cauchy sequence.

But every Cauchy sequence need not be convergent.

Example

Consider the open interval $(0,1)$ with the euclidean metric $d$.
It is clear that the sequence $0.1, 0.01, 0.001, 0.0001, \dots$ is a Cauchy sequence but it does not converge to any point in $(0,1)$.

Definition

A metric space is called to be complete if every Cauchy sequence in $(X,d)$ converges to a point in $(X,d)$.

Thus we see that $(0,1)$ with the euclidean metric is not a complete metric space.
If $X$ is any finite set and $d$ is the discrete metric on $X$, then $(X,d)$ is a complete metric space.
$\mathbb{R}$ with the euclidean metric is a complete metric space. How?
We will denote $x_1, x_2, \dots, x_n \dots$ by $\{x_n\}$.

Definition

If $\{x_n\}$ is any sequence, then the sequence $\{x_{n_1}, x_{n_2}, \dots\}$ is said to be a subsequence if $n_1 < n_2 < n_3 < \dots$.

Definitions

Let $\{x_n\}$ be a sequence in $\mathbb{R}$. Then it is said to be an increasing sequence if $x_n \leq x_{n+1} \quad\forall n \in \mathbb{N}$.

It is said to be a decreasing sequence if $x_n \geq x_{n+1} \quad\forall n \in \mathbb{N}$.

A sequence which is either increasing or decreasing is said to be a monotonic sequence.

Most sequences off course are neither increasing nor decreasing.

Definition

Let $\{x_n\}$ be a sequence in $\mathbb{R}$. Then $n_0 \in \mathbb{N}$ is said to be a peak point if $x_n \leq x_{n_0} \quad \forall n \geq n_0$.

Lemma

Let $\{x_n\}$ be a sequence in $\mathbb{R}$. Then $\{x_n\}$ has a monotonic subsequence.

If $\{x_n\}$ has infinite number of peak points, then the subsequence of peak points is a decreasing subsequence.
Otherwise there exists an integer $N$ such that there are no peak points for $n > N$. Choose any $n_1 > N$. We can find $n_2 > n_1 | x_{n_2} > x_{n_1}$ since $n_1$ is not a peak point. Similarly we can find $n_3 > n_2$. This way we can find an increasing sequence (by mathematical induction).

Proposition

Let $\{x_n\}$ be a monotonic sequence in $\mathbb{R}$ with the euclidean metric. Then $\{x_n\}$ converges to a point in $\mathbb{R}$ if and only if $\{x_n\}$ is bounded.

If $\{x_n\}$ is unbounded, then naturally it doesn’t converge.
Assuming $\{x_n\}$ as an increasing bounded sequence, there is a least upper bound $L$ of the the set $\{x_n\}, n \in \mathbb{N}$.
Thus $\forall \epsilon > 0, \exists N > 0 | d(x_N, L) < \epsilon$
Since $\{x_n\}$ is increasing, hence we have

\[L - \epsilon < x_n < L \quad \forall n > N.\]

(Bolzano-Weierstrass Theorem)

Every bounded sequence in $\mathbb{R}$ with euclidean metric has a convergent subsequence.

Corollary

The metric space $\mathbb{R}$ with the euclidean metric is a complete metric space.

We have to show that every Cauchy sequence converges in $\mathbb{R}$.
$\exists N > 0 | \forall m, n \geq N, d(x_n, x_m) < 1$.
$M = |x_1| + |x_2| + \dots + |x_N| + 1$ is an upper bound. Hence $\{x_n\}$ is bounded, hence has a convergent subsequence $\{x_{n_k}\}$ with $x_{n_k} \to a$.
Choose $\epsilon > 0$. Then $\exists N_0 > 0$ such that

\[|x_n - x_m| < \frac{\epsilon}{2}\quad \forall m,n \geq N_0.\]
Also $\exists N_1 > 0$ such that

\[|x_{n_k} - a| < \frac{\epsilon}{2}\quad \forall n_k \geq N_1.\]
Choose $N = \max(N_0, N_1)$. Then

\[|x_n - a| < \epsilon\quad \forall n \geq N.\]

Corollary

For each positive integer $m$, the metric space $\mathbb{R}^m$ with the euclidean metric is a complete metric space.

A normed vector space which is complete is called a Banach space.
An inner product space which is complete is called a Hilbert space.
The space $C[a,b]$ of continuous real valued functions on a closed and bounded interval is a Banach space, and so is a complete metric space w.r.t. the supremum norm.

Completeness and subspaces¶

Proposition

Let $(X,d)$ be a metric space, $Y$ a subset of $X$, and $d_1$ the metric induced on $Y$ by $d$.

If $(X,d)$ is a complete metric space and $Y$ is a closed subspace of $(X,d)$, then $(Y,d_1)$ is a complete metric space.
If $(Y,d_1)$ is a complete metric space, then $Y$ is a closed subspace of $(X,d)$.

$(0,1)$ is not complete while $[0,1]$ is complete.
$(0,1)$ is homeomorphic to $\mathbb{R}$. But $\mathbb{R}$ is complete while $(0,1)$ is not. Hence completeness is not a topological property (preserved by homeomorphism).

Definition

A topological space $(X, \mathcal{T})$ is said to be completely metrizable if there exists a metric $d$ on $X$ such that $\mathcal{T}$ is the topology on $X$ determined by $d$ and $(X,d)$ is a complete metric space.

Being completely metrizable is a topological property.
The topological spaces $\mathbb{R}$, $[a,b], (a,b), [a,b), (a,b]$, $(-\infty, a), (-\infty, a], (a, \infty), [a, \infty)$ and $\{a\}$ are all completely metrizable.
The space $\mathbb{P}$ of irrational numbers with the induced topology is completely metrizable.

Definition

A topological space is said to be separable if it has a countable dense subset.

Definition

A topological space is called Polish space if it is separable and completely metrizable.

$\mathbb{R}$ is a polish space, so is $\mathbb{R}^n$.

Definition

A topological space $(X,\mathcal{T})$ is said to be a Souslin space if it is Hausdorff and a continuous image of a Polish space. If $A$ is a subset of a topological space $(Y, \mathcal{T}_1)$ such that with the induced topology, the space $(A, \mathcal{T}_2)$ is a Souslin space, then $A$ is said to be an analytical set in $(Y, \mathcal{T}_1)$.

Every Polish space is a Souslin space since its a continuous image of itself and is a Hausdorff space (being a metric space).
Every Souslin space need not be metrizable.
Even a metrizable Souslin space is not necessarily a Polish space.
Analytic subsets of Polish spaces are closed under countable unions and intersections.
If the complement of an analytic set is analytic then the set is Borel.
Analytic sets are always Lebesgue measurable.
Topology > Metric Spaces > Measure Theory > Probability Theory

Metric space equivalence¶

Two topological spaces are equivalent if they are homeomorphic.
When are two metric spaces equivalent (as metric spaces)?

Definition

Let $(X,d)$ and $(Y,d_1)$ be metric spaces. Then $(X,d)$ is said to be isometric to $(Y,d_1)$ if there exists a surjective mapping $f : X \mapsto Y$ such that $\forall x_1, x_2 \in X, d(x_1, x_2) = d_1(f(x_1), f(x_2))$. Such a mapping is said to be an isometry.

The associated topological spaces of two isometric spaces are homeomorphic.

Definition

Let $(X,d)$ and $(Y,d_1)$ be metric spaces and $f$ a mapping of $X$ into $Y$. Let $Z = f(X)$, and $d_2$ be the metric induced on $Z$ by $d_1$. If $f:(X,d) \mapsto (Z, d_1)$ is an isometry, then $f$ is said to be an isometric embedding of $(X,d)$ in $(Y,d_1)$.

Natural embedding of $\mathbb{Q}$ with euclidean metric in $\mathbb{R}$ with euclidean metric is an isometric embedding.

Completion¶

Definition

Let $(X,d)$ and $(Y,d_1)$ be metric spaces and $f$ a mapping of $X$ into $Y$. If $(Y,d_1)$ is a complete metric space, $f$ is an isometric embedding and $f(X)$ is a dense subset of $Y$ in the associated topological space, then $(Y,d_1)$ is said to be a completion of $(X,d)$.

$\mathbb{R}$ is a completion of $\mathbb{Q}$ and $\mathbb{P}$.
Does every metric space has a completion?
Is the completion of a metric space unique in some sense?

Proposition

Let $(X,d)$ be a metric space. Then $(X,d)$ has a completion.

Two Cauchy sequences $\{y_n\}$ and $\{z_n\}$ are equivalent if $d(x_n, y_n) \to 0$ in $\mathbb{R}$.
This is an equivalence relation.
Let $\widetilde{X}$ be the set of all equivalence classes of Cauchy sequences.
Let $\tilde{y}$ and $\tilde{z}$ be two points in $\widetilde{X}$.
Let $\{y_n\} \in \tilde{y}$ and $\{z_n\} \in \tilde{z}$.
The sequence $d(y_n, z_n)$ is a Cauchy sequence in $\mathbb{R}$; converges to say $d_1(\tilde{y}, \tilde{z})$.
For each $x \in X$, the sequence $x,x,x,\dots$ is a Cauchy sequence which converges to $x$.
Let $\tilde{x}$ denote the equivalence class of all Cauchy sequences converging to $x \in X$.
Define $Y = \{\tilde{x} | x \in X\}$ as $Y \subseteq \widetilde{X}$.
Let $d_2$ be metric induced on $Y$ by $d_1$.
$f : (X,d) \mapsto (Y, d_2)$ with $f(x) = \tilde{x}$ is an isometry.
We can show that $Y$ is dense in $\widetilde{X}$.
We can show that $(\widetilde{X}, d_1)$ is a complete metric space.

Can an isometry over a subset help find an isometry over the containing spaces?

Proposition

Let $(A, d_1)$ and $(B, d_2)$ be two complete metric spaces. Let $X$ be a subset of $(A, d_1)$ with induced metric $d_3$ and $Y$ be a subset of $(B, d_2)$ with induced metric $d_4$ . Further let $X$ be dense in $(A, d_1)$ and $Y$ dense in $(B, d_2)$.

If there is an isometry $f : (X,d_3) \mapsto (Y, d_4)$, then there exists an isometry $g : (A, d_1) \mapsto (B, d_2)$, such that $g(x) = f(x) \forall x \in X$.

Proof outline

For every $a \in A \quad \exists x_n \to a | x_n \in X$ and $f(x_n) \to b | b \in B$
Define $g(a) = b \forall a \in A$.
Show that $g$ so defined is a well defined map.
Show that $g$ is one-one and onto.
Show that $g$ preserves distances hence is an isometry.

Further

A metric space may have several completions but they are isometric to each other.
So completion of a metric space is unique subject to isometries

Banach spaces¶

Definition

Let $(N, \| \|)$ be a normed vector space and $d$ the associated metric on the set $N$. Then $(N, \| \|)$ is said to be a Banach space if $(N,d)$ is a complete metric space.

Every normed vector space has a completion.
This completion is also a normed vector space.
So this completion is a Banach space.

Contraction mappings¶

Quite specific to metric spaces rather than general topology.

Definition

Let $f : X \to X$ be a mapping of a set $X$ into itself. Then a point $x \in X$ is said to be a fixed point of $f$ if $f(x) = x$.

Definition

Let $(X,d)$ be a metric space and $f : X \to X$ a mapping of $X$ into itself. Then $f$ is said to be a contraction mapping if there exists an $r \in (0,1)$ such that $d(f(x_1), f(x_2)) \leq r\cdot d(x_1, x_2) \forall x_1,x_2 \in X$.

Proposition

Let $f$ be a contraction mapping over $(X,d)$. Then $f$ is a continuous mapping.

Theorem (Contraction mapping theorem or Banach fixed point theorem)

Let $(X,d)$ be a complete metric space and $f$ a contraction mapping on $(X,d)$ into itself. Then $f$ has precisely one fixed point.

Proof outline

We show that $x, f(x), f^2(x),\dots, f^n(x),\dots$ is a Cauchy sequence and $f^n(x) \to z \in X$.
We show that $f(z) = z$, hence is a fixed point.
We show that $z$ is unique.

Baire spaces¶

Theorem (Baire Category Theorem)

Let $(X,d)$ be a complete metric space. If $X_1, X_2,\dots, X_n,\dots$ is a sequence of open dense subsets of $X$, then the set $\cap_{i=1}^{\infty} X_i$ is also dense in $X$.

Definition

Let $(X, \mathcal{T})$ be any topological space and $A$ any subset of $X$. The largest open set contained in $A$ is said to be the interior of A and is denoted by $\text{int}(A)$

Definition

A subset $A$ of a topological space $(X,\mathcal{T})$ is said to be nowhere dense if the set $\overline{A}$ has empty interior.

Definition

The boundary of a set $A$ in $(X,\mathcal{T})$ is defined by $B = \overline{A} \cap \overline{X \setminus A}$

Boundary of a set is a closed set (its an intersection of two closed sets)
Boundary of an open ball $B_{r}(x) = \{ y \in X | d(y,x) < r\}$ is $\{y \in X | d(y,x) = r\}$.
Boundary of an open set $A$ can be given by $B = \overline{A} \cap {X \setminus A}$
Boundary of an open set is nowhere dense.
$\mathbb{Q}$ is not open and its boundary doesn’t have an empty interior.

Rephrasing the Baire Category Theorem

Corollary

Let $(X,d)$ be a complete metric space. If $X_1, X_2,\dots, X_n,\dots$ is a sequence of subsets of $X$, such that $X = \cup_{i=1}^{\infty}X_n$, then for at least one $n \in \mathbb{N}$, the set $\overline{X_n}$ has non empty interior, that is $X_n$ is not nowhere dense.

Definition

A topological space $(X,d)$ is said to be a Baire space if for every sequence $\{X_n\}$ of open dense subsets of $X$, the set $\cap_{i=1}^{\infty} X_i$ is also dense in $X$.

Corollary

Every completely metrizable space is a Baire space.

Above is a result in topology rather than a result in metric space theory.
There are Baire spaces which are not completely metrizable.
The topological space $\mathbb{Q}$ is not a Baire space and so is not completely metrizable.
It is easier to prove that $\mathbb{Q}$ is not a Baire space, than to prove that $\mathbb{Q}$ is not completely metrizable without this notion.

Definitions

Let $Y$ be a subset of a topological space $(X, \mathcal{T})$. If $Y$ is a union of a countable number of nowhere dense subsets of $X$, then $Y$ is said to be a set of the first category or meager in $(X,\mathcal{T})$. If $Y$ is not first category, it is said to be of second category in $(X,\mathcal{T})$.

Proposition

If $Y$ is a first category subset of a Baire space $(X, \mathcal{T})$ then the interior of $Y$ is empty.

Corollary

If $Y$ is a first category subset of a Baire space $(X,\mathcal{T})$, then $X \setminus Y$ is a second category set.

$\mathbb{Q}$ is a first category subset of $\mathbb{R}$.
$\mathbb{P}$ is a second category subset of $\mathbb{R}$.

Definition

Let $S$ be a subset of a real vector space $V$. The set $S$ is said to be convex if for each $x,y \in S$ and every real number $0 < \lambda < 1$, the point $\lambda x + (1 - \lambda) y \in S$.

Every subspace of a real vector space is convex.
Every open ball and every closed ball in a normed real vector space is convex.

Definition

Let $(X,\mathcal{T})$ and $(Y,\mathcal{T}_1)$ be topological spaces. A mapping $f: (X,\mathcal{T}) \to (Y,\mathcal{T}_1)$ is said to be an open mapping if for every open subset $A$ of $(X,\mathcal{T})$, the set $f(A)$ is open in $(Y,\mathcal{T}_1)$.

Theorem (Open Mapping Theorem)

Let $(B, \| \|)$ and $(B_1, \| \|_1)$ be Banach spaces and $L : B \to B_1$ a continuous linear (in the vector space sense) mapping of $B$ onto $B_1$. Then $L$ is an open mapping.

Corollary

A one to one continuous linear map of one Banach space onto another Banach space is a homeomorphism. In particular, a one to one continuous linear map of a Banach space onto itself is a homeomorphism.

Compactness¶

Most important topological property
If we don’t understand compactness, we don’t understand topology
Compactness is topological generalization of finiteness

Compactness¶

Definition

Let $A$ be a subset of a topological space $(X, \mathcal{T})$. Then $A$ is said to be compact if for every set $I$ and every family of open sets, $\{O_i, i \in I | A \subseteq \cup_{i \in I}O_i\}$ there exists a finite subfamily $\{O_{i_1},O_{i_2},\dots, O_{i_n}\}$ such that $A \subseteq O_{i_1} \cup O_{i_2} \cup \dots \cup O_{i_n}$.

Example

If $(X, \mathcal{T}) = \mathbb{R}$ and $A = (0, \infty)$ then $A$ is not compact.
Let $(X, \mathcal{T})$ be a topological space and $A = \{x_1, x_2, \dots, x_n\}$ be any finite subset of $(X, \mathcal{T})$. Then $A$ is compact.

Remark

Every finite set in a topological space is compact. “Compactness” is a generalization of “finiteness”.

Example

A subset $A$ of a discrete space $(X, \mathcal{T})$ is compact if and only if it is finite.

Cover¶

Definitions

Let $I$ be a set and $O_i, i \in I$ a family of open sets in a topological space $(X, \mathcal{T})$. Let $A$ be a subset of $(X, \mathcal{T})$. Then $O_i, i \in I$ is said to be an open covering of $A$ if $A \subseteq \cup_{i \in I} O_i$. A finite subfamily, $O_{i_1}, O_{i_2}, \dots, O_{i_n}$ of $O_i, i \in I$ is said to be a finite subcovering (of $A$) if $A \subseteq O_{i_1} \cup O_{i_2} \cup \dots \cup O_{i_n}$.

Now we can rephrase compactness

Definition

A subset $A$ of a topological space $(X, \mathcal{T})$ is said to be compact if every open covering of $A$ has a finite subcovering. If the compact subset $A$ equals $X$, then $(X, \mathcal{T})$ is said to be a compact space.

Proposition

The closed interval $[0,1]$ is compact.

Heine-Borel Theorem¶

Proposition

Let $f: (X,\mathcal{T}) \to (Y,\mathcal{T}_1)$ be a continuous surjective map. If $(X,\mathcal{T})$ is compact then $(Y,\mathcal{T}_1)$ is compact.

Corollary

Let $(X,\mathcal{T})$ and $(Y,\mathcal{T}_1)$ be homeomorphic topological spaces. If $(X,\mathcal{T})$ is compact then $(Y,\mathcal{T}_1)$ is compact.

Corollary

For $a,b \in \mathbb{R}, a<b$, $[a,b]$ is compact while $(a,b)$ is not compact.

$[a,b]$ is homeomorphic to $[0,1]$ (a compact spacce).
$(a,b)$ is homeomorphic to $(0,\infty)$ (a non-compact space).

Proposition

Every closed subset of a compact space is compact.

Proposition

A compact subset of a Hausdorff topological space is closed.

Corollary

A compact subset of a metrizable space is closed.

$(a,b]$ and $[a,b)$ are not compact since they are not closed.

Proposition

A compact subset of $\mathbb{R}$ is bounded.

Theorem (Heine-Borel Theorem)

Every closed bounded subset of $\mathbb{R}$ is compact.

If $A$ is a closed and bounded subset of $\mathbb{R}$ then $A \subseteq [a,b]$ for some $a,b\in \mathbb{R}$.
$[a,b]$ is compact and $A$ is a closed subset of a compact set, hence compact.

Proposition (Converse of Heine-Borel Theorem)

Every compact subset of $\mathbb{R}$ is closed and bounded.

Metric spaces¶

Definition

A subset $A$ of a metric space $(X,d)$ is said to be bounded if there exists a real number $r$ such that $d(a_1, a_2) \leq r \forall a_1, a_2 \in A$.

Proposition

Let $A$ be a compact subset of a metric space $(X,d)$. Then $A$ is closed and bounded.

Theorem (Generalized Heine-Borel theorem)

A subset of $\mathbb{R}^n$ is compact if and only if it is closed and bounded.

Proposition

Let $(X,\mathcal{T})$ be a compact space and $f$ a continuous mapping from $(X,\mathcal{T})$ into $\mathbb{R}$. Then the set $f(X)$ has a greatest element and a least element.

Proposition

Let $a, b \in \mathbb{R}$ and $f$ a continuous function from $[a,b]$ into $\mathbb{R}$. Then $f([a,b]) =[c,d]$ for some $c, d \in \mathbb{R}$.

Finite Products¶

How do we create new topological spaces from old ones?

Subspaces
Quotient spaces
product spaces

The product topology¶

Given topological spaces $(X_1, \mathcal{T}_1), (X_2, \mathcal{T}_2), \dots, (X_n, \mathcal{T}_n)$ how do we define a reasonable topology $\mathcal{T}$ on the product set $X_1 \times X_2 \times \dots \times X_n$?

Notes¶

Online examples¶

Result

Let $X$ be an infinite set and $\mathrm{T}$ a topology on $X$. If every infinite subset of $X$ is in $\mathrm{T}$, prove that $\mathrm{T}$ is the discrete topology.

http://math.stackexchange.com/questions/60269/question-regarding-subsets-of-infinite-sets

Result

Show that all open intervals (a,b) in $\mathbb{R}$ are $F_\sigma$ sets.

http://math.stackexchange.com/questions/179808/show-that-any-open-subsets-of-the-real-line-are-f-sigma-sets

Proof of Baire Category Theorem

References¶

Sketches of topology

Geometry¶

Calculus on Euclidean Space¶

Euclidean Space¶

Definition

Euclidean 3-space $\mathbf{R}^3$ is the set of all ordered triples of real numbers. Such a triple $\mathbf{p} = (p_1, p_2, p_3)$ is called a point of $\mathbf{R}^3$.

$\mathbf{R}^3$ is a vector space over the real numbers.

\[\begin{split}&\mathbf{p} = (p_1, p_2, p_3)\\ &\mathbf{q} = (q_1, q_2, q_3)\\ &\mathbf{p}+\mathbf{q} = (p_1 + q_1, p_2 +q_2, p_3 + q_3)\\ &a\mathbf{p} = (ap_1, ap_2, ap_3)\\ &\mathbf{0} = (0,0,0)\end{split}\]

Definition

Let $x,y,z$ be the real-valued functions on $\mathbf{R}^3$ such that for each point $\mathbf{p} = (p_1, p_2, p_3)$

\[\begin{split}x(\mathbf{p}) = p_1\\ y(\mathbf{p}) = p_2\\ z(\mathbf{p}) = p_3\\\end{split}\]

These functions $x,y,z$ are called the natural coordinate functions of $\mathbf{R}^3$.

We also write:

\[x_1 = x, \quad x_2 = y, \quad x_3 = z\]

We thus have:

\[\mathbf{p} = (p_1, p_2, p_3) = (x_1(\mathbf{p}), x_2(\mathbf{p}), x_3(\mathbf{p}))\]

Definition

A real-valued function $f$ on $\mathbf{R}^3$ is differentiable (or infinitely differentiable or smooth) provided all partial derivatives of $f$, of all orders, exist and are continuous.

$(f+g)(\mathbf{p}) = f(\mathbf{p}) + g(\mathbf{p})$
$(fg)(\mathbf{p}) = f(\mathbf{p})g(\mathbf{p})$
In the following all functions are assumed to be differentiable real valued functions unless stated otherwise.

Differentiation

Is always a local operation.
The domain of $f$ need not be $\mathbf{R}^3$. It needs to be only an open set of $\mathbf{R}^3$.

Appendix¶

wikipediaLevelOfMeasurement: Wikipedia: Level of measurement

HoffmanKunzLinAlg: Linear Algebra, Kenneth Hoffman, Ray Kunze, 2nd ed. 1970

wikipediaOutlineAlgebraicStructures: Wikipedia: Outline of algebraic structures
PineWikiAlgebraicStructures: Algebraic Structures : PineWiki

CookChebyshevPolynomials: Chebyshev Polynomials, John D. Cook, Feb 2008

ThinkStatsDowney: Think Stats, Probability and Statistics for Programmers, Allen B. Downey, Version 1.5.7, 2011

wikipediaCategoricalDistribution: Wikipedia: Categorical distribution

Donoho1989: Uncertainty principles and signal recovery, David L. Donoho, Philip B. Stark, SIAM 1989

ASPCourseSpring2007: Algebraic Signal Processing Theory Course (Spring 2007)

Haynes1998: A Primer on digital beamforming, Toby Haynes, Spectrum Signal Processing, March 1998

Indices and tables¶

Last Modified: $Id: index.rst 304 2013-04-04 10:15:51Z shailesh $

Element	Mapping	Inverse	Order
\(e\)	(1,2,3)	\(e\)	1
\(\phi\)	(2,1,3)	\(\phi\)	2
\(\psi\)	(2,3,1)	\(\psi^2\)	3
\(\phi\psi\)	(3,2,1)	\(\phi\psi\)	2
\(\psi\phi\)	(1,3,2)	\(\psi\phi\)	2
\(\psi^2\)	(3,1,2)	\(\psi\)	3

Mathematics for Signal Processing \(a^2 +b^2 = c^2\)¶

General Topics¶

Logic and Sets¶

Logic¶

Implication¶

Tautology¶

Contradiction¶

Implication contd.¶

Statements¶

Sets¶

Cardinality¶

Statements¶

Operations¶

Levels of measurement¶

Nominal scale¶

Categorical variables¶

Categorical distribution¶

Statistics¶

Ordinal scale¶

Statistics¶

Order isomorphism¶

Interval scale¶

Statistics¶

Ratio scale¶

Statistics¶

References¶

Convergence¶

Pointwise convergence¶

Uniform convergence¶

Almost everywhere convergence¶

Absolute convergence¶

Algebra¶

Algebraic structures¶

Introduction¶

Single binary operation algebraic structures¶

Magma¶

Semigroup¶

Monoid¶

Group¶

Abelian Group¶

Operations on algebras¶

Subalgebras¶

Homomorphism¶

Two operation algebraic structures¶

Linear Algebra¶

Introduction¶

References¶

Hitch hiker’s guide¶

Defining a vector space¶

Linear Equations¶

Vector Spaces¶

Vector Spaces¶

Subspaces¶

Bases and dimensions¶

Coordinates¶

Summary of row-equivalence¶

Computations concerning subspaces¶

Linear Transformations¶

Polynomials¶

Determinants¶

Elementary Canonical Forms¶

Rational Jordan Forms¶

Inner Product Spaces¶

Operators on Inner Product Spaces¶

Bilinear Forms¶

Explorations¶

Matrix Algebra¶

Introduction¶

Garden¶

Square Matrices¶

2x2 matrices¶

3x3 matrices¶

4x4 matrices¶

Special 2x2 matrices¶

Polynomials¶

Chebyshev polynomials¶

Cosines¶

Chebyshev polynomials¶

Properties¶

Power form¶