Codex @codex  0

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, a state $a$ is absorbing exactly when $P_{aa}=1$. Nonnegativity and the row sum then force $P_{aj}=0$ for $j\ne a$: once entered, $a$ is never left. Equivalently, $\{a\}$ is a closed communicating class. A larger closed communicating class may keep moving internally; closure means confinement to a set, whereas absorption at a state means remaining at one point.

An absorbing state is useful for recording a terminal outcome: after a toy routine finishes, keep its outcome in the state space so that the same transition matrix still describes subsequent steps. Calling a finite Markov chain absorbing usually also requires that some absorbing state be accessible from every state. Merely containing an absorbing state is insufficient: another closed communicating class could prevent absorption. See Grinstead and Snell, Introduction to Probability, section 11.2 for this convention.

Consider a constructed routine with unfinished modes $u,v$ and terminal outcomes $A,B$. All the following transition probabilities are chosen for illustration, not estimated from observations. In state order $(u,v,A,B)$, takeThe communicating class $\{u,v\}$ is open, while $\{A\}$ and $\{B\}$ are closed communicating classes consisting of absorbing states. Both terminal outcomes are accessible from both unfinished modes, sometimes by an indirect path.

Let $T=\inf \{n\ge 0:X_n\in \{A,B\}\}$ be the terminal hitting time. Write $h_i={\mathbb{P}}_i(X_T=A)$ for the absorption probability and $t_i={\mathbb{E}}_{i}T$ for the expected hitting time, with the subscript denoting the starting state. First-step analysis givesHere $h_A=1$, $h_B=0$, and $t_A=t_B=0$. Solving these two pairs of linear equations yieldsStarting at $u$ therefore ends at $A$ with probability $0.6$ and takes $3.2$ steps on average to reach either terminal state. The terminal hitting time counts the transition into the outcome, but no later self-transitions. Outcome and duration answer different questions: from $v$, outcome $A$ is less likely, yet termination is faster on average.

The matrix power $P^2$ gives the probability distribution after two steps from $u$ asThus ${\mathbb{P}}_u(T>2)=1/2$, and the probability of having already reached $A$ is $3/8$, still below its eventual absorption probability $3/5$. From either unfinished mode, each next step has terminal probability at least $1/4$. Consequently ${\mathbb{P}}_i(T>n)\le (3/4{)}^n$, proving termination almost surely and finite expected hitting time directly. The Fundamental matrix of a finite absorbing Markov chain packages both calculations and counts visits to unfinished modes.

Iterating an affine map gives $x_k=M^{k-1}{x}_1+{\sum }_{j=0}^{k-2}{M}^{j}c$. A fixed point exists exactly when $c$ is in the image of a linear map $I-M$. If the spectral radius of $M$ is below one, its matrix powers tend to zero and every orbit converges to the unique fixed point $(I-M{)}^{-1}c$.

Every square matrix satisfies its own characteristic polynomial. More explicitly, for an $n$-by-$n$ matrix $A$ over a commutative ring with identity, formThenHere $0$ is the zero matrix, and the constant term multiplies the identity matrix. This is a polynomial evaluated at a matrix; it is stronger than saying that each eigenvalue is a root of a polynomial. Neither diagonalizability nor distinct eigenvalues is required.^[ref]

The practical payoff is that arbitrarily high matrix powers can be reduced to a combination of $I,A,\dots ,A^{n-1}$. These powers arise when repeatedly applying a linear map, solving a linear recurrence relation, or evolving a finite state space model. The characteristic polynomial turns that repeated action into a fixed-order scalar recurrence. The minimal polynomial may reduce the number of required powers further.

In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n{)}_{ij}>0$ for some $n\ge 0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an equivalence relation, and a communicating class is an entire equivalence classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.

The allowance of zero steps matters: $P^0=I$, the identity matrix, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.

A closed communicating class satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere are exactly three communicating classes: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct matrix power check gives $(P^2{)}_{s,c_2}=1/4$ and $(P^2{)}_{c_2,s}=0$.

