Skip to content

Math

Definitions & Conceptions#

Wolfram MathWorld

easy definitions#

Statistics#
  • confidence interval A confidence interval means that if you take all possible samples of size n and compute their 95% confidence intervals, 95% of the intervals will include the population proportion, and only 5% of them will not.
Discrete / Graph theory#

Notes#

STAT#

A transition matrix $P=\begin{bmatrix} a & 1-a \ 1-b & b\end{bmatrix}$ has a stationary distribution $\pi=\begin{bmatrix} \frac{b-1}{a+b-2} & \frac{a-1}{a+b-2} \end{bmatrix}$, or $$\pi=\begin{bmatrix} \frac{b_{lose}}{a_{lose}+b_{lose}} & \frac{a_{lose}}{a_{lose}+b_{lose}} \end{bmatrix}$$ [Inspired by]( "Suppose that Peter and Paul alternate tossing a coin for which the probability of a head is three tenths and the probability of a tail is seven tenths. If they toss until someone gets a head, and Peter goes first, what is the probability that Peter wins?")

Terminology#

常用缩写#

ABBR meaning
WLOG without loss of generalcity
WLOG: without loss of generality Sin pérdida de generalidad
BWOC by way of contradiction
sps suppose

读音

written how to read
$N_O$ N-nought, n subscript zero, N-zero, N-null
$\aleph_0$ Aleph-nought, aleph-null

Math words#

Group English 中文
- parity 奇偶性
- Scientific notation 科学计数法
$b^{x}$ Exponential function 指数函数
$b^{x}$: $b$ base 底数 / 基数
$b^{x}$: $x$ index / exponent 指数
stationary distribution 平稳分布
coset 陪集/伴集/傍集

Idempotent matrix Morphism 态射

symbols#
Symbol English 中文
＋ plus 加号；正号
－ minus 减号；负号
± plus or minus 正负号
× is multiplied by 乘号
÷ is divided by 除号
＝ is equal to 等于号
≠ is not equal to 不等于号
≡ is equivalent to 全等于号
≌ is equal to or approximately equal to 等于或约等于号
≈ is approximately equal to 约等于号
＜ less than sign 小于号
＞ more than or greater than sign 大于号
≮ is not less than 不小于号
≯ is not more than 不大于号
≤ is less than or equal to 小于或等于号
≥ is more than or equal to 大于或等于号
％ per cent 百分之…
‰ per mill 千分之…
∞ infinity 无限大号
∝ varies as 与…成比例
√ (square) root 平方根
∵ since; because 因为
∴ hence 所以
∷ equals, as (proportion) 等于， 成比例
∠ angle 角
⌒ semicircle 半圆
⊙ circle 圆
○ circumference 圆周
△ triangle 三角形
⊥ perpendicular to 垂直于
∪ union of 并， 合集
∩ intersection of 交， 通集
∫ the integral of …的积分
∑ (sigma) summation of 总和
° degree 度
′ minute 分
″ second 秒
＃ number …号
℃ Celsius system 摄氏度
＠ at 在

advanced symbols#

Symbol Meaning
$\hookrightarrow$ “有钩箭头” 常用来标记一[包含映射]^1

set theory#

全序集 (Total order) total order, simple order, linear order, connex order, or full order A set paired with a total order is called a chain, a totally ordered set, a simply ordered set, a linearly ordered set, or a loset.

upper bound or majorant | bounded from above or majorized | bounded above lower bound or minorant | bounded from below or minorized | bounded below

Why is the set of all integers denoted by ℤ ? The notation Z came from the first letter of the German word Zahl, which means number. source

Cayley table = multiplication table for group. Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements

$A\subset B \iff A \cup B=B$

$e \in A \rightarrow e\in B \iff A \cup B=B$

包含映射 = 内含映射 = 自然映射。 常用字母 i 表示。

group theory#

some terms#

Chi Eng
同态基本定理 Fundamental theorem on homomorphisms
第一/二同构定理 Isomorphism theorems (Th A,B)
商群 Quotient group
单群 Simple group
单射 Injective function / injection
单射 surjective function / surjective
  • Free module: module that has a basis.

unclassified note.#

  • Symmetric group(对称群) is not Symmetry group(空间对称群)。
  • permutation group(置换群): subgroup of the symmetric group(对称群).
  • 陪集 = 伴集 = 傍集 是子集的等价类，eg: in $\mathbb{Z}/n$, $\bar{1}=1+\bar{0}=\bar{0}+1$ 左右陪集相同 $\iff$ 正规子群。
  • 同态的类型 同构（isomorphism）：就是双射的同态。两个对象称为同构的，如果存在相互间的同构映射。同构的对象就其上的结构而言是无法区分的。 满同态（epimorphism）：就是满射的同态。 单同态（monomorphism）：（有时也称扩张）是单射的同态。 双同态（bimorphism）：若 $f$ 既是满同态也是单同态，则称 f 为双同态。?和同构的区别? 自同态（endomorphism）：任何同态 $f : X \rightarrow X$ 称为 $X$ 上的一个自同态。 自同构（automorphism）：若一个自同态也是同构的，那么称之为自同构。

