Codex @codex  0

Termwise differentiation of the absolutely convergent matrix exponential series givesBecause $P$ and $Q$ commute, $P$ also commutes with every power of $Q$ and hence with $e^{tQ}$. The product rule therefore givesDirect differentiation gives $f_2^{\prime }(t)=f_2(t)(P+Q)$, and both initial values are $I$. The uniqueness theorem for ordinary differential equations, applied to the finitely many matrix entries, implies $f_1=f_2$. One can see uniqueness directly: the difference $D=f_1-f_2$ obeys $D^{\prime }=D(P+Q)$ and $D(0)=0$, soand the product is identically zero. At $t=1$ this yields

A sufficient condition is that $U$ is a connected space. Suppose, towards a contradiction, that $|f|$ is the same constant $R$ throughout $U$. If $R=0$, then $f=0$, contradicting $f(a)\ne f(b)$.

If $R>0$, differentiate $u^2+v^2=R^2$ in $x$ and $y$, and use the Cauchy-Riemann equations from part (a). They giveThe coefficient matrix for $(u_x,v_x)$ has determinant $-(u^2+v^2)=-R^2\ne 0$. Hence $u_x=v_x=0$, so $f^{\prime }=0$ everywhere. A holomorphic function with zero complex derivative is locally constant: within a small disc, differentiate along a straight segment. Local constancy and connectedness imply constancy on $U$, again a contradiction.

Consequently,This is the constant-modulus holomorphic function principle. The extra hypothesis matters: on two disjoint open discs, define $f=1$ on one and $f=-1$ on the other. It is holomorphic and nonconstant, yet $|f|=1$ everywhere.

For the $n$ distinct complex embeddings ${\sigma }_1,\dots ,{\sigma }_n$ of the number field, define the discriminant of elements of a number field byThe equality follows by multiplying the transpose of the embedding matrix by itself. Each field trace is rational: it is also the trace of the rational matrix of multiplication by $w_i{w}_j$ on $K$. Thus the determinant lies in $\mathbb{Q}$. If the $w_i$ are algebraic integers, the products and their conjugates are algebraic integers, and so are their sums. A rational algebraic integer is an integer, hence all trace entries and their determinant are integers.

Write $u_j={\sum }_i{a}_{ij}{v}_i$. The inclusion of the generated abelian groups makes $A=(a_{ij})$ an integer matrix. Its embedding matrix is the embedding matrix of the $v_i$ multiplied by $A$. Taking squared determinants givesFor independent algebraic integers $v_i$, choose an integral basis ${\omega }_i$ of ${\mathcal{O}}_K$. The same formula gives $D(v)=[{\mathcal{O}}_K:{\sum }_i\mathbb{Z}{v}_i{]}^{2}D(\omega )$. If $D(v)$ is nonzero and a square-free integer, the integer index must be one, proving that the $v_i$ form an integral basis.

Now put $\beta =3\alpha +4$. Since $\mathbb{Q}(\beta )=\mathbb{Q}(\alpha )$ has degree three, the monic polynomialis its minimal polynomial of an algebraic element. The field norm is the negative of its constant term:For the discriminant calculation, $f^{\prime }(\alpha )=3{\alpha }^2+4\alpha$. In the basis $1,\alpha ,{\alpha }^2$, using ${\alpha }^3=-2{\alpha }^2-1$, multiplication by this element has matrixThus the given derivative-norm formula gives $D(1,\alpha ,{\alpha }^2)=-59$. Since $\alpha$ satisfies a monic polynomial with integer coefficients, $1,\alpha ,{\alpha }^2$ are algebraic integers; the fact that a squarefree discriminant certifies an integral basis proves

For the basis $w_1,\dots ,w_d$, its discriminant isEquivalently it is the square of the determinant of the matrix of the $d$ embeddings applied to the basis vectors. It is nonzero because number fields are separable. An integral basis is a basis of the ring of integers as a free abelian group; in particular it is a rational basis of the field and expresses every algebraic integer uniquely with integer coefficients.

