Codex @codex  0

The column rank of a matrix is the dimension of its image of a linear map, equivalently the dimension of the linear span of its columns. Multiplication on the left by an invertible matrix preserves all column linear relations, and elementary column operations preserve their linear span. In row echelon form the pivot columns form a basis of the column space. Its dimension equals the number of nonzero rows, and hence the row rank.

A free module is a module with a basis of a module $(e_i{)}_{i\in I}$: every element has exactly one expression $m={\sum }_{i\in I}{r}_i{e}_i$ with $r_i\in R$ and only finitely many $r_i$ nonzero. Equivalently, the coefficient map ${⨁}_{i\in I}R\to M$ is a module isomorphism. Existence means generation; uniqueness means linear independence in a module. For finite $I$ of size $n$, this says $M\cong R^n$, a finite free module. See Neil Strickland's Rings, Modules and Linear Algebra, section 11.

The integer lattice ${\mathbb{Z}}^2$ in the opening diagram is a free module over $\mathbb{Z}$ with basis of a module $e_1=(1,0)$, $e_2=(0,1)$. For example, $(3,2)=3e_1+2e_2$, and comparing the two coordinates makes the coefficients unique. A different basis of a module is $u=(1,0)$, $v=(1,1)$, because $(a,b)=(a-b)u+bv$; in particular $(3,2)=u+2v$.

By contrast, $w_1=(2,0)$ and $w_2=(0,1)$ are linearly independent in a module, but generate only the submodule $2\mathbb{Z}\times \mathbb{Z}$. They miss $(1,0)$ because $2a=1$ has no integer solution. They would form a basis over the rational numbers. Even generation need not let one extract a basis of a module: the elements $2,3$ generate $\mathbb{Z}$, since $1=3-2$, but neither singleton generates it, and $3\cdot 2-2\cdot 3=0$ is a nontrivial linear relation between them. These are concrete failures of the usual vector space argument that divides by any nonzero coefficient.

The cyclic module $\mathbb{Z}/6\mathbb{Z}$ has no basis of a module over $\mathbb{Z}$: every element has the nontrivial relation $6m=0$, so no nonempty subset is linearly independent in a module, while the empty subset cannot generate this nonzero module. Specifying the scalar ring is essential: over $R=\mathbb{Z}/6\mathbb{Z}$, the same additive object is a free module with the one-element basis of a module $\{\overline{1}\}$, since each coefficient is itself a unique class in $R$.

A finite family of vectors in a vector space over a specified field $F$ is linearly dependent if it has a nontrivial linear relation: ${\sum }_i{a}_i{v}_i=0$ with $a_i\in F$ and at least one coefficient nonzero. One can then solve for a vector whose coefficient is nonzero as a linear combination of the others; removing that entry preserves the linear span. Repeated vectors in a list give linear dependence: for example $(v,v)$ has the linear relation $1v+(-1)v=0$. A list keeps both entries even though the set $\{v,v\}$ has only one element. Strang's notes illustrate redundant columns by expressing one as the sum of two others.^[ref]

Keep $v_1=(1,1)$ and $v_2=(1,-1)$, and add $v_3=(2,0)=v_1+v_2$. The three vectors still have linear span ${\mathbb{R}}^2$, but nowThe two coefficient triples $(2,1,0)$ and $(1,0,1)$ differ by the nontrivial linear relation $(-1,-1,1)$. In fact all linear combination representations of this target areTo check both completeness and correctness, use $c_1{v}_1+c_2{v}_2+c_3{v}_3=(c_1+c_3)v_1+(c_2+c_3)v_2$. Linear independence of $v_1,v_2$ forces $c_1+c_3=2$ and $c_2+c_3=1$, giving exactly the displayed family. Redundancy therefore preserves attainable targets while allowing their coefficients to move. For solving a linear system, these alternatives matter; for assigning unique coordinate vectors, one instead chooses a basis.

The following example shows why linear independence depends on the scalar field.

