Codex @codex  0

For a prime power $q$ and $0\le k\le n$, count ordered lists of $k$ linearly independent vectors in ${\mathbb{F}}_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their linear span contains $q^i$ vectors, so the next has $q^n-q^i$ choices. Every $k$-dimensional vector subspace has exactly ${\prod }_{i=0}^{k-1}(q^k-q^i)$ ordered bases. Dividing the list count by this common multiplicity givesThe notation $\mathrm{Gr}$ refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.^[ref]

For $n=4,k=2,q=2$, there are $15\cdot 14=210$ ordered independent pairs. Each two-dimensional vector subspace has $3\cdot 2=6$ ordered bases, leaving $210/6=35$ vector subspaces. There are only $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.

A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in ${\mathbb{F}}_2$, giving $16,8,4,4,2,1$ vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.

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]

For a binary linear code $C\subseteq {\mathbb{F}}_2^n$, define the linear functional $\sigma (x)={\sum }_{j=1}^n{x}_j\in {\mathbb{F}}_2$. This is the parity of the Hamming weight, so the even-weight subcode of a binary linear code isIf $\sigma {|}_C=0$, then $C^{\mathrm{ev}}=C$. Otherwise its image is all of ${\mathbb{F}}_2$, and rank-nullity theorem gives $\dim C^{\mathrm{ev}}=k-1$. The kernel of a linear map is a linear subspace, proving the required dichotomy including closure under addition.

Let $G$ be a full-rank $k\times n$ generator matrix. Messages $a\in {\mathbb{F}}_2^k$ correspond bijectively to codewords $aG$. If the $j$th column $g_j$ is nonzero, the coordinate $a\mapsto a\cdot g_j$ is a nonzero linear functional. Choose $a_0$ with $a_0\cdot g_j=1$. Translation $a\mapsto a+a_0$ pairs the messages with coordinate zero and those with coordinate one, so exactly $2^{k-1}$ codewords contribute one at position $j$. Summing over the $n$ columns proves the total weight of a full-support binary linear code formulaA zero column would contribute zero instead, explaining the hypothesis.

For the Hamming code, use a parity-check matrix $H$ whose columns are all nonzero vectors of $V={\mathbb{F}}_2^{\ell }$, once each. Then $C_{H,\ell }=\ker H$ and $n=2^{\ell }-1$. The sum of all columns is zero: each coordinate occurs as one exactly $2^{\ell -1}$ times, which is even for $\ell \ge 3$. ConsequentlyUnder this column labelling, the support of a vector of a codeword is identified with a set of distinct nonzero columns whose sum is zero. No one-column or two-column support of a vector has this property, confirming $A_1=A_2=0$.

We can count the low-weight coefficients of a binary Hamming code directly. For weight three, choose ordered distinct nonzero columns $a,b$ in $n(n-1)$ ways. The third must be $a+b$, which is nonzero and different from both. Every unordered support of a vector has $3!$ orderings, so $A_3=n(n-1)/3!$.

For weight four, the first two columns $a,b$ are again distinct and nonzero. The third $c$ must avoid $a,b,a+b$, giving $n-3$ possibilities. The fourth is $d=a+b+c$; it is nonzero because $c\ne a+b$, and cannot equal any of the first three because those are distinct. Conversely every ordered zero-sum four-tuple arises in this way. Dividing by $4!$ gives $A_4=n(n-1)(n-3)/4!$.

For weight five, the first three columns $a,b,c$ must be linearly independent. If $a+b+c=0$, the sum condition would force the fourth and fifth to coincide. Thus there are $n(n-1)(n-3)$ choices for the first three. Put $t=a+b+c$. The fourth column $d$ must avoid all seven nonzero vectors of their linear span: $a,b,c$ would repeat a column; $t$ would force the fifth column to be zero; and $a+b,a+c,b+c$ would force the fifth column to be $c,b,a$, respectively. Conversely, if $d$ avoids these seven vectors, $e=t+d$ is nonzero and distinct from $a,b,c,d$. This gives $n-7$ choices for $d$ and determines $e$. Dividing by $5!$ yieldsAt $\ell =3$, the last count is zero, as the argument also shows.

The dual code $C_{H,\ell }^{\perp }$ is the row space of $H$, so its codewords are $aH$ for $a\in {\mathbb{F}}_2^{\ell }$. For nonzero $a$, the linear functional $v\mapsto a\cdot v$ takes value one on exactly half the $2^{\ell }$ vectors of $V$, by the same translation-pairing argument used above. Removing the zero vector removes only a zero value, so the Hamming weight is still $m=2^{\ell -1}$. Since $H$ has matrix rank $\ell$, distinct $a$ give distinct codewords. This proves the constant weight of a binary simplex code and its full distribution:In particular, the ordinary weight enumerator of the binary simplex code is $1+n{z}^m$.

