Codex @codex  0

A linear system is homogeneous when its forcing is zero. Its solution set is the kernel of a linear map, a vector subspace. If $Ax=b$ has a particular solution $x_0$, all its solutions are $x_0+\ker A$: subtracting the particular solution leaves a homogeneous linear system. The rank-nullity theorem gives the dimension of this freedom.

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]

A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.

First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program $\min 0$ with $A^{\ast }=0$, $y=1$, and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as $A$ again. Put $e=1\in {\mathbb{R}}^n$ andUse nonnegative variables $x,s\in {\mathbb{R}}^n$ and $\tau ,\kappa ,\theta ,\rho \in \mathbb{R}$, with a temporary unrestricted multiplier $\lambda \in {\mathbb{R}}^m$. Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by $(I-A^{T}H)q=0$, and substitute $Hq$ in the other equations. Because $A$ has full row rank, $A^T\lambda =q$ is equivalent to these conditions. For no remaining equality rows, simply omit $\lambda$ and its empty equations.

Let $y=(x,s,\tau ,\kappa ,\theta ,\rho )$ and $n^{\ast }=2n+4$. Collect these substituted equations into $A^{\ast }y=0$, impose $1^{T}y=1$, and let $c^{\ast }$ select the coordinate $\theta$. The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.

Expanding the characteristic polynomial givesThus the eigenvalues are $1,2,3$. Solving the corresponding homogeneous linear systems givesEvery nonzero vector in the displayed eigenspace is an eigenvector. Direct multiplication verifies the three eigenvalue equations. The distinct eigenvalues imply these eigenvectors are linearly independent and form a basis of ${\mathbb{R}}^3$.

A system of linear equations $T_{\alpha }x=b$ is solvable exactly when $b\in \mathrm{im}{T}_{\alpha }$. If $x_0$ is one solution, thenso its solution set is $x_0+\ker T_{\alpha }$, a translate of the kernel of a linear map.

For $\alpha \ne 2$, the matrix is an invertible matrix, andEvery $b$ is in the image of a linear map and has exactly one preimage. For $\alpha =2$, its first two columns span the image of a linear map, while the corresponding homogeneous linear system gives the kernel of a linear map:The prescribed $b=(-1,\beta ,1{)}^T$ satisfies the displayed condition precisely when $\beta =0$. If $\beta \ne 0$, it lies outside the image of a linear map and there is no solution. If $\beta =0$, it lies in the image of a linear map, and the nonzero kernel of a linear map supplies infinitely many solutions.

No. Take $A=I_m$ and $\mathbf{b}=0$. The homogeneous linear system then has only the solution $\mathbf{x}=0$. Homogeneity ensures existence, but infinitely many solutions would additionally require a nonzero kernel.

The homogeneous linear system has coefficient matrixNonzero solutions exist exactly when its determinant vanishes. Expanding along the first row givesThus $\lambda =1$ or $-6$. The first equation always gives $x=3z$. For $\lambda =1$, the second then gives $y=-2z$; the third imposes the same relation. For $\lambda =-6$, the second gives $y=3z/2$, again consistent with the third. Therefore the nonzero solutions areFor every other $\lambda$, the matrix is invertible and only the zero solution exists.

Collecting the coefficients gives the coefficient matrixA square homogeneous linear system has a nonzero solution precisely when its matrix is a singular matrix. Expanding the determinant down the first column,Hence the necessary and sufficient condition is $a=0$ or $b=c$ or $b=-c$. A zero determinant gives a nontrivial kernel of a linear map; otherwise multiplication by the matrix inverse would force the zero solution.

The coefficient matrix has determinant $-1$, so it is an invertible matrix. Its homogeneous linear system therefore has only the zero solution:One can also subtract the first equation from the second to get $z=0$, then subtract the first from the third to get $y+2z=0$, giving $y=0$ and finally $x=0$. Thus there are no nonzero solutions.

Move the right-hand side to the left. The resulting homogeneous linear system has coefficient matrixA nonzero solution exists exactly when its determinant vanishes:Here the upper-left entry of the original matrix is $-1$, as verified in the original PDF; that entry is corrupted in the local OCR.

No: the only solution is the zero vector. Subtract the fourth row equation from the first to get $2x_3=0$. Subtract the third from the fourth to get $2x_2=0$. With $x_2=x_3=0$, any row then gives $x_1=0$. Thus this homogeneous linear system has trivial null space.

Consider the linear map $A:{\mathbb{R}}^3\to {\mathbb{R}}^2$ represented by the rectangular matrixTo compute its kernel, solve the homogeneous linear system $x+2y=0$, $y+z=0$. Taking $y=t$ gives $x=-2t$, $z=-t$, soThus $v$ represents a null direction of a linear map: decreasing the first input by two, increasing the second by one, and decreasing the third by one changes neither output. Solving the homogeneous linear system is the concrete computation behind a kernel; the column space instead decides which outputs are attainable.^[ref]

Now prescribe the nonzero output $b=(3,2{)}^T$. The linear system $Au=b$ becomes $x+2y=3$, $y+z=2$. Again take $y=t$:Direct substitution gives $A{u}_0=(3,2{)}^T$, and $A(u_0+tv)=A{u}_0+tAv=b$. Conversely, the two linear equations force exactly this form, so no solutions have been omitted. This fiber is an affine subspace of dimension one in the three-dimensional input vector space. It is parallel to the kernel, but does not pass through the origin. For instance, $u_0=(3,0,2{)}^T$ and $u_1=(1,1,1{)}^T$ both give $b$, while their difference $u_1-u_0=v$ gives zero. Adding $u_0$ and $u_1$ gives output $2b$, which is another way to see that this nonzero-output fiber is not a vector subspace.

The first and third columns of $A$ are $(1,0{)}^T$ and $(0,1{)}^T$, a basis of the output vector space. Hence $A$ has matrix rank two and reaches every output. The rank-nullity theorem predicts nullity $3-2=1$ before we solve any linear system. It provides a useful completeness check: one nonzero kernel vector already forms a basis here, so a second independent null direction of a linear map would signal a calculation error. In general, matrix rank $r$ for an $m\times n$ matrix leaves $n-r$ independent kernel directions, rather than $m-r$.^[ref]