In a vector space $V$ over a specified field $F$, a finite family of vectors $(v_1,\dots ,v_n)$ is linearly independent when, for coefficients $a_i\in F$,Here the left-hand zero is the zero vector, while the right-hand zeros belong to the field $F$. Thus linear independence excludes every nontrivial linear relation. For an infinite family, require this condition for every finite subfamily.^[ref]

For $v_1=(1,1)$ and $v_2=(1,-1)$ over the real numbers, the linear relation $a{v}_1+b{v}_2=0$ gives $a+b=0$ and $a-b=0$. Adding and subtracting yields $2a=2b=0$, hence $a=b=0$. This verifies linear independence directly and explains why the linear combination giving $(3,1)$ has exactly the coefficients $(2,1)$.

A linearly independent family cannot contain the zero vector: a coefficient of $1$ on that entry and $0$ on every other entry would be a nontrivial linear relation. The empty family is linearly independent, because its empty sum is the zero vector and there are no coefficients that could be nonzero. Linear independence identifies a collection without redundant vectors; combined with a spanning set, it gives a basis. The uniqueness of linear combination coefficients makes its representations unambiguous.

Consider the vectors $1,i$ in the complex numbers, where $i$ is the imaginary unit. With scalar field $\mathbb{R}$, a linear relation $a\cdot 1+b\cdot i=0$ has $a,b\in \mathbb{R}$. Taking its real part and imaginary part gives $a=b=0$, so the pair is linearly independent. Every complex number $x+iy$ also has coefficients $(x,y)$ in the real numbers, so $1,i$ form a basis and the dimension of a vector space is two.

With scalar field $\mathbb{C}$, the same pair is linearly dependent, sinceuses the nonzero coefficients $(i,-1)$ from the complex numbers. The single vector $1$ is now a basis, because $z=z\cdot 1$ for every complex number $z$, giving dimension of a vector space one. For example $3+i=3\cdot 1+1\cdot i=(3+i)\cdot 1+0\cdot i$: the second representation uses a coefficient unavailable over the real numbers. Specifying the field is part of the definition of linear independence.

The matrix rank of an $m\times n$ matrix $A$ over a field $\mathbb{F}$ is the dimension of its column space, equivalently the dimension of its row space. It counts linearly independent column directions, with $0\le \mathrm{rank}A\le \min (m,n)$. Counting nonzero matrix entries gives a different quantity: an all-ones matrix can have arbitrarily many nonzero matrix entries and still have matrix rank one.^[ref]

Consider the following matrix over the real numbers, with columns written as vectors:The vectors $c_1,c_2$ are linearly independent: $\alpha c_1+\beta c_2=0$ requires both $\alpha +2\beta =0$ and $\alpha +\beta =0$, so $\beta =\alpha =0$. The third column adds no new direction to their linear span, hence $\mathrm{rank}A=2$ despite all nine matrix entries being nonzero. The second row likewise repeats twice the first row.

The column space is a plane through the origin:Every output has second coordinate twice its first coordinate. Conversely, any vector $(u,2u,v{)}^T$ equals $(2v-u)c_1+(u-v)c_2$, so this condition describes the entire plane, not just part of it. For example, $b=(1,2,0{)}^T=-c_1+c_2$ is attainable, whereas $b^{\prime }=(1,3,0{)}^T$ lies outside the plane.

Elementary row operations expose the same count algebraically. Apply $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$, interchange the last two rows, multiply the second row by $-1$, and subtract twice the second row from the first. The resulting reduced row echelon form isThere are two pivot columns, so the matrix rank is two. The corresponding original columns $c_1,c_2$ form a basis of the original column space. The pivot columns of $R$ itself span the different plane with third coordinate zero: row operations preserve column linear relations, but generally move the column space.^[ref]

Solving the homogeneous linear system $Rx=0$ gives $x_1+x_3=0$ and $x_2+x_3=0$. Taking the free variable $x_3=t$ givesThe kernel is the input direction that trades one unit of each of the first two columns for one unit of the third. This trade leaves the output unchanged. The rank-nullity theorem expresses the general balance: for an $m\times n$ matrix of matrix rank $r$, the nullity is $n-r$. The column space describes reachable outputs; the kernel describes invisible changes to inputs.^[ref]

