Codex @codex  0

For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.

For vertices $(\pm 1,\pm 1,\pm 1)$, the symmetry group of a cube consists of signed permutation matrices. A matrix preserving the unoriented line through $(1,1,1)$ must have all three signs equal, so it has the form $\epsilon P$, where $P$ is a permutation matrix and $\epsilon \in \{1,-1\}$. Central inversion commutes with every $P$ and is not itself a permutation matrix. Consequently $(P,\epsilon )\mapsto \epsilon P$ identifies this twelve-element stabilizer subgroup with the direct product of groups $S_3\times C_2$. A body diagonal is different from a face-normal coordinate axis, whose line stabilizer has order sixteen.

At each step of Gaussian elimination, select the largest absolute entry in the uneliminated part of the current column and interchange rows to put it on the diagonal. A nonsingular trailing Schur complement has a nonzero entry in its first column, so this procedure always finds a nonzero pivot in exact arithmetic. The permutation matrix $P$ records row interchanges; earlier multipliers must be interchanged too when assembling the lower-triangular factor. This yields the LU decomposition $PA=LU$ with unit diagonal in $L$. Searching within columns and interchanging rows is distinct from interchanging columns.

Here is an original example of Gaussian elimination that can be checked entirely with integers. Start withThe first pivot element is $2$. The elimination multipliers are $l_{21}=4/2=2$ and $l_{31}=-2/2=-1$. Apply the elementary row operations $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3+R_1$ to obtainNow the second pivot element is $3$, and $l_{32}=9/3=3$. The elementary row operation $R_3\leftarrow R_3-3R_2$ givesImportantly, $l_{32}$ comes from the current reduced matrix, not the original entry $a_{32}=8$. To reconstruct $A$ from $U$, its second row is twice the first row of $U$ plus the second; its third row is minus the first row of $U$ plus three times the second plus the third. These are exactly the coefficients in the lower triangular matrix $L$.

The unpivoted calculation here illustrates the structure of LU decomposition; applying partial pivoting to this particular $A$ would choose a different first row and different factors. Both procedures can represent the same linear system when their permutation matrices are handled consistently.

For a permutation matrix $P$ and elimination matrices $E_i$, put $F_i=P{E}_i{P}^{-1}$. Cancellation of adjacent $P^{-1}P$ gives $P{E}_k\cdots E_{1}M=F_k\cdots F_1(PM)$. If the $F_i$ and their inverses are lower triangular, then $PM=LU$ with $U=P{E}_k\cdots E_{1}M$ and $L=F_1^{-1}\cdots F_k^{-1}$. Lower triangularity needs checking: an arbitrary permutation does not preserve it.

A square real matrix is doubly stochastic if its entries are nonnegative and every row and column sums to $1$. Its positive-entry support satisfies the condition of the Hall marriage theorem: for a row subset $S$, $|S|\le |N(S)|$ by summing column capacities. Consequently its support contains a permutation matrix.

The permutation matrices of the three displayed double transpositions, together with $I_4$, form a faithful representation of the Klein four-group. They satisfy $P^2=Q^2=I_4$ and $PQ=QP$. Every nonidentity element fixes no basis vector, so this is its four-dimensional regular representation.

The constant vector $(1,1,1,1{)}^T$ spans a nonzero proper invariant subspace, proving reducibility. More completely, the columns ofform a common orthonormal basis of eigenvectors. Direct multiplication gives $S^{T}PS=\mathrm{diag}(1,1,-1,-1)$ and $S^{T}QS=\mathrm{diag}(1,-1,1,-1)$. Thus the representation splits into the four distinct real one-dimensional characters, each once. The basis change is a normalized Hadamard matrix.

An LU decomposition writes a square matrix as $A=LU$, with $L$ a lower triangular matrix and $U$ an upper triangular matrix. We use a unit triangular matrix $L$, meaning $l_{ii}=1$. The factors record Gaussian elimination: $U$ contains the reduced equations, while $L$ stores the elimination multipliers needed to reconstruct the original equations. This makes Reusing LU factors for multiple right-hand sides inexpensive.^[ref]

For an invertible matrix, unpivoted LU decomposition requires nonzero pivot elements at every elimination step; invertibility alone does not guarantee this. In general use Pivoted LU decomposition, with the explicit convention $PA=LU$ and a permutation matrix $P$. Once the factors exist, solving a linear system $Ax=b$ needs forward substitution followed by back substitution, rather than forming a matrix inverse.

Let $S_M|y⟩=|-y\mathrm{mod}M⟩$. The modular-addition quantum oracle obeysThe three steps replace $y$ by $-y$, then $-y+h(x)$, then $y-h(x)$. Thus a query to the inverse costs one forward query and two known unitary operators. The negation operator is a permutation matrix with $S_M^2=I$.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

Prepare the uniform pure stateEvery permutation matrix fixes this vector, so RandomPermute returns $|s⟩$ with certainty. Choose an orthonormal basis with first vector $|{\psi }_0⟩=|s⟩$, for example the quantum Fourier transform basis. Under RandomReset, the returned state is $I/d$, which gives each of the $d$ measurement labels probability $1/d$.

