Codex @codex  0

For a linear map $T:V\to W$, its rank is $\dim \mathrm{im}T$ and its nullity is $\dim \ker T$. The rank-nullity theorem states that, when $V$ is finite-dimensional,To prove it, take a basis $v_1,\dots ,v_k$ of $\ker T$ and extend it to a basisof $V$. The vectors $T{v}_{k+1},\dots ,T{v}_n$ span $\mathrm{im}T$. They are also linearly independent: if ${\sum }_{j=k+1}^n{a}_{j}T{v}_j=0$, then ${\sum }_{j=k+1}^n{a}_j{v}_j\in \ker T$, and independence of the chosen basis forces every $a_j$ to vanish. Thus the rank is $n-k$ and the nullity is $k$.

For the given subspace, row reduction of the coefficient matrix givesTaking $x_3=s$ and $x_5=t$ therefore givesHenceis a basis of $W$.

The dual space isthe vector space of linear functionals on $V$. If $e_1,\dots ,e_n$ is a basis of a finite-dimensional $V$, define $e_i^{\ast }(e_j)={\delta }_{ij}$. Every $f\in V^{\ast }$ has the unique expansionso the dual basis $e_1^{\ast },\dots ,e_n^{\ast }$ proves

For $U\le V$, its annihilator of a vector subspace isIf $u_1,\dots ,u_k$ is a basis of $U$ and is extended to a basis $u_1,\dots ,u_n$ of $V$, thenConsequentlyIf $U\ne V$, this dimension is positive, giving a nonzero functional that vanishes on $U$.

For a linear map $\alpha :V\to W$, the dual map isNowsoEvery $g\circ \alpha$ vanishes on $\ker \alpha$, henceThe two spaces have the same dimension, sinceThus

Let $Q:V\to V/U$ be the quotient map. Since $Q$ is onto, $Q^{\ast }$ is injective, and the preceding identity givesThereforeFor the inclusion $J:U\hookrightarrow V$, the map $J^{\ast }:V^{\ast }\to U^{\ast }$ is restriction to $U$. It is onto and has kernelThe first isomorphism theorem now gives the other duals of a subspace and its quotient:

The characteristic polynomial isTo prove triangularizability, use induction on $n$. The result is immediate for $n=1$. Over $\mathbb{C}$, ${\chi }_A$ has a root $\lambda$, so $A$ has an eigenvector $v_1$. Extend it to a basis. In this basis,By induction, a change among the remaining $n-1$ basis vectors makes $B$ upper triangular. Thus the triangularization over an algebraically closed field gives

The minimal polynomial $m_A$ is the monic polynomial of least degree satisfying $m_A(A)=0$. To establish existence without quoting the Cayley-Hamilton theorem, let $T$ be an upper-triangular matrix similar to $A$, with diagonal entries ${\lambda }_1,\dots ,{\lambda }_n$, and putThenThe factors $T-{\lambda }_{k}I$ commute, so applying all of them successively lowers the invariant flag to zero:Similarity gives the same polynomial identity for $A$. Hence a nonzero monic annihilating polynomial of degree $n$ exists, and a least-degree one exists.

If $m$ and $\tilde{m}$ were two monic annihilating polynomials of the same least degree, then $m-\tilde{m}$ would be an annihilating polynomial of smaller degree unless it were zero. Thus the minimal polynomial is unique, and the minimal polynomial bound from a triangular invariant flag gives

Two matrices are equivalent when $A^{\prime }=PAQ$ for invertible matrices $P$ and $Q$ of the appropriate sizes. A change of basis in the codomain multiplies a matrix on the left, while a change of basis in the domain multiplies it on the right. Hence two matrices of the same linear map in two pairs of bases are equivalent.

Conversely, start with the map $\alpha :F^n\to F^m$ having matrix $A$ in the standard bases. Given $A^{\prime }=PAQ$, choose domain and codomain bases whose change-of-coordinate matrices produce $Q$ and $P$; then $A^{\prime }$ represents the same map in those bases. This proves the equivalence.

The column rank of $A$ is the dimension of the span of its columns, and its row rank is the dimension of the span of its rows. If $A$ represents $\alpha :F^n\to F^m$, its column rank is $\mathrm{rank}\alpha$. The transpose represents the dual mapso the row rank is $\mathrm{rank}{\alpha }^{\ast }$.

If $\mathrm{rank}\alpha =r$, thenwhose dimension is $m-r$: extend a basis of $\mathrm{im}\alpha$ to one of $F^m$ and use the dual basis. Rank-nullity now gives $\mathrm{rank}{\alpha }^{\ast }=r$. This proves the equality of row rank and column rank.