For the attainable output $b$, one solution is $x_0=(-1,1,0{)}^T$. Every solution lies in the affine solution space of a linear equationIndeed, $A{x}_0=b$ and $A(-1,-1,1{)}^T=0$. Conversely, subtracting $x_0$ from any solution gives a vector in the kernel, so this describes every solution. For $b^{\prime }$, the same row operations on the augmented matrix expose $0=1$: the second requirement demands $3$ where twice the first requires $2$.

In general, a linear system $Ax=b$ is solvable exactly when appending $b$ leaves the matrix rank unchanged:Appending a vector outside the column space adds an independent direction. When a solution $x_0$ exists, every solution is $x_0+\ker A$, because $A(x-x_0)=0$. Thus one count predicts both how many output directions are reachable and, through the rank-nullity theorem, how many independent input directions remain free.^[ref]

Use the left $A$-module structure $c\cdot (a\otimes b)=ca\otimes b$ on the tensor product of associative algebras. Expanding each $b\in B$ in the basis $b_1,\dots ,b_m$ shows that every tensor can be writtenThus the displayed family generates the module.

For uniqueness, let ${\beta }_j:B\to k$ be the corresponding dual basis, with ${\beta }_j(b_i)={\delta }_{ij}$. Applying the linear map ${\mathrm{id}}_A\otimes {\beta }_j$ to a linear relation ${\sum }_i{a}_i\otimes b_i=0$ gives $a_j=0$. Hence the family is linearly independent in a module, andIn particular $1\otimes b_1,\dots ,1\otimes b_m$ is a basis of a module, with coefficients uniquely in $A$.

A reduced crystallographic root system in a real Euclidean space is a finite spanning subset $\Phi$ not containing zero, with $\Phi \cap \mathbb{R}\alpha =\{\alpha ,-\alpha \}$, closed under $s_{\alpha }(v)=v-2(v,\alpha )\alpha /(\alpha ,\alpha )$, and satisfying $2(\beta ,\alpha )/(\alpha ,\alpha )\in \mathbb{Z}$ for all roots. A base of a root system is a vector-space basis $\Delta \subseteq \Phi$ such that every root has integer coefficients of one sign in that basis.

Choose $h$ not orthogonal to any root and call roots with $(h,\alpha )>0$ positive. Let $\Delta$ be the positive roots that cannot be written as a sum of two positive roots. Repeated decomposition terminates because each summand has strictly smaller positive $h$-value in a finite set. Thus every positive root is a nonnegative integer combination of $\Delta$.

For distinct $\alpha ,\beta \in \Delta$, $(\alpha ,\beta )\le 0$: otherwise the allowed difference-root lemma would make either $\alpha -\beta$ or $\beta -\alpha$ positive, decomposing one of them. In a real linear relation among $\Delta$, move negative coefficients to the other side, obtaining $u=v$ as positive combinations with disjoint supports. Then $\Vert u{\Vert }^2=(u,v)\le 0$, so $u=0$. But a nonempty positive combination has $(h,u)>0$, a contradiction. Thus the elements are linearly independent. They span every root and hence $E$, proving existence of a base of a root system. The difference-root lemma is used only for distinct roots; that qualification excludes the zero difference.

For the displayed set, there are eight coordinate roots, twenty-four roots with two nonzero unit entries, and sixteen half-coordinate roots: forty-eight in total. It spans ${\mathbb{R}}^4$, is reduced, and has squared root lengths one and two. Signed coordinate permutations preserve it. Reflections in coordinate roots are sign changes, and reflections in roots $e_i\pm e_j$ are signed coordinate permutations. Every half-coordinate root is obtained by a signed permutation from $h=(1/2,1/2,1/2,1/2)$, so it remains to check its reflectionIt sends $e_i$ to $e_i-h$, a half-coordinate root; it fixes $e_i-e_j$ and sends $e_i+e_j$ to the negative sum of the other two coordinate vectors. For a half-coordinate root, the sum of its four signs is $0,\pm 2$ or $\pm 4$; the formula sends it, respectively, to itself, a coordinate root, or its negative when parallel to $h$. Thus reflection closure holds. For a long root, the required Cartan integer is an integer dot product; for a coordinate root it is twice a half-integer; for $h$ it is ${\sum }_i{\beta }_i\in \mathbb{Z}$. Symmetry gives the remaining cases. Therefore this is the F4 root system.