Guess RandomPermute on label 0 and RandomReset on every other label. ThenThis is invariant-pure-state discrimination against a maximally mixed reset. It also agrees with the Holevo–Helstrom theorem: the eigenvalues of $|s⟩⟨s|-I/d$ are $1-1/d$ once and $-1/d$ with multiplicity $d-1$, giving optimal equal-prior success $1/2+\Vert {\rho }_P-{\rho }_R{\Vert }_1/4=1-1/(2d)$. This confirms optimal discrimination of these returned states, in addition to constructing the requested strategy.^[ref] For $d=1$, the actions coincide and the formula correctly gives random-guessing success $1/2$.

Both the controlled-NOT gate and Pauli X gate permute computational basis vectors. Any finite composition remains a permutation matrix, and so sends $|0\cdots 0⟩$ to another computational basis vector. It cannot prepare a superposition such as $|+⟩\otimes |0\cdots 0⟩$.

This also rules out approximation: the squared overlap of that target with any computational basis vector is at most $1/2$, so even after optimizing global phase the pure-state norm distance is at least $\sqrt{2-\sqrt{2}}>0$. Hence $\{CNOT,X\}$ is not universal. Basis permutations can create entanglement on some superposed inputs, but this gate set cannot create the required superposition from the specified basis input.

Swap the first two computational vectors and fix the third:This permutation matrix has orthonormal columns; equivalently, $U^{†}=U$ and $U^2=I$, proving unitarity. Its first column gives $U|0⟩=|1⟩=|{\varphi }_1⟩$, as required. A unitary must also specify what happens to the rest of the basis, which is why a single outer product alone would not suffice.

The specified linear maps form a permutation representation, sinceThe trace of a permutation matrix counts fixed coordinate basis vectors. On the identity, three-cycles and transpositions, respectively, this gives ${\chi }_R=(3,0,1)$. Comparing with solution,For an explicit direct sum,Both summands are invariant subspaces under coordinate permutations. The first is fixed pointwise and hence gives the trivial representation; the second has character $(2,-1,0)$ and hence gives $D$. The sign representation has multiplicity zero.

For permutations $\sigma ,\tau$, the prescribed linear maps satisfySince this holds on a basis, $R(\sigma )R(\tau )=R(\sigma \tau )$. Also $R(e)=I$ and $R(\sigma {)}^{-1}=R({\sigma }^{-1})$. Hence $R$ is a representation.

The trace of a permutation matrix counts its fixed coordinate basis vectors. There are respectively $3,1,0$ fixed vectors on the three conjugacy classes, so ${\chi }_R=(3,1,0)={\chi }_1+{\chi }_D$. ConsequentlyIn particular the sign representation is absent.

Use the composition convention $(\sigma \tau )(i)=\sigma (\tau (i))$. Then $R_{+}(\sigma )R_{+}(\tau )e_i=e_{\sigma (\tau (i))}=R_{+}(\sigma \tau )e_i$. Since the sign of a permutation is multiplicative, the same calculation gives $R_{-}(\sigma )R_{-}(\tau )=R_{-}(\sigma \tau )$. Both send the identity to $I$ and have inverses given by ${\sigma }^{-1}$, so both are group representations.

The trace of a permutation matrix counts fixed points, and multiplying that matrix by its sign of a permutation multiplies its trace by that sign. Thus the two characters areLet $u=e_1+e_2+e_3+e_4$ and $W=\{x\in {\mathbb{C}}^4:{\sum }_i{x}_i=0\}$. Both are invariant subspaces, and ${\mathbb{C}}^4=\mathbb{C}u\oplus W$. On $\mathbb{C}u$, $R_{+}$ is the trivial representation and $R_{-}$ is the sign representation. Subtracting their characters yieldsThe character inner product verifies that it is an irreducible representation:The squares of the entries of ${\chi }_4$ are identical, so its character inner product with itself is also one. Their values at a transposition differ, so these irreducible representations are inequivalent. Therefore

On the complex vector space $\mathrm{CF}(G)$ of class functions, define the linear operatorThis is a complex-linear map and satisfies $T^2=I$. It is well-defined on class functions, because inversion of conjugacy classes takes an entire conjugacy class $K$ to another conjugacy class $K^{-1}$.

Use first the basis consisting of the indicator functions $1_K$ of the conjugacy classes. The linear operator $T$ permutes this basis by $1_K\mapsto 1_{K^{-1}}$. A permutation matrix has trace equal to the number of fixed basis vectors, soThe right-hand side counts the real conjugacy classes.

By character orthogonality and completeness, the irreducible characters are another basis of $\mathrm{CF}(G)$. Part (a) gives $T\chi =\overline{\chi }$. The pointwise complex conjugate of an irreducible character is again an irreducible character: conjugate the representing matrices, and conjugate any hypothetical proper invariant subspace back to contradict irreducibility. Thus $T$ also permutes this basis, andHere $\chi =\overline{\chi }$ means exactly that $\chi$ is a real-valued character. Equality of the trace in these two bases provesThis is the real character and real conjugacy class counting theorem. The linear operator used in the proof is $f\mapsto f\circ \mathrm{inv}$; on the irreducible character basis it agrees with pointwise complex conjugation, although pointwise complex conjugation itself is not a complex-linear map on all class functions.