book 《抽象代数学》#

notes:#

If $G/K$ Abelian, $G'=[G:G]={aba^-b^-| a,b \in G} \subset K$.

Exercise#

2-3-2 All subgroup of $G$ is normal. Show that $G$ is Abelian.

BWOC, suppose that exist $g,h$ such that $gh\neq hg$. Note $G=, H=$. $G,H$ is subgroup so both are normal. Then by $gH=Hg, Gh=hG$, exist $m,n\in \mathbb{Z}$, such that $gh=h^m g, gh=h g^n$. This means $h^mg=gh=hg^n$, or $u:= h^{m-1}=g^{n-1}$. $gu=ug; hu=uh$. Here we can assume that $d:=\gcd(m-1,n-1)=1$, otherwise, WLOG, we set $u^d:= h^{m-1}=g^{n-1}$

So $gu=gh^{m-1}=ghh^{m-2}=(hg^n)h^{m-2}=(hgu)h^{m-2}=hgh^{m-2}u=h^2gh^{m-3}u^2=h^3gh^{m-4}u^3=\dots=h^{m-1}gh^{m-m}u^{m-1}=ugu^{m-1}=gu^m$.

This shows $u^{m-1}=e$

Similarly, $uh=g^{n-1}h=ug^{n-2}hg=u^{n-1}hg^{n-1}=u^nh$

$u^{m-1}=e=u^{n-1}, h^{(m-1)(n-1)}=g^{(m-1)(n-1)}=e$ > $u^d=e$, and by assumption, $d=1$. Hence $u=e$

So, $gh=hgu=hge=hg$. It contradicts $gh\neq hg$.

(7). $N$ is normal subgroup of a finite group $G$. $|N|$ and $|G|/|N|$ coprime. Show that $\forall x, x^{|N|}=e \implies x\in N$.

Let $t = |G|/|N|=|G/N| , n=|N|$, then $N=x^{lt}N, \forall l\in \mathbb{Z}$. Also $x^{mn}N=N, \forall l\in \mathbb{Z}$. This implies that $\exist l,m$ such that $x^N=x^{mn-lt}N=N$, since $gcd(n,t)=1$. QED.

(8). $N$ is normal subgroup of group $G$. $N \cap [G,G]={e}$. Show that $N \subseteq C$, center of $G$

Note $G'=[G,G], \forall n\in N, \forall g\in G, n\in N \iff gng^-\in N \iff ngn^-g^-=n(gn^-g^-)\in N. ngn^-g^-\in G' \iff ngn^-g^-=e\in N\cap G' \iff ng=gn \iff N \subseteq C.$

(10). $\exist p, \forall a,b \in G, (ab)^p=a^p b^p$. Denote $S:={x\in G| \exist m\in \mathbb{N}, x^{p^m} = e }$. Show that $S$ is normal, and $x^pS=S \rightarrow xS=S$.

$\forall g \in G, \forall s \in S, (gsg^-)^{p^m}=gs^{p^m}g^-=e \iff gsg^- \in S \iff S$ is normal.

$x^p S = S \iff x^p \in S \iff \exist m\in \mathbb{N}, {(x^p)}^{p^m} = e = x^{p\cdot p^m} = x^{p^{m+1}} \iff x\in S$.

(11). $|G|=120, H\subset G, |H|=24$. Show $\exist g\notin H, gH=Hg \rightarrow H \triangleleft G$.

Think about $F=\, H\subset F \subset G \iff 5|H|=|G|=k|F|=kl|H|, k,l\in \mathbb{Z}$. While $g \notin H \iff gH \neq H \implies |F|>|G| \implies |G|=|F|=5|H| \iff G=F \iff G=H\sqcup gH\sqcup g^2H\sqcup g^3H\sqcup g^4H \iff \forall x\notin H, \exist k\in {1,2,3,4}, h_1,h_2\in H, x=g^kh_1=h_2g^k \implies xH=g^kh_1H=g^kH=Hg^k=Hh_2g^k=Hx \iff \forall x \in G, xH=Hx \iff H$ is normal. QED.

2-4

(8). Show that $N$ is a maximal normal subgroup of $G \iff G/N$ is simple.

$N$ is normal subgroup.

$G/N$ is simple $\iff G/N$ has only trivial subgroups ${e},G/N \iff \nexists H/N \triangleleft G/N, {e} \subsetneq H \subsetneq G/N \iff \nexists H\triangleleft G, N\subsetneq H \subsetneq G$.