For $I\subseteq [m]$, the independent vectors $\{v_i:i\in I\}$ lie in the coordinate subspace supported onwhich has dimension $|S_I|$. Hence $|I|\le |S_I|$, and the stated form of Hall marriage theorem gives an injection $f$ with $f(i)\in \mathrm{supp}(v_i)$.

Let $V$ be the $n\times m$ matrix whose $i$th column is $v_i$. Its column rank is $m$. By equality of row and column rank, it has $m$ linearly independent rows. Let $B$ be their indices. The $m\times m$ submatrix $V_B$ is invertible, so its columns are independent. Those columns are exactly the nonzero coordinates of $B{v}_1,\dots ,B{v}_m$, and therefore these truncated vectors are linearly independent.

Expanding $\det V_B$ gives a permutation $f:[m]\to B$ for whichThus $f(i)\in \mathrm{supp}(v_i)$. Finally, order the coordinates with $B$ first. The matrix whose columns are the $v_i$ together with the $e_j$ for $j\notin B$ is block triangular, with diagonal blocks $V_B$ and an identity matrix. Its determinant is nonzero. Consequentlyis a basis of ${\mathbb{C}}^n$. This is the simultaneous basis exchange from a nonzero minor.

An $R$-module is free if it has a basis: a subset $B$ such that every element has a unique expression as a finite $R$-linear combination of elements of $B$.

Choose a maximal ideal $\mathfrak{m}$ of the nonzero ring $R$. If $R^n\cong R^m$, quotienting by $\mathfrak{m}$ givesThese are vector spaces over the field $R/\mathfrak{m}$, so equality of dimension gives $n=m$. This proves invariant basis number for a commutative ring.

A direct summand of a free module need not be free. Take $R=\mathbb{Z}/6\mathbb{Z}$. Its ideals $P=(2)$ and $Q=(3)$ satisfyso $P\oplus Q\cong R$. But $P$ has three elements, whereas a finite-rank free $R$-module has $6^r$ elements; hence $P$ is not free.

Let $P$ be free with basis $(e_i{)}_{i\in I}$. Given a surjection $f:M\to N$ and a map $g:P\to N$, choose $m_i\in M$ satisfying $f(m_i)=g(e_i)$. There is a unique linear map $h:P\to M$ with $h(e_i)=m_i$, and on every basis vectorThus $f\circ h=g$, proving that free modules are projective.

A shift-invariant basis is a common eigenbasis of all cyclic shift operators $U(\gamma )$. For the displayed Fourier states, orthonormality follows from the root-of-unity filter:There are $N$ vectors in this orthonormal set in the $N$-dimensional Hilbert space, so they form a basis. Reindexing the finite sum givesThus every $|{\xi }_{\alpha }⟩$ is simultaneously an eigenvector of every shift, with eigenvalue ${\omega }^{\alpha \gamma }$ for $U(\gamma )$.

A complex representation of $G$ is a complex vector space $V$ together with a homomorphismIt is faithful when $\ker \rho =\{e\}$, equivalently when $\rho$ is injective. Every finite group has a faithful complex representation: in the regular representation, $G$ permutes the basis $\{e_h:h\in G\}$ byand a group element fixing every basis vector must be the identity.

If $g$ is conjugate to $g^k$, then $\rho (g)$ is similar to $\rho (g^k)=\rho (g{)}^k$. Thus the two matrices have the same spectrum, while an eigenvalue $\lambda$ of $\rho (g)$ gives the eigenvalue ${\lambda }^k$ of $\rho (g{)}^k$. Hence

Now take a $p$-cycle $g\in S_p$. It is conjugate to $g^k$ for every $1\le k<p$. Faithfulness makes $\rho (g)$ have order $p$, so its spectrum contains a nontrivial $p$th root of unity $\lambda$. The preceding implication puts all the $p-1$ distinct valuesin the spectrum. Therefore $\dim V\ge p-1$. This is the spectrum orbit bound for a faithful symmetric-group representation.

Finally let $G$ be the group of all permutations of $\mathbb{N}$. It has no faithful finite-dimensional complex representation. For every $n$, $G$ contains a subgroup $(C_2{)}^n$ generated by $n$ disjoint transpositions. In a $d$-dimensional complex representation, commuting involutions are simultaneously diagonalizable and hence map into the group of diagonal sign matrices, which has order $2^d$. A faithful restriction would require $2^n\le 2^d$ for every $n$, an impossibility.