The function composition of two bijections $f,g:X\to X$ is a bijection, with inverse function $(f\circ g{)}^{-1}=g^{-1}\circ f^{-1}$. Thus function composition is a binary operation on $\mathrm{Sym}(X)$. It is associative, since both $(f\circ g)\circ h$ and $f\circ (g\circ h)$ send $x$ to $f(g(h(x)))$.

The identity function ${\mathrm{id}}_X$ is a bijection and satisfies $f\circ {\mathrm{id}}_X={\mathrm{id}}_X\circ f=f$. Every bijection $f$ has an inverse function $f^{-1}:X\to X$, itself a bijection, satisfying $f\circ f^{-1}=f^{-1}\circ f={\mathrm{id}}_X$. These verify all group axioms, so $\mathrm{Sym}(X)$ is a group, the symmetric group of $X$.

If every $\Vert v_i\Vert =1$, then each diagonal entry of the Gram matrix is $A_{ii}=⟨v_i,v_i⟩=1$, so its matrix trace is $n$. Using iii and the permitted arithmetic-geometric mean inequality,The bound is attained by any orthonormal family, whose Gram matrix is the identity matrix.

By the spectral theorem for real symmetric matrices, there is an orthogonal matrix $Q$ such thatFor clarity, the diagonalization can also be justified recursively. The characteristic polynomial has a complex root of a polynomial by the fundamental theorem of algebra. By ii its eigenvalue is real; taking a nonzero real or imaginary part of an associated eigenvector in ${\mathbb{C}}^n$ gives a real eigenvector, which can be normalized. Its orthogonal complement is invariant, because $⟨Ax,z⟩=⟨x,Az⟩=\lambda ⟨x,z⟩=0$. Restriction to this linear subspace is again symmetric, and induction on dimension gives an orthonormal basis of eigenvectors.

All ${\lambda }_i\ge 0$ by ii. The permitted invariance of determinant and matrix trace under change of basis, applied to the diagonal matrix, yields

Symmetry of the real inner product gives $A^T=A$. Moreover, i with $y=x$ shows thatso the Gram matrix is a positive semidefinite matrix. To also check reality of every eigenvalue, allow a nonzero vector $z=a+ib\in {\mathbb{C}}^n$ with $Az=\lambda z$. Since $A$ is a real symmetric matrix,Here $z^{\ast }$ is the conjugate transpose, and $a^{T}Ab=b^{T}Aa$ cancels the imaginary part. Thusbecause $z^{\ast }z>0$. This proves both that every eigenvalue is real and that it is nonnegative.

Bilinearity of the real inner product gives, for the specified linear combinations,The last equality is the entrywise rule for matrix multiplication, with $x^T$ the transpose of the column vector $x$.

The two-vector Gram matrix isThe upper bound follows because the subtracted square is nonnegative. If either vector is zero, the determinant is zero. Otherwise apply the non-strict version of the calculation in i: $\Vert v_1-t{v}_2{\Vert }^2\ge 0$ with $t=⟨v_1,v_2⟩/\Vert v_2{\Vert }^2$ gives $⟨v_1,v_2{⟩}^2\le \Vert v_1{\Vert }^2\Vert v_2{\Vert }^2$. ThereforeEquality on the left holds exactly when the two vectors are linearly dependent; equality on the right holds exactly when they are orthogonal. The Gram determinant measures the squared area of their parallelogram: in the nonzero case, $\det A=\Vert v_2{\Vert }^2\Vert v_1-t{v}_2{\Vert }^2$, the square of base times perpendicular height.

The hypothesis implies $v_1,v_2\ne 0$, since the zero vector is a scalar multiple of every vector. SetSince $v_1$ is not a scalar multiple of $v_2$, $w\ne 0$. Positive definiteness and bilinearity of the real inner product giveMultiplying by $\Vert v_2{\Vert }^2>0$ and taking square roots proves the strict Cauchy-Schwarz inequalitySince every real number $s$ satisfies $s\le |s|$, this proves, in particular,The argument derives the required inequality directly from the inner product axioms.