In the printed base order, the Gram matrix isUsing the convention $a_{ij}=2({\alpha }_i,{\alpha }_j)/({\alpha }_j,{\alpha }_j)$, the Cartan matrix isThe row-coroot convention transposes this matrix. The Dynkin diagram is the chain $1-2\Rightarrow 3-4$, with the double bond pointing toward the shorter third root:

The associated symmetric positive definite form, normalized as a squared length, isIndeed it equalswhich is strictly positive for nonzero $x$. The alternative Gram normalization $Q/2$ is the same positive definite form up to a positive scalar.

A tabloid records the sets of entries in each row of a tableau. Let $C_t$ be the subgroup permuting entries independently within each column. The polytabloid isand the Specht module $S^{\lambda }$ is spanned by these vectors. A standard polytabloid is one whose tableau increases along rows and down columns.

Order tabloids by first sorting each row increasingly, then comparing the resulting row-reading words lexicographically. For a standard tableau $t$, every nonidentity column permutation produces a strictly larger word. In the first row affected by that permutation, each replacement comes from farther down the same column and is larger than the entry it replaces; all earlier rows remain unchanged. Sorting the affected row therefore increases its word. Also no nontrivial column permutation fixes its row sets, since a cell is the unique intersection of its row and column. Hence the least tabloid in $e_t$ is $\{t\}$ with coefficient one.

Distinct standard tableaux have distinct row tabloids. In a nonzero linear relation among their polytabloids, choose the least leading tabloid with a nonzero coefficient. None of the vectors with larger leading tabloids can contribute to it, so its coefficient cannot cancel. This contradiction proves linear independence of the standard polytabloids.

Choose the linear relationThen the displayed tensor contraction is $(a_i{c}_i)b_k-(a_i{b}_i)c_k=(a\cdot c)b_k-(a\cdot b)c_k$, precisely the $k$th vector component of $a\times (b\times c)$ by the vector triple product identity. The matrix $M$ need not be a symmetric matrix.

The row rank of $A$ is the dimension of the span of its rows in ${\mathbb{R}}^n$; its column rank is the dimension of the span of its columns in ${\mathbb{R}}^m$. Elementary row operations replace rows by invertible linear combinations, so preserve their span. They also preserve every column relation: $Ac=0$ if and only if $EAc=0$ for an invertible elementary matrix $E$. Reduce $A$ to row echelon form $R$, with $r$ nonzero rows. These rows are independent because their leading entries occur in distinct, successively later columns. The $r$ pivot columns are independent by their triangular pivot submatrix, while every column lies in the $r$-dimensional coordinate space supported on the nonzero rows. Thus both ranks of $R$, and hence both ranks of $A$, equal $r$. Row rank equals column rank.

Elementary column operations replace columns by invertible linear combinations and preserve their span. Equivalently, right multiplication by an invertible elementary matrix $F$ preserves row relations, since $c^{T}AF=0$ if and only if $c^{T}A=0$. Therefore either elementary row operations or elementary column operations preserve the matrix rank, and any finite sequence gives $\boxed{\mathrm{rank}(A^{\prime })=\mathrm{rank}(A)}$.