NOTE: Image of function/mapping and Quotient group are always related.

(9). $N,H$ are two maximal normal subgroups of $G$. Show that $H \cap N$ is a maximal normal subgroup of $H$.

$H \cap N$ is a maximal normal subgroup of $H \iff H/H\cap N\cong NH/N$ simple $\impliedby NH \subset G, G/N$ simple. $\iff N$ is maximal normal subgroup of $G$.

$\impliedby: NH=G$ for the maximality (being maximal).

(10). Let $\phi$ is an automorphism, $\phi(a)=a \leftrightarrow a=e$. Show that $\psi: a \mapsto \phi(a)a^{-1}$ is injective. If $G$ is finite, all element of $G$ has form $\phi(a)a^{-1}$.

$\psi$ is injective: $\psi(x)=\psi(y) \iff \phi(x)x^{-1}=\phi(y)y^{-1} \iff \phi(xy^-)=\phi(x)\phi(y^-)=xy^- \iff xy^-=e \iff x=y$.

This is equivalent to show that $\psi$ is surjective. $e=\phi(e)e^-. \forall a\neq e, a\neq \phi(a)a^-$. $\psi$ is injective $\implies |\psi(G)|=|G|$. $\psi$ is an automorphism. $\implies \psi(G) \subset G$. This means $G=\psi(G)$. So it is bijective hence a surjective.

(11). $G,\phi$ as in (10). $G$ is finite and $\phi^2=1$. Show that $|G|$ is odd and that $G$ is Abelian.

Define a relation $a \sim b \iff \phi(a)=b \vee a=b$. Then $a\sim a; a \sim b \implies a=\phi(\phi(a)) = \phi(b)\lor a=b; a\sim b,b\sim c \implies c=a \vee c=\phi(a) \vee c=\phi(\phi(a))=a \iff a\sim c.$ This means it is equivalence. Equivalence classes of $\sim$ on $G$, except ${e}$, have 2 elements. So $|G|$ is odd.

Since all elements of $G$ can be written as $\phi(a)a^-$ from conclusion of (10). $\forall g\in G, \exists a, g=\phi(a)a^- \implies g\phi(g)=\phi(a)a^- \phi(\phi(a))\phi(a^-)=\phi(a)a^- \phi(\phi(a))\phi(a^-)=\phi(a)a^- a\phi(a^-)=e$. Similarly, $\phi(g)g=e$. This means $\phi(g) = g^-$. We can get our objective by applying (7).

NOTE: to prove $\phi(g)=g^-$, we need to rewrite $g=\phi(a)a^-$.

(12). $G$ is finite and Abelian. $|G|=n, \gcd(m,n)=1.$ Show that $\phi: x\mapsto x^m$ is an automorphism of $G$.

$\phi(G) \subset G$ because $G$ is a group.

$\phi$ is injective. $x^m=y^m \implies \exist k,l : x=x^{km-ln}=y^{km-ln}=y.$ Injective $\implies |\phi(G)|=|G|$. Automorphism $\implies \phi(G) \subset G$. This means $G=\phi(G)$. So it is surjective, hence bijective.

(13). $G$ finite and $|G|>2$. $\exists a: a^2 \neq e.$ Show that $|Aut(G)|>1$.

$\exists a: a^2 \neq e.$ is not needed. If $|G|$ is prime, $G$ is cyclic group, $x \mapsto x^2$ is an automorphism. If $|G|$ composite, $G=\bigoplus\Z/n\Z$. If $n=2, \forall n$, we can mapping one generator to another. If not, $\exist n \neq 2 \implies \exists a: a^2 \neq e.$

Sylow 定理证明：#

取一个 所有 G 的 Sylow 群构成的集合 的 G-轨道，T。$r:=|T|$. 在该轨道中，取一 p-群 P， 群 P 对 T 对轨道分划中，有一个元素的轨道只有{P}，若有{Q}则 PQ=QP 是一个 p-群，与 P 是 sylow p-群 矛盾（其他轨道中的元素数均为 p 的 ~~倍数~~ 幂次 ）。 因此 $r\equiv 1(\mod p)$。 如果该集合有另一轨道，取另一轨道中的元素 P，对轨道 T 如上分划计数，则 r 是 p 对倍数，矛盾。因此只有一个轨道。

证明策略：

  • 证明是正规子群：正规化子=整个群。
  • 商群+归纳法。
  • $HN$ 封闭 $\iff HN=NH$.

Theory of Computation#

book: Introduction to the Theory of Computation

tools#

LaTeX typesetting in Mathematica http://szhorvat.net/pelican/latex-typesetting-in-mathematica.html