Every $v\in V$ is a finitely supported sequence, so for a finite set of indices $S$,Thus $E$ is a spanning set. If $F$ contained $v\notin E$, the displayed expression would give a nontrivial relationamong the distinct vectors of the finite subset $\{v\}\cup \{e^{(i)}:i\in S\}$ of $F$: the coefficient of $v$ is $1$. This contradicts the linear independence of $F$. It also covers $v=0$, whose singleton is not linearly independent. Hence $F=E$. In particular, $E$ is both a basis and a maximal linearly independent subset of $V$.

Take any finite selection of distinct indices $i_1,\dots ,i_r$ and a relationThe coordinate at $i_j$ on the left is exactly ${\alpha }_j$, while the zero vector has coordinate zero. Hence ${\alpha }_j=0$ for each $j$. Every finite subset of $E$ is therefore linearly independent, which is the definition of linear independence for an infinite set. Thus $E$ is linearly independent in the vector space of finitely supported sequences.

Write $v={\sum }_{i=1}^{k+1}{\alpha }_i{u}_i$. Since $v\notin ⟨u_1,\dots ,u_k⟩$, necessarily ${\alpha }_{k+1}\ne 0$. Rearranging givesAll generators of $⟨u_1,\dots ,u_{k+1}⟩$ therefore belong to $⟨u_1,\dots ,u_k,v⟩$, proving one set inclusion. Conversely, $u_1,\dots ,u_k,v$ all belong to the linear subspace $⟨u_1,\dots ,u_{k+1}⟩$, proving the other set inclusion. ThusThis linear span exchange does not require linear independence of the original vectors.

Suppose ${\sum }_{i=1}^{k+1}{\alpha }_i{u}_i=0$. If ${\alpha }_{k+1}\ne 0$, thencontrary to the hypothesis. Hence ${\alpha }_{k+1}=0$. The assumed linear independence of $u_1,\dots ,u_k$ then gives ${\alpha }_1=\cdots ={\alpha }_k=0$. Therefore $u_1,\dots ,u_{k+1}$ are linearly independent. Adding a vector outside the previous linear span creates no nontrivial relation.

Put $U=⟨u_1,\dots ,u_k⟩$. Taking all coefficients zero puts the zero vector in $U$. If $s={\sum }_i{\alpha }_i{u}_i$, $t={\sum }_i{\beta }_i{u}_i$ lie in $U$ and $a,b\in \mathbb{R}$, thenThus $U$ is closed under vector addition and scalar multiplication, contains the zero vector, and is therefore a linear subspace of $V$. This is precisely why the linear span is a linear subspace.

Use the linear mapIt is well defined because $\mathrm{deg}(ap),\mathrm{deg}(bq)\le 2n-1$, and it is a linear map by distributivity of polynomial multiplication. If $\Phi (a,b)=0$ for a nonzero pair, ii would give a common root of a polynomial of $p$ and $q$. The hypothesis therefore implies $\ker \Phi =\{(0,0)\}$, so $\Phi$ is injective.

By i, the domain and codomain both have dimension $2n$: a basis of the domain is $(x^j,0),(0,x^j)$ for $0\le j<n$, and a basis of the codomain is $1,x,\dots ,x^{2n-1}$. The stated finite-dimensional result makes $\Phi$ surjective. In particular $1$ has a preimage, proving the degree bound in polynomial Bézout's identity:Indeed, injectivity also proves uniqueness of this pair under the stated degree of a polynomial bounds.

Suppose, for a contradiction, that $p$ and $q$ have no common root of a polynomial. Since the polynomial ring $\mathbb{C}[x]$ has no zero divisors and $p,q\ne 0$, the relation $ap+bq=0$ with $a,b$ not both zero forces both $a$ and $b$ to be nonzero.

By the fundamental theorem of algebra, writewhere the ${\alpha }_j$ are distinct. For each $j$, $q({\alpha }_j)\ne 0$. The equality $bq=-ap$ implies that $(x-{\alpha }_j{)}^{m_j}$ divides $bq$. The multiplicity of a root in polynomial multiplication is the sum of its multiplicities in the factors: factor out the largest powers of $x-{\alpha }_j$ and note that the two remaining factors have nonzero values at ${\alpha }_j$. Since $q({\alpha }_j)\ne 0$, $b$ must contain $(x-{\alpha }_j{)}^{m_j}$.