For the block matrices, put $M=\left(\begin{array}{cc}PQ& 0\\ Q& QR\end{array}\right)$. The explicit invertible multiplicationsfollow by first subtracting $P$ times the lower block row from the upper one and then subtracting the first block column times $R$ from the second. Changing the sign of the upper block row gives $N=\left(\begin{array}{cc}0& PQR\\ Q& 0\end{array}\right)$. These operations preserve matrix rank, proving that the two specified block matrices have equal rank. Their off-diagonal form gives $\mathrm{rank}(N)=\mathrm{rank}(Q)+\mathrm{rank}(PQR)$, since the two image components occupy independent coordinate blocks.

Choose $r_1=\mathrm{rank}(PQ)$ independent columns of $PQ$ and $r_2=\mathrm{rank}(QR)$ independent columns of $QR$. Select the corresponding $r_1$ columns from the first block column of $M$ and $r_2$ from the second. In a linear relation among these selected columns, the upper coordinate block forces every coefficient of the first selection to vanish; the lower block then forces every coefficient of the second to vanish. Consequently $\mathrm{rank}(M)\ge r_1+r_2$. Combining this with the equality of block ranks proves the Frobenius rank inequality:

Write $u=(a,b{)}^T$, $v=(c,d{)}^T$ and $\Delta =ad-bc$. If $xu+yv=0$, thenEliminating $y$ gives $\Delta x=0$, and eliminating $x$ gives $\Delta y=0$. Hence $\Delta \ne 0$ implies linear independence.

For the converse, suppose $\Delta =0$. If $u=0$, the family already contains the zero vector and is linearly dependent. If $a\ne 0$, the equality $ad=bc$ gives $v=(c/a)u$. If $a=0$ but $u\ne 0$, then $b\ne 0$ and $bc=0$ forces $c=0$, so $v=(d/b)u$. Both cases give a nontrivial linear relation. ThereforeThis is the two-dimensional determinant criterion, proved directly without assuming that criterion.

Subtracting the first vector from each of the other two preserves the basis property by iii. The resulting family isIts last two vectors belong to the plane with first coordinate zero. By b, they are linearly independent there precisely whenIn that case their two-dimensional span is the whole plane, and adjoining $e_1$ gives a basis of ${\mathbb{R}}^3$. If the displayed expression vanishes, a nontrivial linear relation among those two vectors prevents a basis. Thus

No. Every one of the three vectors has equal first and second Cartesian coordinates, so their linear span is contained in the plane $x=y$. That linear subspace has dimension two and cannot equal ${\mathbb{R}}^3$.

More explicitly, call the three given vectors $\mathbf{u},\mathbf{v},\mathbf{w}$ in their listed order. ThenThis nontrivial linear relation proves linear dependence, whereas a basis must be linearly independent. Being unit vectors alone does not ensure that they form a basis.

For quantifier elimination for infinite underlying vector spaces, we first justify that formulas cannot make finer distinctions than their linear-equation data. In any infinite underlying vector space, eliminate an existential variable from a disjunction of conjunctions of linear equations and inequations. If an equation has a nonzero coefficient of that variable, solve for it and substitute. If none does, the inequations forbid only finitely many values, leaving an available value in the infinite domain; the remaining equations concern only the other variables. Terms are linear combinations, so induction gives quantifier elimination for $T$ and completeness, since closed terms reduce to zero.

For one variable there are two possible complete types, zero and nonzero. Both are isolated, and every definable set is their union. ThusFor types of pairs of vectors over a finite field, the linear relation kernel $\{(a,b)\in K^2:ax+by=0\}$ determines the complete type. If $q=|K|$, the possibilities are one rank-zero pair, $q+1$ rank-one directions, and one rank-two independent type. Concretely these are $(0,0)$; $x\ne 0$ with $y={\lambda }_a(x)$ for each $a\in K$; $x=0,y\ne 0$; and the independent pairs. Their isolating formulas are finite because $K$ is finite. HenceEvery class is the union of a selection of these atoms. Basis extension also shows that pairs with the same relation kernel are conjugate by a linear automorphism within any infinite-dimensional model.

Yes. An $\mathbb{F}$-module over a field is a vector space. Start with a finite generating list. If it is linearly dependent, one vector has a nonzero coefficient in a linear relation; dividing by that coefficient expresses the vector using the others, so it can be removed without changing the span. Repeating terminates with a linearly independent generating list, which is a basis and therefore a basis of a module.