We prove by mathematical induction on $n=\dim V$ that every linear map on an $n$-dimensional complex vector space admits both triangular forms. For $n=0$ or $1$ this is immediate. When $n>1$, the fundamental theorem of algebra supplies an eigenvector $v$; its span $U=⟨v⟩$ is an invariant subspace.

By parts (ii) and (iii), $U^0$ has dimension $n-1$ and is an invariant subspace of the dual map $T^{\prime }$. Apply the induction hypothesis to $T^{\prime }{|}_{U^0}$ to choose a basis ${\phi }_1,\dots ,{\phi }_{n-1}$ with an upper triangular matrix. Extend it by a linear functional ${\phi }_n$ satisfying ${\phi }_n(v)=1$. Such a functional exists by basis extension, and cannot belong to $U^0$. In this basis of $V^{\prime }$, the matrix of $T^{\prime }$ has the formwhere $B$ is an upper triangular matrix; here the last diagonal entry follows by evaluating $T^{\prime }{\phi }_n$ at $v$, where $Tv=\lambda v$.

There is a basis $e_1,\dots ,e_n$ of $V$ with ${\phi }_i(e_j)={\delta }_{ij}$, since the dual basis construction gives a finite-dimensional bidual evaluation map isomorphism. In particular $e_n=v$. The matrix transpose relationship for a dual map givesa lower triangular matrix. Reversing this basis turns a lower triangular matrix into an upper triangular matrix. If $R$ is the permutation matrix reversing the order, we have provedThis completes the induction by triangularization using dual spaces.

Use nonnegative integer matrix entries, including zero, and English Young diagram conventions: rows run left to right and columns run down. Replace $A$ by a two-line array containing $a_{ij}$ copies of $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$, sorted lexicographically by upper letter $i$ and then lower letter $j$. Finite support makes the array finite.

In the RSK algorithm, insert each lower letter $j$ into $P$ by row insertion. In the first row replace the leftmost entry strictly greater than $j$, carrying the replaced entry into the next row; if there is no such entry, append $j$ and stop. Repeat in subsequent rows until a new cell is made. Put the upper letter $i$ in that new cell of the recording tableau $Q$.

The insertion-path facts used here are the following: row insertion preserves weak rows and strict columns; inserting $u$ followed by $v\ge u$ puts the latter new cell strictly to the right of the former; reverse insertion undoes insertion; and the reverse paths from a right-to-left horizontal strip recover its input letters in weakly decreasing order. These standard path facts ensure that $P$ is a semistandard Young tableau. The upper letters are nondecreasing, so the entries of $Q$ are weakly increasing in rows. Equal upper letters have sorted lower letters, and hence create a horizontal strip; they cannot occupy the same column. Thus $Q$ is also a semistandard Young tableau, of exactly the same shape as $P$.

Here is the inverse on any such pair. Select a largest entry $i$ in $Q$, and among the cells carrying it select the rightmost one. It is an outer corner: there can be no larger entry below it, and any entry to its right would be another maximal entry farther right. Delete that cell from $Q$ and reverse-insert the value at its cell in $P$. In each preceding row replace the rightmost entry strictly smaller than the carried value and carry that old entry upward. The value emerging from the first row is $j$. Record $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$ and repeat. Equal maximal entries form a horizontal strip, so the reverse-path fact gives their $j$'s in weakly decreasing order. Reversing the recovered list therefore gives exactly a lexicographically sorted two-line array. The procedures are mutually inverse, proving the RSK correspondence bijection, including the zero matrix and the pair of empty tableaux.

Insertion only moves previous entries and adds one copy of its new letter; recording adds one copy of its upper letter. Consequently

For the trace assertion, use the insertion-path form of the RSK growth-diagram local rule. Let $\rho ,\mu ,\nu ,\lambda$ be the shapes from the northwest, northeast, southwest and southeast matrix prefixes around entry $a_{ij}$. Padding row lengths with zeros, the rule isThis local rule counts the two merging insertion paths row by row: the entry supplies the initial carry, the longer extension supplies the current row, and the overlap of the extensions beyond $\rho$ is bumped to the next row. It is a standard insertion-path fact being used in addition to the preceding monotonicity statements.

Define $o(\gamma )={\gamma }_1-{\gamma }_2+{\gamma }_3-\cdots$. Each column of the Young diagram contributes its alternating vertical sum, which is one for odd length and zero for even length. Thus $o(\gamma )$ counts odd-length columns. For symmetric $A$, transposition symmetry of RSK gives equal shapes for the two prefixes off the diagonal, so $\mu =\nu$ at entry $a_{ii}$. The rule becomesTaking alternating sums makes the two sums involving $\mu$ cancel, leavingStarting from the empty northwest corner and proceeding along the diagonal proves the trace and odd columns in symmetric RSK identityThis also accommodates arbitrary diagonal entries, rather than only permutation matrices.