Thus $b$ has at least ${\sum }_j{m}_j=n$ roots of a polynomial counted with multiplicity of a root, so $\mathrm{deg}b\ge n$. This contradicts $b\in V_{n-1}$. ConsequentlyCounting multiplicity of a root is necessary: counting only distinct roots of a polynomial would miss repeated factors.

The monomials $1,x,\dots ,x^n$ form a basis of $V_n$: they span every polynomial of degree of a polynomial at most $n$, and equality of polynomials forces equality of every coefficient, proving linear independence. ThereforeThe zero polynomial is included in $V_n$ even though its degree of a polynomial need not be assigned an ordinary nonnegative value.

The transpose is a linear map, so $T(A)=A+A^T$ is a linear map on the $n^2$-dimensional vector space $M_{n\times n}(F)$. Let $E_{ij}$ denote a matrix unit. The answer depends on the characteristic of a field.

If $\mathrm{char}F\ne 2$, then $T(A)=0$ means $A^T=-A$. Such skew-symmetric matrices have zero diagonal, and their entries above the diagonal can be chosen freely. A basis of the kernel of a linear map is $E_{ij}-E_{ji}$ for $i<j$, giving nullity $n(n-1)/2$. The image of a linear map consists of all symmetric matrices: $T(A)$ is symmetric, and every symmetric matrix $S$ is $T(S/2)$. Its basis comprises $E_{ii}$ and $E_{ij}+E_{ji}$ for $i<j$, giving rank of a linear map $n(n+1)/2$.

If $\mathrm{char}F=2$, then $-A=A$, so $\ker T$ consists of all symmetric matrices, with dimension $n(n+1)/2$. Every $T(A)$ is symmetric with zero diagonal, and every symmetric zero-diagonal matrix $S$ arises by taking $A_{ij}=S_{ij}$ for $i<j$ and all other entries zero. The image of a linear map therefore has basis $E_{ij}+E_{ji}$ for $i<j$, and dimension $n(n-1)/2$. This is the symmetrization map in characteristic two.

In both cases the rank-nullity theorem is verified explicitly:

Over the finite field $F={\mathbb{Z}}_p$, a basis of the hyperplane has $n-1$ vectors by ii. Each vector on the hyperplane has a unique expression as a linear combination of that basis, and each coefficient has $p$ possibilities. ThusEquivalently, choose freely all coordinates except $x_j$, where $a_j\ne 0$, and solve uniquely for $x_j$. For $n=1$ this counts just the zero vector, consistently with $p^0=1$.

Define the linear functional $L:F^n\to F$ by $L(x)={\sum }_{i=1}^n{a}_i{x}_i$. The given hyperplane is $H=\ker L$. Choose $j$ with $a_j\ne 0$. For any $t\in F$, the vector whose only nonzero coordinate is $x_j=t/a_j$ satisfies $L(x)=t$. Hence $L$ is surjective and has rank of a linear map equal to ${\dim }_{F}F=1$.

Applying the rank-nullity theorem to this particular linear map givesThe nonzero-coefficient hypothesis is essential: if all $a_i$ were zero, the kernel of a linear map would instead be all of $F^n$.

The rank-nullity theorem for a linear map $T:V\to W$, with $V$ a finite-dimensional vector space over a field $F$, isHere the nullity is the dimension of the kernel of a linear map, and the rank of a linear map is the dimension of its image of a linear map.

Matrix similarity transports commuting operators: with $M=PD{P}^{-1}$,By ii, all such matrices are thereforeFor completeness, matrix multiplication givesThe parameterization is injective, since matrix multiplication by $P^{-1}$ and $P$ recovers the parameter diagonal matrix. Thus there are infinitely many choices. Already the distinct scalar matrices $t{I}_3$, $t\in \mathbb{R}$, give an infinite family.