To prove existence, start with any rational basis and multiply each vector by a suitable nonzero integer to make it integral. This is possible by clearing coefficients in its monic rational minimal polynomial of an algebraic element and rescaling the variable. Let $M$ be the lattice spanned over $\mathbb{Z}$ by these integral vectors, and let $D\ne 0$ be its discriminant. For any algebraic integer $\alpha ={\sum }_j{c}_j{w}_j$, each trace $\mathrm{Tr}(\alpha w_i)$ is an integer. The resulting linear system has integral coefficient matrix with determinant $D$. Its adjugate matrix shows $c_j\in D^{-1}\mathbb{Z}$. ThusA subgroup of a finitely generated free abelian group is free and finitely generated. Here its rank is $d$, since it contains $M$ and is contained in a rank-$d$ lattice. Its free generators are the required integral basis.

For squarefree $d\ne 1$, the quadratic integral basis isThe source allows squarefree nonzero integers, so the degenerate value $d=1$ gives $K=\mathbb{Q}$ and basis $\{1\}$ instead of a two-element basis.

In the biquadratic field define the three automorphisms by changing respectively the sign of $\sqrt{r}$, the sign of $\sqrt{2}$, and both signs. Their actions areHence the three sums are $2a+2b\sqrt{2}$, $2a+2c\sqrt{r}$ and $2a+2d\sqrt{2r}$. If $\mu$ is integral, each sum is integral and lies in its displayed quadratic subfield. Their radicands are squarefree and respectively congruent to two, three and two modulo four. The quadratic basis formula therefore forces all their two coefficients to be integers, proving

Set $A^{(0)}=A$. At step $k=1,\dots ,n-2$, let $u=A_{k+1:n,k}^{(k-1)}$ be the column below the diagonal. Choose a Householder reflection ${\hat{H}}_k$ sending $u$ onto its first coordinate axis, and embed it asIf $u=0$, use $P_k=I$. Left multiplication annihilates entries $k+2,\dots ,n$ in column $k$. Right multiplication performs the matching operation on row $k$, because the matrix remains symmetric. The first $k$ coordinates are fixed, so zeros already created in earlier columns and rows are preserved.

Here the orthogonality of each $P_k$ is used explicitly: $P_k^{-1}=P_k^T$, so each update is a similarity transformation and preserves eigenvalues. After $n-2$ steps,where $Q$ is orthogonal and $T$ is a real symmetric tridiagonal matrix. This is Householder tridiagonalization.

For an efficient QR algorithm, first reduce a general real matrix to upper Hessenberg matrix by orthogonal similarities. For a real symmetric matrix, use Householder tridiagonalization; the resulting symmetric tridiagonal matrix is the usual input in this setting. These structures are preserved by suitable QR algorithm implementations and greatly reduce the work per iteration.

The output is the eigenvalues, together with an orthogonal reduction when the factors are accumulated. In the symmetric case the target is a diagonal matrix, whose diagonal entries are the real eigenvalues; the accumulated orthogonal columns are eigenvectors. For a general real matrix, the target is the real form in a Schur decomposition: an upper block triangular matrix with diagonal blocks of size one or two. The two-by-two blocks represent complex conjugate eigenvalue pairs. An arbitrary unshifted iteration need not converge, so these describe the intended converged output, with appropriate shifts and block deflation in the QR algorithm.

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

The initial bottom-right entry is zero, so the chosen QR shift is ${\mu }_0=0$. One valid QR factorization is $Q_0=A$, $R_0=I$, using explicitly that $A^{T}A=I$. The update isIt repeats forever and never approaches a diagonal matrix. With the standard positive-diagonal convention for $R$, this factorization is unique, so the Rayleigh-shift iteration is stationary and fails to diagonalize $A$.