Thus every finitely generated module over a field is a free module. For the zero module, the empty list is the required basis of a module.

Source gap / TODO: the original printed page 4, confirmed visually, omits the unknown vector. It literally equates a $3\times 3$ matrix with a $3\times 1$ vector, so it does not define a well-formed system of linear equations. The following answer is conditional on the usual intended interpretation $A\mathbf{x}=(1,k^2,k{)}^T$; the missing factor is not present in the source.

Under that interpretation, the rows satisfy $r_1-2r_2+r_3=0$. Applying this linear relation to the right-hand side gives the necessary consistency conditionIt is sufficient too: the upper-left $2\times 2$ minor has determinant $4-9=-5\ne 0$, so the first two rows are linearly independent. The third row is $2r_2-r_1$, and imposes precisely the condition already found. ThereforeFor completeness, setting $x_3=t$ givesand direct substitution satisfies all three linear equations exactly for those two values of $k$. An unconditional answer to the malformed printed equality awaits a source correction.

For row reduction with a parameterized right-hand side at $\tau =5$, the nonzero reduced equations areColumn 3 has no pivot element, so $x_3$ is a free variable in a linear system. Taking $x_3=t$ gives every solution:There is no further restriction on $t$. Independent substitution into the original linear system givesConversely, the two reduced equations force exactly these coordinate formulas, so no solutions have been omitted. The same computation with zero right-hand side gives the kernel $\ker A=\mathrm{span}\{v\}$. Its dimension is one. The rank-nullity theorem appears here as $2+1=3$: two pivot columns and one freely chosen coordinate account for the three unknowns.^[ref]

In general a consistent linear system has solution set $x_0+\ker A$. Subtracting $A{x}_0=b$ from $Ax=b$ proves this description in both directions. The particular solution places the affine subspace, and the kernel supplies its directions.^[ref] Over the real numbers this example is an entire line; over the rational numbers the same formula uses rational $t$. A free variable in a linear system over a finite field instead has only finitely many choices.

The pivot columns identify a different object: the original column space. Here they selectwhich form its basis, while $a_3=-7a_1+3a_2$. The corresponding reduced columns are $(1,0,0,0{)}^T$ and $(0,1,0,0{)}^T$; their linear span is a different plane. For example, every original output satisfies $y_3=y_1+y_2$, but $(1,0,0,0{)}^T$ does not. Since $E$ is an invertible matrix, column linear relations survive $EA=R$ even though the output vectors move. This is why choosing original columns at the reduced pivot positions works.

Two matrices of the same size over the same field are row-equivalent matrices if a sequence of elementary row operations transforms one into the other.^[ref] Every operation is reversible, so they have the same row space and the same column linear relations. Writing the entire sequence as multiplication by an invertible matrix gives $R=EA$ andThus the kernel is preserved. For a nonzero right-hand side, perform every operation on the whole augmented matrix $[A\mid b]$: changing the coefficients while keeping $b$ fixed generally changes the solutions. The column space instead transforms to $E\mathrm{col}A$, which need not equal $\mathrm{col}A$.

The row rank of a matrix is the dimension of the vector space spanned by its rows. Elementary row operations preserve this row space; multiplication on the right by an invertible matrix preserves all linear relations among the rows.

To see why row rank equals column rank, write a reduced row echelon form as $R=EA$, where $E$ is a product of elementary matrices and is an invertible matrix. Reversibility of the row operations gives equal row spaces for $R$ and $A$. Also $Rz=0$ if and only if $Az=0$, so the columns have exactly the same linear relations. If $R$ has $r$ nonzero rows, its pivot columns are the first $r$ standard basis vectors of ${\mathbb{F}}^m$ and span its column space. Its nonzero rows are linearly independent, since their matrix entries in the pivot positions form an identity matrix. Both dimensions therefore equal $r$, and both counts transfer back to $A$.