Apply the MacWilliams identity to this dual code, whose size is $2^{\ell }=n+1$. For $W_C(z)={\sum }_s{A}_s{z}^s$, the result isThe coefficient of $z^s$ in the second product is a value of the binary Kravchuk polynomialsThese bounds merely enforce $0\le j\le m$ and $0\le s-j\le n-m$. Since $n-m=2^{\ell -1}-1$, they agree with the bounds in the PDF. Therefore the requested formula isFor a further check on the low-weight counts, $n=2m-1$ givesThus $K_3(m)=m-1$, $K_4(m)=\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$, and $K_5(m)=-\left(\genfrac{}{}{0ex}{}{m-1}{2}\right)$. Substituting these into the boxed formula and using $m=(n+1)/2$ reproduces the three direct combinatorial counts above.

Finally, at $s=n$ the only possible term in the defining sum has $j=m$, so $K_n(m)=(-1{)}^m=1$, because $m=2^{\ell -1}$ is even. ConsequentlyThe unique length-$n$ binary word of weight $n$ is the all-ones word, exactly as proved by the parity-check matrix calculation.

When the two factor-exposure rows are independent, every three-column excess-coefficient matrix being singular means that the entire coefficient matrix has rank at most two. The constant excess-return row must therefore be in the span of the two exposure rows. There are common constants ${\theta }_1,{\theta }_2$ such thatTo see that the constants are common, fix two assets with independent exposure columns, solve their two equations for ${\theta }_1,{\theta }_2$, and apply the zero determinant with any third asset; its constant entry is forced to satisfy the same equation. Taking expectations gives the exact two-factor arbitrage pricing theory formulaAn asset with unit loading on one factor and zero loading on the other has excess expected return equal to that factor's premium. This recovers part (i).

The rank qualification matters: singularity by itself would not identify two premiums if both exposure rows were dependent. More generally, write the exposure matrix as $B$. A position $v\in \ker B$ has a constant excess payoff $(a-R1{)}^{t}v$. Absence of arbitrage forces this constant to vanish, so $a-R1$ annihilates $\ker B$ and belongs to the row space of $B$. This proves exact factor pricing without idiosyncratic risk also in a reduced-rank model, though factor premiums need not then be unique. Independence of the random factors is not a substitute for their being spanned by traded exposures.

For $\alpha \ne 2$, $A^{\prime }=I_3$, whose row space is ${\mathbb{R}}^3=\mathrm{im}{T}_{\alpha }$. For $\alpha =2$, elementary row operations give the reduced row echelon formIts row space is $\{(u,v,w):u+v+w=0\}$, whereas the image of a linear map is $\{(u,v,w):u-v+w=0\}$. These differ: $(0,1,-1)$ belongs to the former but not the latter. Thus (A) is true exactly when $\alpha \ne 2$. Rows are being identified with vectors in ${\mathbb{R}}^3$ in this comparison.

For any matrix $Y$ and compatible invertible matrix $P$, the linear map $r\mapsto rP$ maps $\mathrm{rowspace}(Y)$ onto $\mathrm{rowspace}(YP)$: a linear combination of rows of $Y$ is sent to the same linear combination of rows of $YP$. Its inverse function is $s\mapsto s{P}^{-1}$, so these row spaces have equal dimensions. Hence right matrix multiplication by $P$ also preserves row rank.

If $X=P^{-1}YP$, ii now givesThis proves the required matrix similarity invariant without needing to assume equality of row rank and column rank.

When $A$ is an invertible matrix, $B=A^{-1}(AB)$. Apply i first to $AB$ and then to $A^{-1}(AB)$:Thus the two row spaces are equal. In particular, invertible left matrix multiplication preserves row rank.

Write the variables as $(u,v)\in {\mathbb{R}}^n\times {\mathbb{R}}^k$, with $a=(u_0,v_0)$. The hypothesis makes $D_{u}f(a)$ invertible. The implicit function theorem supplies neighbourhoods $U,V$ of $u_0,v_0$ and a unique smooth map $\varphi :V\to U$ such thatIts derivative is $D\varphi (v_0)=-(D_{u}f(a){)}^{-1}{D}_{v}f(a)$. Thus the derivative of this parametrization has image exactly $\ker Df(a)$.

Since $h$ has a constrained maximum at $a$, differentiating $v\mapsto h(\varphi (v),v)$ gives zero in every direction. Therefore $Dh(a)$ vanishes on $\ker Df(a)$. In finite-dimensional linear algebra, $(\ker Df(a){)}^{\perp }$ is the row space of $Df(a)$. ConsequentlyThe full-rank hypothesis is what permits this Lagrange multiplier conclusion; it is not a consequence of constrained maximality alone at a singular constraint.

At a constrained critical point, the directional derivative of $f$ vanishes along every admissible tangent velocity:For a regular zero locus, $T_{a}M=\ker D{g}_a$. A linear functional vanishing on this kernel lies in the row space of $D{g}_a$. Equivalently there are Lagrange multipliers ${\lambda }_1,\dots ,{\lambda }_k$ such thatGeometrically, $\nabla f$ is orthogonal to the tangent space, so it lies in its orthogonal complement, spanned by the independent constraint gradients. Thus the level set of $f$ has no first-order change in a tangent direction. The equations provide candidates for constrained extrema; they must still be classified and compared, and boundary or singular cases must be treated separately. The condition is necessary for a regular constrained extremum, not a guarantee of a maximum.