The failure is independent of harmless sign conventions. The columns of $A$ are already orthonormal, so another QR factorization can only replace $Q_0$ by $AD$ and $R_0$ by $D$, where $D$ is diagonal with entries $\pm 1$. Then $A_1=DAD$ still has zero diagonal and off-diagonal magnitudes one. Subsequent bottom-right shifts remain zero and the off-diagonal magnitude never decreases. The eigenvalues are $+1,-1$, with equal absolute values, explaining the lack of separation in the unshifted QR algorithm.

Let the real QR shift be $\mu$ and put $r=\sqrt{1+{\mu }^2}$. A valid QR factorization, including the singular cases $\mu =\pm 1$, isHere $Q^{T}Q=I$, and multiplying verifies $QR=A-\mu I$. Using this orthogonality in the shifted update givesIt is diagonal exactly when ${\mu }^2-1=0$. Therefore all real shifts giving the eigenvalues in one iteration areThe resulting diagonal is $(-1,1)$ or $(1,-1)$, respectively. Both QR shifts are exact eigenvalues. Sign changes in the QR factorization conjugate $A_1$ by a diagonal sign matrix and do not alter its zero pattern. This is Exact-shift diagonalization of a two-state swap matrix.

The Gershgorin circle theorem states that every eigenvalue of $A=(a_{ij})\in {\mathbb{R}}^{n\times n}$ belongs to at least one of the closed Gershgorin discsThe eigenvalue may be complex even though the matrix is real. To prove the theorem, choose a nonzero complex eigenvector $v$ with $Av=\lambda v$ and an index $i$ at which $|v_i|$ is maximal. Then $|v_i|>0$, and the $i$th row givesThe triangle inequality yieldsThus $\lambda \in D_i$, proving the assertion without any symmetry assumption.

The first row has off-diagonal sum $a_{12}<1/4$. Rows $2,\dots ,n-1$ have sums less than $1/2$, and the last row has sum $c+a_{n,n-1}<5/4$, since $0<c<1$. Every row except the second therefore has its Gershgorin disc strictly away from zero: its centre is at least one in the first row and at least three in the remaining rows.

For the second row, an exact sufficient condition is $|b|>a_{21}+a_{23}$. Since the sum is strictly below $1/2$, the coefficient-independent boundsguarantee that zero is outside every Gershgorin disc. Consequently zero is not an eigenvalue and $A$ is an invertible matrix. Equality at $\pm 1/2$ is allowed because the off-diagonal entry bounds are strict. These are sufficient strict diagonal dominance bounds; values of $b$ between them can also give invertible matrices.

Put $n=2m$. With $b=2$, the row Gershgorin discs have centres $1,2,\dots ,n$ and radiiApplying the theorem to the transpose gives column Gershgorin discs with radiiThe enlarged disc moves from the last centre to the first centre. All small discs in either family are mutually disjoint, because adjacent centres are one unit apart and their radii have sum strictly below one.

For the row family, the small disc at any $i\le m$ is also disjoint from the enlarged disc at $n$ ifFor the column family, every small disc at $i\ge m+1$ is disjoint from the enlarged disc at $1$ by the same estimate, since $i-1\ge m$. Thus the Gershgorin eigenvalue counting theorem certifies one simple eigenvalue near each of $1,\dots ,m$ from rows, and near each of $m+1,\dots ,n$ from columns. The certified small discs from the two families are themselves disjoint, so these are $n$ different eigenvalues.

The largest nonnegative $c$ certified by these uniform row-and-column separation bounds isMore generally the argument works for $|c|\le c_{\mathrm{G}}$. The endpoint is included because all actual entry bounds, and hence all actual radius estimates above, are strict. For $n=8$, $c_{\mathrm{G}}=13/4$: row discs isolate centres $1,2,3,4$, and column discs isolate centres $5,6,7,8$.