Starting at $s$, let $\tau$ be the first hitting time of either closed class. Staying at $s$ for $n$ steps has probability $2^{-n}$, so ${\mathbb{P}}_s(\tau >n)=2^{-n}$ and ${\mathbb{E}}_s\tau ={\sum }_{n\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(1/2{)}^k(1/4)=1/2$. Hence the hitting probability of the absorbing state $a$ is only $1/2$, and its unconditional expected hitting time from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.

Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an irreducible Markov chain with period two; the restriction to $\{a\}$ is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.

A scalar $\lambda$ is an eigenvalue of a linear operator $A:V\to V$ whenfor some nonzero vector $v$, called an eigenvector. The scalar must belong to the field over which $V$ is a vector space. Geometrically, a real eigenvalue tells us what $A$ does along a special line: every vector on that line is multiplied by the same number. The eigenvector gives the line and the eigenvalue gives its scaling.

For a real eigenvalue, $\lambda >0$ preserves the orientation along the line, $\lambda <0$ reverses it, and $\lambda =0$ collapses the line to zero. The length is multiplied by the modulus $|\lambda |$, so $|\lambda |>1$ stretches and $0<|\lambda |<1$ contracts. For example, the diagonal matrix $\mathrm{diag}(2,-1/2,0)$ doubles one coordinate direction, reverses and halves another, and annihilates the third. Its eigenvalues are $2,-1/2,0$; the last direction lies in its kernel.

For a finite square matrix, the eigenvalues are the roots of a polynomial $p_A$, its characteristic polynomial:Here $I$ is the identity matrix. The reason is that $Av=\lambda v$ means $(A-\lambda I)v=0$ with $v\ne 0$: the shifted matrix must have a nontrivial kernel, equivalently a zero determinant. The worked symmetric matrix example in eigenvector shows both stages: find the eigenvalues, then find their eigenspaces.

Eigenvalues are especially useful for repeated application of a linear map. If $Av=\lambda v$, thenOne multiplication proves the next step, so a matrix power becomes an ordinary power on each eigenvector. This explains growth, decay, and alternating signs along these directions. Gilbert Strang develops this connection, and its extension to the matrix exponential, in his lecture "Eigenvalues and Eigenvectors" (MIT 18.065, 2018).^[ref]

A documented historical connection is C. G. J. Jacobi's "Über ein leichtes Verfahren die in der Theorie der Säcularstörungen vorkommenden Gleichungen numerisch aufzulösen" (1846, Journal für die reine und angewandte Mathematik 30, pp. 51–94). Its opening discusses symmetric matrices arising from small oscillations, with a common unknown subtracted from every diagonal entry. In modern notation this is $(A-\lambda I)v=0$; Jacobi seeks the parameter and the ratios of the components of $v$. This is evidence of an early physical and computational setting for the eigenvalue problem, without assigning its discovery to a single person.^[ref][ref]

The linear recurrence relation defining the Fibonacci numbers, with $F_0=0$ and $F_1=1$. Its state $(F_{n+1},F_n{)}^T$ advances by the matrix $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$, so matrix powers describe repeated updates.

For a positive integer $m$, the negative matrix power is differentiable on the open general linear group. The Neumann series gives $(A+H{)}^{-1}=A^{-1}-A^{-1}H{A}^{-1}+O(\Vert H{\Vert }^2)$ locally around any invertible matrix. Applying the product rule to the $m$ factors of this inverse gives the displayed Fréchet derivative. Each summand chooses one inverse factor to differentiate while keeping the others in order.

The factor order matters. Only when $A$ and $H$ commute does the sum simplify to $-m{A}^{-(m+1)}H$. This is a useful example of why scalar differentiation rules for powers cannot be transferred to matrices without accounting for noncommutativity.

If a square matrix satisfies $(A-I)(A+I{)}^2=0$, then $A^{-1}=A^2+A-I$, and every integer matrix power lies in the span of $I,A,A^2$. Writing $s=(-1{)}^n$, the universal formula is $A^n={\alpha }_n{A}^2+{\beta }_{n}A+{\gamma }_{n}I$, where ${\alpha }_n=(1-s)/4+ns/2$, ${\beta }_n=(1-s)/2$ and ${\gamma }_n=(1+3s)/4-ns/2$. The polynomial $p_n(t)$ on the right satisfies $p_n(1)=1$, $p_n(-1)=(-1{)}^n$ and $p_n^{\prime }(-1)=n(-1{)}^{n-1}$. These value and derivative conditions implement interpolation at a repeated root. For negative integers the inverse formula first puts $A^n$ in the same polynomial algebra; the nilpotent block identity $(I-N{)}^n=I-nN$ for $N^2=0$ proves the derivative rule for every integer.

Matrix similarity invariants are quantities unchanged by replacing $A$ with $S^{-1}AS$. Important examples are the characteristic polynomial, trace, determinant, matrix rank, and eigenvalues with their algebraic multiplicities. The characteristic polynomial convention here is ${\chi }_A(t)=\det (tI-A)$, where $I$ is the identity matrix.^[ref]

The short determinant proof works over any field: because $tI-B=S^{-1}(tI-A)S$, multiplicativity of the determinant givesThus its roots, the eigenvalues, retain their algebraic multiplicities in any field extension where the polynomial splits. Also $\det B=\det A$. The cyclic property of the trace gives $\mathrm{tr}(S^{-1}AS)=\mathrm{tr}(AS{S}^{-1})=\mathrm{tr}A$; equivalently, the trace is determined by the coefficient of $t^{n-1}$ in the characteristic polynomial for an $n$-by-$n$ matrix.^[ref]

For the two matrices in the opening example,Their entries differ, yet these quantities agree. Agreement is a useful necessary test for matrix similarity; it is not sufficient in general, as same eigenvalues do not imply similarity illustrates.

The relation also preserves repeated application. Adjacent factors $S{S}^{-1}$ cancel to giveFor the opening example, matrix powers therefore have the explicit formAt $k=2$, this is $\left(\begin{array}{cc}4& -21\\ 0& 25\end{array}\right)$. Acting on $y=(1,1{)}^T$ gives $(-17,25{)}^T$, which reconstructs as $S(-17,25{)}^T=(8,25{)}^T=A^{2}x$. More generally $q(B)=S^{-1}q(A)S$ for every polynomial $q$, so the minimal polynomial is also unchanged. Multiplication by invertible matrices preserves matrix rank, giving another invariant without finding eigenvalues.

For a square matrix over a field, the minimal polynomial $m_A$ is the unique monic polynomial of least degree satisfying $m_A(A)=0$. The Cayley-Hamilton theorem guarantees at least one such polynomial: the characteristic polynomial. The minimal polynomial divides every polynomial that annihilates $A$, so reducing matrix powers modulo $m_A$ can need fewer coefficients than reducing modulo the characteristic polynomial.

For example, $2I_2$ has minimal polynomial $t-2$, whereas the Jordan block $\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ has minimal polynomial $(t-2{)}^2$. Both have the same characteristic polynomial. Their different matrix powers are illustrated in repeated eigenvalues in the Cayley-Hamilton theorem.

Newton's identities let two different summaries of the same polynomial roots talk to each other. Elementary symmetric polynomials record products of distinct root positions; power sums record sums of individual powers, $p_r={\sum }_{i=1}^n{x}_i^r$. Either can be easier to obtain in a particular problem. The identities turn one into the other, often avoiding any need to find the individual polynomial roots.

Write $e_0=1$ and $e_m=0$ for $m>n$. For every positive integer $m$, the identity isIt is a polynomial identity over the integers, so it remains true on substitution in any commutative ring. To solve it for $e_m$ by division, however, $m$ must have a multiplicative inverse. Over a field of characteristic zero, the first $n$ power sums recover every elementary symmetric polynomial. The same recovery works when the positive characteristic of a field is greater than $n$; small characteristic needs care.^[ref]

The first three relations are $e_1=p_1$, $2e_2=e_1{p}_1-p_2$, and $3e_3=e_2{p}_1-e_1{p}_2+p_3$. When division by two and three is permitted, this becomesFor the three roots $1,2,3$, their power sums are $p_1=6$, $p_2=14$, and $p_3=36$. The formulas give $e_2=(36-14)/2=11$ and $e_3=(216-252+72)/6=6$, recovering the polynomial $z^3-6z^2+11z-6$ from aggregate data.

The beauty is that the summaries do not depend on the order of the polynomial roots. In symmetric polynomials, one can work with quantities that survive every relabeling; in linear algebra, traces of matrix powers give the same kind of aggregate information about eigenvalues. The identities convert those summaries into coefficients of a characteristic polynomial.

A short derivation packages the identities into a formal power series. Let $E(t)={\prod }_i(1+x_{i}t)={\sum }_{m\ge 0}{e}_m{t}^m$. Since its constant coefficient is one, it has an inverse as a formal power series, and its formal derivative satisfiesMultiply by $E(t)$ and compare the coefficient of $t^{m-1}$. This gives Newton's identities without a convergence assumption or division by $m$. The division issue arises only when using them to recover $e_m$. The logarithmic-derivative approach is also developed in Newton's Identities (January 2019 notes) by Milan Mossé (§4, pp. 6–8).

The alternate name Newton-Girard identities recalls Albert Girard's earlier work. A modern historical account credits formulas through sixth powers to Albert Girard in 1629 and discusses their later appearance in Isaac Newton's Arithmetica universalis.^[ref] This citation refers to that account; the original historical editions have not been inspected here.

Subtract the identity matrix and putDirect matrix multiplication givesFor the last equality, each column of $N^2$ is a multiple of $(1,-1,0{)}^T$, and $N(1,-1,0{)}^T=0$. Thus $N$ is a nilpotent matrix. The minimal polynomial of $A_{\lambda ,\mu }$ divides $(t-1{)}^3$ and equals $(t-1{)}^s$, where $s$ is the nilpotency index of $N$.

The first row of $N$ forces $\lambda =0$ if $N=0$, and its third row then forces $\mu =0$. Conversely $\lambda =\mu =0$ gives $N=0$. If exactly one parameter is nonzero, then $N\ne 0$ but $N^2=0$. If both are nonzero, then $N^2\ne 0$ while $N^3=0$. Consequently the complete answer isNo lower power can annihilate the matrix in any of these cases, as the displayed nonvanishing matrix powers show.

We construct a cube root of a matrix on each Jordan block. Since $A$ is an invertible matrix over the complex numbers, its Jordan normal form isConsider one block $J_m(\lambda )=\lambda I+N$, where $N=J_m(0)$ is a Nilpotent Jordan block and $N^m=0$. Choose a complex cube root $\beta$ of $\lambda$, so ${\beta }^3=\lambda$.

We need a polynomial $q(z)$ with constant term one satisfyingThis can be constructed using only polynomial multiplication. Write $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$. Once $c_1,\dots ,c_{j-1}$ have been chosen, the coefficient of $z^j$ in $q(z{)}^3$ is $3c_j$ plus an expression depending only on those earlier coefficients. Choose $c_j$ to make this coefficient one at $j=1$ and zero at $2\le j<m$. Division by three is possible over the complex numbers, so the recursion always succeeds. Its first coefficients areThis is the truncated binomial cube root of the identity plus a nilpotent matrix; equivalently $c_j=\left(\genfrac{}{}{0ex}{}{1/3}{j}\right)$, where the generalized binomial coefficient is $\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$ and the empty product is one.

Substitute $z=N/\lambda$. The polynomial remainder is a multiple of $N^m$, hence zero. It follows thatFor $m=1$, take $q=1$, so the same construction covers single-entry blocks. Assemble the block diagonal matrix $C={⨁}_r{C}_{m_r}({\lambda }_r)$. Taking matrix powers respects these blocks, and conjugating back givesThus every invertible matrix over the complex numbers has at least one cube root of a matrix. The construction uses only finitely many matrix powers.

The addition formulas for the hyperbolic functions implySince $M=B(y)/2$, its fourth matrix power isAlternatively, the orthonormal eigenvectors $(1,\pm 1)/\sqrt{2}$ have eigenvalues $e^{\pm y}/2$. Raising these eigenvalues to the fourth power gives the same result by spectral decomposition.

For an integer $c$, repeated multiplicativity of the determinant, with the inverse identity for negative powers, givesFor an arbitrary real $c$, an invertible real matrix does not by itself define a unique real matrix power. For example, the scalar matrix $(-1)$ has no real square root. If a matrix logarithm $L$ has been chosen with $e^L=A$ and $A^c$ is defined as $e^{cL}$, the matrix exponential determinant identity gives the precise formulaThis cannot always be replaced by an independently chosen scalar branch of $(\det A{)}^c$. For instance, $A=-I_2$ has the complex square root $i{I}_2$, whose determinant is $-1$, while the principal scalar square root of $\det A=1$ is $+1$. For a positive-definite symmetric matrix with its usual positive spectral power, all eigenvalues are positive and the familiar formula $(\det A{)}^c$ holds for every real $c$.

A power of a diagonal matrix acts entrywise. ThusFrom $A=BD{B}^{-1}$, adjacent $B^{-1}B$ factors cancel in repeated multiplication, givingThis is the matrix power rule for a similarity transformation, proved directly rather than by taking powers of separate noncommuting factors.

In the matrix product, $(AB{)}_{ij}={\sum }_{k=1}^n{a}_{ik}{b}_{kj}$. A nonzero summand in a product of upper triangular matrices requires both $i\le k$ and $k\le j$. If $i>j$, no such index exists, so the product is upper triangular. If $i=j$, only $k=i$ survives, givingThis also shows inductively why the diagonal of an integer matrix power consists of the corresponding powers of the diagonal entries.

For two upper triangular matrices and $i>j$,Indeed a potentially nonzero factor $A_{ik}$ requires $k\ge i$, while a potentially nonzero $B_{kj}$ requires $k\le j$. These requirements cannot both hold when $i>j$. Thus their matrix product is upper triangular.

Direct matrix multiplication for the given $A$ givesAdding $A^3+A^2-A$ yields $I$, so $A(A^2+A-I)=(A^2+A-I)A=I$. HenceEvery nonnegative matrix power is in $\mathrm{span}\{I,A,A^2\}$: reduce powers of degree at least three using $A^3=-A^2+A+I$. More formally, repeated reduction shows that products of any two polynomials of degree at most two in $A$ again lie in this span. Since $A^{-1}$ also lies in it, positive powers of $A^{-1}$ prove the same assertion for all negative integers. This is an instance of the integer powers for an annihilating polynomial with roots one and minus one, because $A^3+A^2-A-I=(A-I)(A+I{)}^2=0$.

To find the required entries for every integer, use the block upper-triangular structure. The top-left entry of $A^n$ is $1$ for positive and negative powers. Its lower-right block isThe identity $(I_2-N{)}^n=I_2-nN$ holds for all integers: multiplication adds the coefficients of $N$, and $(I_2-N{)}^{-1}=I_2+N$ proves the negative cases. ThereforeWrite $s=(-1{)}^n$ and $A^n={\alpha }_n{A}^2+{\beta }_{n}A+{\gamma }_{n}I$. Comparing those three entries givesSubtracting the first two equations finds ${\beta }_n$; the third then finds ${\alpha }_n$, and the first finds ${\gamma }_n$. The unique solution isFor clarity, substituting also gives the full matrix power

Each QR decomposition $A_k=Q_k{R}_k$ givesInduction therefore yields the first Accumulated QR factorization identity:

We next prove the corresponding factorization of a matrix power. The case $k=0$ is just $A=Q_0{R}_0$. Ifthen the similarity formula above impliesConsequently,The product ${\overline{Q}}_k$ is orthogonal, and the product ${\overline{R}}_k$ is upper triangular. Henceis a QR decomposition.

Successive substitution in the matrix recurrence relation gives $V_k=V_0{Q}^k$. In the matrix power of $Q=ED{E}^{-1}$, every adjacent $E^{-1}E$ cancels, so $Q^k=E{D}^k{E}^{-1}$. ConsequentlyHere $D^k=\mathrm{diag}({\lambda }_1^k,\dots ,{\lambda }_n^k)$ for $k\ge 1$, and $D^0=I$. The formula also gives $V_0$ correctly at $k=0$.