QR Factorisation

Recall that a matrix Q є Mn is orthogonal if QQT = I = QTQ. If A є Mn is non-singular, then it may be factorised in the form A = QR, where Q is orthogonal, and R is upper triangular with positive diagonal terms. This factorisation is equivalent to the Gram-Schmidt process in which the columns of A are expressed as linear combinations of orthonormal vectors q;-, the columns of Q.

QR factorisation gives us a procedure for getting another matrix, A*, isospectral to A:if A = QR, then A* = RQ may be written A* = QT(QR)Q = QTAQ : A* is orthogonally equivalent to A. If A is symmetric, so that AT = A, then (A*)T = (QTAQ)T = QTATQ = QTAQ = A* : A* is symmetric; A and A* are isospectral.

We can apply QR ^ RQ transformation with a shift. Suppose p is not an eigenvalue of A є Sn, write

A — pI = QR (5)

and construct A* from

A* — pI = RQ. (6)

Again, A* = pI + RQ = QT(pI + QR)Q = QTAQ, so that A and A* are isospectral; we write A* = Gp(A).

The simplest application of this result is to isospectral in-line spring-mass systems. Now K is a Jacobi matrix with negative off-diagonal and M is diagonal: M = diag(m, m2,…, mn). We write M = P2, where P = diag(p1, p2,…, pn); Equation (1) may be written

P—1(K — XP2)P—1Pu = 0,


(A — A!)x = 0, A = P—1KP—1, x = Pu.

The matrix A is a Jacobi matrix with negative off-diagonal. We form A* from (5), (6) and then factorise A* in the form A* = P*—XK*P*—1 to obtain a new in-line spring-mass system. The details of the analysis may be found in Gladwell (1995). The extension to a system in which K, M are both Jacobi matrices, with negative, positive off-diagonals respectively, may be found in Gladwell (1999).

This application depends on the fact that the operation Gp defined by (5), (6) changes a Jacobi matrix A with negative (positive) off-diagonal into a Jacobi matrix A* with negative (positive) off – diagonal. It may be verified that A* is PD (PSD) iff A is PD (PSD). This is a special case of a general result, proved in Gladwell (1998): Suppose A є Sn, and p is not an eigenvalue of A (both these conditions are necessary), then A, A* have the same staircase pattern, and A* is TP, NTN, O or SO, iff A is TP, NTN, O or SO, respectively.

This general result may be used to find an isospectral family of FEM models of a thin straight rod in longitudinal vibration. Now K, M are Jacobi matrices with negative, positive, off-diagonals respectively. We start from Equation (1), factorise M = BBT where B is a bi-diagonal upper triangle matrix, and reduce (1) to standard form

(B-tKB-T – XI)BTu = 0.

It may be shown that A = B-tKB-T is SO. We find A* = GP(A), and then factorise A* = B*-tK*B*-T to form a new FEM model, K*, M* with M* = B*B*T; K*, M*, like K, M are Jacobi matrices with negative, positive, off-diagonals respectively, corresponding to a FEM model of a new rod, as described in Gladwell (1997).

The operation is essentially tied to staircase matrices: A* is a staircase iff A is a staircase. To obtain a wider class of isospectral matrices, we must consider the concept of isospectral flow.