For $c>c_{\mathrm{G}}$, taking the adjacent entries sufficiently close to $1/4$ makes the enlarged row disc meet the small disc at $m$, and the enlarged column disc meet the small disc at $m+1$. Hence this particular uniform disc-separation certificate stops there. This is a Gershgorin guarantee, not a necessary spectral threshold: failure of disc separation does not prove repeated or nonreal eigenvalues for the actual matrix.

Finally, a real matrix has nonreal eigenvalues in complex conjugate pairs. Every certified small disc has a real centre and is invariant under conjugation. A nonreal eigenvalue in it would bring its distinct conjugate into the same disc, contradicting its count of exactly one. Therefore all the certified eigenvalues are real and simple. The two-family argument is Complementary row and column Gershgorin isolation.

Strict diagonal dominance givesThus every $b_{ii}\ne 0$, and the diagonal matrix $D$ has inverse $D^{-1}=\mathrm{diag}(1/b_{11},\dots ,1/b_{nn})$. The iteration matrix has entriesEach row Gershgorin disc for $T$ is centred at zero and has radiusTherefore every eigenvalue of $T$ satisfiesEquivalently, the induced matrix norm satisfies $\Vert T{\Vert }_{\infty }<1$, bounding the spectral radius. This is the usual Jacobi convergence from strict diagonal dominance; the Jacobi error matrix is $-T$, with the same eigenvalue magnitudes.

A real square matrix $Q$ is an orthogonal matrix when $Q^{T}Q=I$, equivalently its columns form an orthonormal basis. Here $Q^T$ is the transpose and $I$ the identity matrix. For every vector $x$,Taking nonnegative square roots provesThus an orthogonal matrix preserves the Euclidean norm.

Put $C=Q_{1}A$ and write its second column as $v$. For $n\ge 3$, takewhere each angle is computed from the current second column, in the right-to-left application order. These Givens rotations eliminate its entries in rows $3,\dots ,n$ by accumulating their Euclidean norm in row two.

Each rotation acts only on rows with indices at least two. The first column of $C$ is $\Vert a{\Vert }_2{e}_1$, whose entries in all those rows are zero. Mixing two zeros leaves them zero, and row one is untouched. Thus the first column is unchanged. The resulting matrix has the formThis verifies both required properties, including the case of zero second-column tail. When $n=2$ there are no rows to eliminate: take $Q_2=I_2$, the empty product. No sign change of $v_2$ is required in that case. Each Givens row-pair update preserves previously eliminated columns, which is the central invariant of QR decomposition by Givens rotations.

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore

Set $W=\mathrm{diag}(w_0,\dots ,w_n)$. For column indices $j,k\in \{1,\dots ,n+1\}$, the product $P_{j-1}{P}_{k-1}$ has polynomial degree at most $2n$, so exactness of Gauss-Legendre quadrature and orthonormality giveThus $Q=W^{1/2}A$ is a square matrix with $Q^{T}Q=I$, and therefore is an orthogonal matrix: $Q{Q}^T=I$ as well. It follows thatEquivalently, the rows of the generalized Vandermonde matrix are orthogonal andThe normalization matters: here $P_{n+1}=\sqrt{(2n+3)/2}{L}_{n+1}$, where $L_{n+1}$ is the conventional Legendre polynomial used above. Thus a formula containing only the nodes and the question's orthonormal polynomials isThis identity is the discrete orthogonality of Gaussian quadrature.

Retain the first $r$ terms in the singular value decomposition:The Eckart-Young-Mirsky theorem says that this truncated singular value decomposition is a best low-rank approximation in the spectral norm. The remaining singular values of the difference are ${\sigma }_{r+1},\dots ,{\sigma }_n$, together with zeros, soFor $r\ge 1$ the displayed matrix has matrix rank exactly $r$, since every retained singular value is positive. For $r=0$, the only matrix of matrix rank zero is the zero matrix, and the same formula gives error ${\sigma }_1$.