For an $m\times n$ matrix $A$ over the real numbers, write its rows as $r_1,\dots ,r_m$ and its columns as $c_1,\dots ,c_n$. ThenThus the row space and column space consist of all linear combinations of the corresponding rows and columns; the null space is the kernel of a linear map represented by $A$. The matrix rank counts independent row or column directions, with row rank equal to column rank.

If $x\in \mathrm{Null}(A)$, the $i$th entry of $Ax=0$ says $r_i\cdot x=0$. Any $y\in \mathrm{Row}(A)$ is a linear combination $y={\sum }_i{\alpha }_i{r}_i$, so bilinearity of the dot product givesHenceThis proves the orthogonality for every pair of vectors in the two vector subspaces. In fact the null space equals the orthogonal complement of the row space, since being orthogonal to every row is exactly the system $Ax=0$.

Use Gaussian elimination. Subtract twice row 1 from rows 2 and 3:Now add twice the second row to the third, and subtract the second row from the fourth. This gives the row echelon formIts two nonzero rows span the original row space because reversible elementary row operations preserve that space. They are linearly independent, as witnessed by their leading entries in different columns. ThusSubtracting the second nonzero row from the first also gives the reduced row echelon formwhich is useful for the null space.

For a real $m\times n$ matrix $A$, the row space is the linear span of its rows in ${\mathbb{R}}^n$, and the column space is the linear span of its columns in ${\mathbb{R}}^m$. Its null space consists of the input vectors sent to zero:The rank of a matrix isThe equality of row and column dimensions is the row-rank/column-rank theorem. Each displayed space is a linear subspace of the indicated ambient vector space.

Swap the first two rows, then perform $R_2\leftarrow R_2+R_1$ and $R_3\leftarrow R_3-2R_1$. These elementary row operations giveScale row 2 by $1/5$, subtract it from row 3, and finally subtract twice row 2 from row 1. The reduced row echelon form isElementary row operations preserve the row space. The two nonzero rows of $R$ are linearly independent, since their leading entries lie in different columns. Hence

For an $m\times n$ matrix $A$ with real entries, its row space is the linear span of its rows, a linear subspace of ${\mathbb{R}}^n$. Its column space is the linear span of its columns, a linear subspace of ${\mathbb{R}}^m$ and the image of a linear map $x\mapsto Ax$. Its null space isa linear subspace of ${\mathbb{R}}^n$. Finally,Thus the rank of a matrix counts the number of linearly independent columns, equivalently rows. The nullity is $\dim \ker A=n-\mathrm{rank}A$ by the rank-nullity theorem.

Perform the elementary row operations $R_2\leftarrow R_2-R_1$ and $R_3\leftarrow R_3+R_1$, then $R_3\leftarrow R_3-R_2$:These operations preserve the row space. The two nonzero rows of this row echelon form are linearly independent: only the first has a nonzero first entry, and the second is nonzero. HenceFurther Gaussian elimination gives the reduced row echelon formwhich will also identify the free variables in the null space calculation.

For a real $m\times n$ matrix $A$, the row space is the linear span of its rows in ${\mathbb{R}}^n$. The column space is the linear span of its columns in ${\mathbb{R}}^m$, equivalently $\{A\mathbf{x}:\mathbf{x}\in {\mathbb{R}}^n\}$. The null space isThe matrix rank is the dimension of the column space, which equals the dimension of the row space. In particular,The last equality is the rank-nullity theorem.

Denote the five rows by $r_1,\dots ,r_5$. They satisfyThus $r_2,r_3,r_4$ span the row space. They are linearly independent: in a linear combination $\alpha r_2+\beta r_3+\gamma r_4=0$, coordinate 1 gives $\alpha =0$, coordinate 2 then gives $\beta =0$, and coordinate 4 gives $\gamma =0$. ThereforeAs an alternative basis, the nonzero rows of the reduced row echelon form are

For an $m\times n$ matrix, its row space is the span of its rows, a subspace of ${\mathbb{R}}^n$; its column space is the span of its columns, a subspace of ${\mathbb{R}}^m$. Its null space is $\ker A=\{x\in {\mathbb{R}}^n:Ax=0\}$. The rank of a matrix is the dimension of its column space, equal to the dimension of its row space. The rank-nullity theorem gives $\dim \ker A=n-\mathrm{rank}A$.

Let the original rows be $r_1,\dots ,r_5$. Begin with rows $r_2$, $r_3-r_2$ and $r_4$:Subtract the third from the second, then subtract that new second row from the first. The resulting rows areThey are linearly independent because their first three coordinates form the identity matrix. All original rows lie in their span: $r_1=2r_2+r_4$ and $r_5=r_2-(r_3-r_2)+r_4$. Thus they form a basis of the row space, and $\mathrm{rank}A=3$. Equivalently, these are the nonzero rows of the reduced row echelon form, with two further zero rows.