# A Test Matrix for an Inverse Eigenvalue Problem

Authors: G. M. L. Gladwell; T. H. Jones; N. B. Willms
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We present a real symmetric tridiagonal matrix of ordern whose eigenvalues are {
2
k
}
k
=
0
n
-
1 which also satisfies the additional condition that its leading principle submatrix has a uniformly interlaced spectrum, {
2
l
+
1
}
l
=
0
n
-
2.  The matrix entries are explicit functions of the size n, and so the matrix can be used as a test matrix for eigenproblems, both forward and inverse.  An explicit solution of a spring-mass inverse problem incorporating the test matrix is provided.


---

## Body

## 1. Introduction

We are motivated by the following inverse eigenvalue problem first studied by Hochstadt in 1967 [1]. Given two strictly interlaced sequences of real values,
(1)
(
λ
i
)
1
n
,
(
λ
i
o
)
1
n
-
1
,
with
(2)
λ
1
<
λ
1
o
<
λ
2
<
λ
2
o
<
⋯
<
λ
n
-
1
<
λ
n
-
1
o
<
λ
n
,
find the n
×
n, real, symmetric, and tridiagonal matrix, B, such that λ
(
B
)
=
(
λ
i
)
1
n are the eigenvalues of B, while λ
(
B
o
)
=
(
λ
i
o
)
1
n
-
1 are the eigenvalues of the leading principal submatrix of B, where B
o is obtained from B by deleting the last row and column. The condition on the dataset (2) is both necessary and sufficient for the existence of a unique Jacobian matrix solution to the problem (see [2], Section 4.3 or [3], Section 1.2 for a history of the problem and Section 3 of this paper for additional background theory).A number of different constructive procedures to produce the exact solution of this inverse problem have been developed [4–9], but none provide an explicit characterization of the entries of the solution matrix, B, in terms of the dataset (2). Computer implementation of these procedures introduces floating point error and associated numerical stability issues. Loss of significant figures due to accumulation of round-off error makes some of the known solution procedures undesirable. Determining the extent of round-off error in the numerical solution, B
^, computed from a given dataset requiresa priori knowledge of the exact solution B. In the absence of this knowledge, an additional numerical computation of the forward problem to find the spectra λ
(
B
^
) and λ
(
B
^
o
) allows comparison to the original data.Test matrices, with known entries and known spectra, are therefore helpful in comparing the efficacy of the various solution algorithms in regard to stability. It is particularly helpful when test matrices can be produced at arbitrary size. However some existent test matrices given as a function of matrix sizen suffer the following trait: when ordered by size, the minimum spacing between consecutive eigenvalues is a decreasing function ofn. This trait is potentially undesirable since the reciprocal of this minimum separation between eigenvalues can be thought of as a condition number on the sensitivity of the eigenvectors (invariant subspaces) to perturbation (see [10], Theorem 8.1
.
12). Some of the algorithms for the inverse problem seem to suffer from this form of ill-conditioning. From a motivation to avoid confounding the numerical stability issue with potential increased ill-conditioning of the dataset as a function of n, the authors developed a test matrix which has equally spaced and uniformly interlaced simple eigenvalues.In Section2 we provide the explicit entries of such a matrix, A
(
n
). We claim that its eigenvalues are equally spaced as
(3)
λ
(
A
(
n
)
)
=
{
0,2
,
4
,
…
,
2
n
-
2
}
,
while its leading principal submatrix A
o
(
n
) has eigenvalues uniformly interlaced with those of A
(
n
), namely,
(4)
λ
(
A
o
(
n
)
)
=
{
1,3
,
5
,
…
,
2
n
-
3
}
.
A short proof verifies the claims. In Section 3 we present some background theory concerning Jacobian matrices, and in Section 4 we apply our test matrix to a model of a physical spring-mass system, an application which leads naturally to Jacobian matrices.


## 2. Main Result

LetA
(
n
) be an n
×
n real symmetric tridiagonal matrix with entries
(5)
a
i
i
=
n
-
1
,
i
=
1,2
,
…
,
n
a
i
,
i
+
1
=
1
2
i
(
2
n
-
i
-
1
)
,
i
=
1,2
,
…
,
n
-
2
a
n
-
1
,
n
=
n
(
n
-
1
)
2
and let A
o
(
n
) be the principal submatrix of A
(
n
), that is, the (
n
-
1
)
×
(
n
-
1
) matrix obtained from A
(
n
) by deleting the last row and column.Theorem 1.
A
(
n
) has eigenvalues {
0,2
,
…
,
2
n
-
2
} and A
o
(
n
) has eigenvalues {
1,3
,
…
,
2
n
-
3
}.Proof.
By induction, whenn
=
2
(6)
A
(
2
)
=
[
1
1
1
1
]
has eigenvalues 0,2, and A
o
(
2
) has eigenvalue 1. Assume the result holds for n. So A
(
n
) has eigenvalues {
0,2
,
…
,
2
n
-
2
}. Let B
=
A
o
(
n
+
1
)
-
n
I and A
=
A
(
n
)
-
(
n
-
1
)
I. Then B and A are similar via B
R
=
R
A where R is upper triangular, with entries
(7)
r
i
j
=
{
k
(
j
-
1
)
!
(
2
n
-
j
-
1
)
!
(
i
-
1
)
!
(
2
n
-
i
+
1
)
!
i
,
j
have
same
parity
and
j
≥
i
,
0
otherwise
,
(8)
k
=
{
2
j
≠
n
,
1
j
=
n
.
Therefore A
o
(
n
+
1
) has eigenvalues {
1,3
,
…
,
2
n
-
1
}.
Now we show thatA
(
n
+
1
) has eigenvalues {
2
n
}
∪
{
eigenvalues
of
A
(
n
)
}. Let C
=
A
(
n
+
1
)
-
2
n
I. Factorize C
=
-
L
L
T, where L is lower bidiagonal. We find
(9)
l
i
i
=
2
n
-
i
+
1
2
;
l
i
+
1
,
i
=
-
i
2
,
i
=
1,2
,
…
,
n
-
1
,
l
n
n
=
n
+
1
2
;
l
n
+
1
,
n
=
-
n
;
l
n
+
1
,
n
+
1
=
0
.
Therefore C has eigenvalue 0 and thus A
(
n
+
1
) has eigenvalue 2
n.
DefineD
=
2
n
I
-
L
T
L; so
(10)
D
=
[
D
o
O
O
2
n
]
with
(11)
d
i
i
=
2
n
-
1
2
;
d
i
+
1
,
i
=
1
2
i
(
2
n
-
i
)
,
i
=
1,2
,
…
,
n
-
1
,
d
n
n
=
n
-
1
2
.
Now D
o has the same eigenvalues as A
(
n
) since they are similar matrices via S
D
o
=
A
(
n
)
S where S is upper triangular with entries
(12)
s
i
i
=
2
n
-
i
;
s
i
,
i
+
1
=
-
i
,
i
=
1,2
,
…
,
n
-
1
,
s
n
n
=
2
n
;
s
i
j
=
0
,
otherwise
.
Therefore A
(
n
+
1
) has eigenvalues {
2
n
}
∪
{
eigenvalues
of
A
(
n
)
}.


## 3. Discussion

A real, symmetricn
×
n tridiagonal matrix B is called aJacobian matrix when its off-diagonal elements are nonzero ([2], page 46). We write
(13)
B
=
[
a
1
-
b
1
0
0
⋯
0
-
b
1
a
2
-
b
2
0
⋯
0
0
-
b
2
a
3
-
b
3
⋱
⋮
0
0
⋱
⋱
⋱
0
⋮
⋮
⋱
-
b
n
-
2
a
n
-
1
-
b
n
-
1
0
0
⋯
0
-
b
n
-
1
a
n
]
.
The similarity transformation, B
^
=
S
-
1
B
S, where S
=
S
-
1 is the alternating sign matrix, S
=
diag
⁡
(
1
,
-
1,1
,
-
1
,
…
,
(
-
1
)
n
-
1
), produces a Jacobian matrix B
^ with entries same as B except for the sign of the off-diagonal elements, which are all reversed. If instead we use the self-inverse sign matrix, S
(
m
)
=
diag
⁡
(
1,1
,
…
,
1
︸
m
,
-
1
,
-
1
,
…
,
-
1
︷
n
-
m
), to transform B, then B
^ is a Jacobian matrix identical to B except for a switched sign on the m
th off-diagonal element. In regard to the spectrum of the matrix, there is therefore no loss of generality in accepting the convention that a Jacobian matrix is expressed with negative off-diagonal elements; that is, b
i
>
0, for
all
i
=
1
,
…
,
n
-
1in (13).While Cauchy’s interlace theorem [11] guarantees that the eigenvalues of any square, real, symmetric (or even Hermitian) matrix will interlace those of its leading (or trailing) principal submatrix, the interlacing cannot be strict, in general [12]. However, specializing to the case of Jacobian matrices restricts the interlacing to strict inequalities. That is, Jacobian matrices possess distinct eigenvalues, and the eigenvalues of the leading (or trailing) principal submatrix are also distinct and strictly interlace those of the original matrix (see [2], Theorems 3.1
.
3 and 3.1
.
4. See also [10] exercise P8.4.1, page 475: when a tridiagonal matrix has algebraically multiple eigenvalues, the matrix fails to be Jacobian). The inverse problem is also well-posed: there is a unique (up to the signs of the off-diagonal elements) Jacobian matrix B having given spectra specified as per (2) (see [2], Theorem 4.2
.
1, noting that the interlaced spectrum of n
-
1 eigenvalues (
λ
o
)
1
n
-
1 can be used to calculate the last components of each of thenorthonormalized eigenvectors of B via equation 4.3
.
31). Therefore, the matrix A
(
n
) in Theorem 1 is the unique Jacobian matrix with eigenvalues equally spaced by two, starting with smallest eigenvalue zero, whose leading principal submatrix has eigenvalues also equally spaced by two, starting with smallest eigenvalue one.As a consequence of the theorem, we now have the following.Corollary 2.
The eigenvalues of the real, symmetricn
×
n tridiagonal matrix(14)
W
n
=
[
a
-
c
n
-
1
2
0
0
⋯
0
-
c
n
-
1
2
a
-
c
2
n
-
3
2
0
⋯
0
0
-
c
2
n
-
3
2
a
-
c
3
n
-
6
2
⋱
⋮
0
0
⋱
⋱
⋱
0
⋮
⋮
⋱
-
c
(
n
-
2
)
(
n
+
1
)
4
a
-
c
n
(
n
-
1
)
2
0
0
⋯
0
-
c
n
(
n
-
1
)
2
a
]form the arithmetic sequence,
(15)
λ
(
W
n
)
=
{
a
o
+
2
c
(
i
-
1
)
}
i
=
1
n
,
while the eigenvalues of its leading principal submatrix, W
n
o, form the uniformly interlaced sequence
(16)
λ
(
W
n
o
)
=
{
a
o
+
c
+
2
c
(
i
-
1
)
}
i
=
1
n
-
1
,
h
h
h
h
h
h
w
h
e
r
e
a
=
a
o
+
c
(
n
-
1
)
.The form and properties ofW
n were first hypothesised by the third author while programming Fortran algorithms to reconstruct band matrices from spectral data [3]. Initial attempts to prove the spectral properties of W
n by both he and his graduate supervisor (the first author) failed. Later, the first author produced the short induction argument of Theorem 1, in July 1996. Alas, the fax on which the argument was communicated to the third author was lost in a cross-border academic move, and so the matter languished until recently. In summer of 2013, the second and third authors assigned the problem of this paper as a summer undergraduate research project, “hypothesize, and then verify, if possible, the explicit entries of an n
×
n symmetric, tridiagonal matrix with eigenvalues (15), such that the eigenvalues of its principal submatrix are (16).” Meanwhile the misplaced fax from the first author’s proof was found during an office cleaning. The student, A. De Serre-Rothney, was able to complete both parts of the problem. His proof is now found in [13]. Though longer than the one presented here, his proof utilizes the spectral properties of another tridiagonal (nonsymmetric) matrix, the so-calledKac-Sylvester matrix, K
n, of size (
n
+
1
)
×
(
n
+
1
), with eigenvalues λ
(
K
n
)
=
{
2
k
-
n
}
k
=
0
n [14–17]:
(17)
K
n
=
[
n
n
-
1
0
0
⋯
0
1
n
n
-
2
0
⋯
0
0
2
n
n
-
3
⋱
⋮
0
0
⋱
⋱
⋱
0
⋮
⋮
⋱
n
-
2
n
1
0
0
⋯
0
n
-
1
n
]
.The referee has pointed out the connection between the spectra (3) and (4) and the classical orthogonal Hahn polynomials of a discrete variable [18]. Using (3) as nodes with weights
(18)
ω
i
-
1
=
∏
j
=
1
n
-
1
(
λ
i
-
λ
j
o
)
∏
1
≤
j
≤
n
,
j
≠
i
n
(
λ
i
-
λ
j
)
,
i
=
1
,
…
,
n
,
determine the Hahn polynomials, h
k
-
1
/
2
,
-
1
/
2
(
x
/
2
,
n
), k
=
0,1
,
…
,
n
-
1, whose three-term recurrence coefficients are the entries of a Jacobi matrix with eigenvalues (3), hence similar to our A
(
n
).


## 4. A Spring-Mass Model Problem

One simple problem where symmetric tridiagonal matrices arise naturally is the inverse problem for the spring-mass system shown in Figure1. In this case the squares of the natural frequencies of free vibration for system (a) are the eigenvalues of a Jacobi matrix B, while those for system (b) are the eigenvalues of its principal minor B
o.Spring-mass system: (a) right hand end free, (b) right hand end fixed.
(a)
(b)Specifically, letC be the stiffness matrix, and let M be the mass (inertia) matrix for the system in Figure 1(a):
(19)
C
=
[
k
1
+
k
2
-
k
2
-
k
2
k
2
+
k
3
-
k
3
·
·
·
-
k
n
-
1
k
n
-
1
+
k
n
-
k
n
-
k
n
k
n
]
,
M
=
[
m
1
m
2
·
m
n
-
1
m
n
]
.Then the squares of the natural frequencies of the systems in Figure1 satisfy (
C
-
λ
M
)
x
=
0 and (
C
o
-
λ
o
M
o
)
x
o
=
0, where C
o is obtained from C by deleting the last row and column. The solutions can be ordered 0
<
λ
1
<
λ
1
0
<
λ
2
<
⋯
<
λ
n
-
1
<
λ
n
-
1
o
<
λ
n. We can also rewrite the systems as (
B
-
λ
I
)
u
=
0 and (
B
o
-
λ
o
I
)
u
o
=
0 where B
=
M
-
1
/
2
C
M
-
1
/
2 and u
=
M
1
/
2
x. Note that the squares of the natural frequencies of the systems are the eigenvalues of B and B
o.Suppose that the matrixB
(
n
)
:
=
A
(
n
)
+
I was to arise from a spring-mass system like in Figure 1; that is, we are considering the system whose squares of the natural frequencies are the equally spaced values {
1,3
,
…
,
2
n
-
1
} for system (a) and {
2,4
,
…
,
2
n
-
2
} for system (b). The system in Figure 1 is the simplest possible discrete model for a rod vibrating in longitudinal motion and more closely approximates the continuous system as n
→
∞. In a physical system, we expect clustering of frequencies. The test matrix B
(
n
) does not share this phenomenon and so we expect the stiffnesses and masses associated with it to become unrealistic as n
→
∞. To demonstrate this, we will explicitly solve for the stiffnesses and masses associated with B
(
n
).WithB
(
n
)
=
A
(
n
)
+
I we note that
(20)
B
i
i
=
a
i
=
n
,
i
=
1
,
…
,
n
B
i
,
i
+
1
=
-
b
i
=
-
1
2
i
(
2
n
-
i
-
1
)
,
i
=
1
,
…
n
-
2
B
n
-
1
,
n
=
-
b
n
-
1
=
-
n
(
n
-
1
)
2
with eigenvalues {
2
k
+
1
}
k
=
0
n
-
1, while B
o
(
n
) has eigenvalues {
2
k
}
k
=
1
n
-
1.Letu
=
〈
m
1
1
/
2
,
…
,
m
n
1
/
2
〉
T with m
i
>
0 for all i. Let m
=
∑
i
=
1
n
m
i
=
u
T
u. We wish to solve
(21)
B
(
n
)
u
=
〈
m
1
-
1
/
2
k
i
,
0
,
…
,
0
〉
T
for (
m
i
)
i
=
1
n andk
1.The bottom,n
th, equation is
(22)
m
n
-
1
1
/
2
=
-
n
m
n
1
/
2
-
b
n
-
1
=
2
(
n
n
-
1
)
1
/
2
α
,
where we choose m
n
1
/
2
=
α. We will thus be able to express m
i
1
/
2 in terms of the scaling parameter α.The(
n
-
1
)
th equation is
(23)
m
n
-
2
1
/
2
=
α
b
n
-
1
-
n
m
n
1
/
2
-
b
n
-
2
=
α
n
(
n
-
1
)
/
2
-
n
2
n
/
(
n
-
1
)
-
(
1
/
2
)
(
n
-
2
)
(
n
+
1
)
=
α
2
(
n
(
n
+
1
)
(
n
-
1
)
(
n
-
2
)
)
1
/
2
.Thei
th equation, for i
≠
1, n
-
1, n, is
(24)
-
b
i
-
1
m
m
-
i
1
/
2
+
n
m
i
1
/
2
-
b
i
m
i
+
1
1
/
2
=
0
.
Then
(25)
m
i
-
1
1
/
2
=
2
n
m
i
1
/
2
-
(
i
(
2
n
-
i
-
1
)
)
1
/
2
m
i
+
1
1
/
2
(
(
i
-
1
)
(
2
n
-
i
)
)
1
/
2
.Now suppose(26)
m
n
-
i
1
/
2
=
α
2
(
n
(
n
+
1
)
⋯
(
n
+
i
-
1
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
i
)
)
1
/
2
for i
=
1,2
,
…
,
j. Then cases i
=
1,2 are already verified, and the strong inductive assumption applied in (25) with i
-
1
=
n
-
(
j
+
1
) implies i
=
n
-
j. So
(27)
m
n
-
j
-
1
=
(
2
n
α
2
(
n
(
n
+
1
)
⋯
(
n
+
j
-
1
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
j
)
)
1
/
2
V
V
-
(
(
n
-
j
)
(
n
+
j
-
1
)
)
1
/
2
m
n
-
j
+
1
1
/
2
n
(
n
+
1
)
⋯
(
n
+
j
-
1
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
j
)
)
×
(
(
(
n
-
j
-
1
)
(
n
+
j
)
)
1
/
2
)
-
1
=
α
2
(
n
(
n
+
1
)
⋯
(
n
+
j
-
1
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
j
)
)
1
/
2
×
[
(
j
)
1
/
2
)
-
1
(
2
n
(
n
+
j
-
1
n
-
j
)
1
/
2
VV
V
V
-
(
(
n
-
j
)
(
n
+
j
-
1
)
)
1
/
2
(
n
+
j
-
1
n
-
j
)
1
/
2
)
V
V
×
(
(
(
n
-
j
-
1
)
(
n
+
j
)
)
1
/
2
)
-
1
(
n
+
j
-
1
n
-
j
)
1
/
2
]
=
α
2
(
n
(
n
+
1
)
⋯
(
n
+
j
-
1
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
j
)
)
1
/
2
×
[
2
n
-
(
n
-
j
)
(
(
n
-
j
-
1
)
(
n
+
j
)
)
1
/
2
]
=
α
2
(
n
(
n
+
1
)
⋯
(
n
+
j
-
1
)
(
n
+
j
)
(
n
-
1
)
(
n
-
2
)
⋯
(
n
-
j
)
(
n
-
j
-
1
)
)
1
/
2
which verifies, by strong induction, the closed form for m
n
-
i
1
/
2 given by (26).Finally, the first equation of (21) is
(28)
n
m
1
1
/
2
-
b
1
m
2
1
/
2
=
m
1
-
1
/
2
k
1
and so
(29)
k
1
=
n
m
1
-
b
1
(
m
1
m
2
)
1
/
2
.We note that the valuesm
n
-
i can be written as
(30)
m
n
-
i
=
2
α
2
(
n
+
i
-
1
)
!
(
n
-
i
-
1
)
!
(
(
n
-
1
)
!
)
2
for i
=
1
,
…
,
n
-
1, and
(31)
m
n
=
α
2
(
n
+
0
-
1
)
!
(
n
-
0
-
1
)
!
(
(
n
-
1
)
!
)
2
=
α
2
.SinceC
=
M
1
/
2
B
(
n
)
M
1
/
2, then
(32)
k
i
+
1
=
-
C
i
,
i
+
1
=
-
m
n
-
(
n
-
i
)
1
/
2
B
i
,
i
+
1
m
n
-
(
n
-
i
-
1
)
1
/
2
=
α
2
(
i
!
(
2
n
-
i
-
1
)
!
(
(
n
-
1
)
!
)
2
)
,
(33)
k
1
=
α
2
(
2
n
-
1
)
!
(
(
n
-
1
)
!
)
2
.From (26) we have m
1
/
m
n
=
2
(
(
2
n
-
2
)
!
/
(
(
n
-
1
)
!
)
2
)which goes to infinity as n
→
∞ and from (32) we see that k
1
/
k
n
=
(
2
n
-
1
)
!
/
(
n
-
1
)
!
n
! which also goes to infinity as n
→
∞. This is not a model of a physical rod, as expected.


## 5. Conclusion

A family ofn
×
n symmetric tridiagonal matrices, W
n, whose eigenvalues are simple and uniformly spaced and whose leading principle submatrix has uniformly interlaced, simple eigenvalues has been presented (14). Members of the family are characterized by a specified smallest eigenvalue a
o and gap size c between eigenvalues. The matrices are termedJacobian, since the off-diagonal entries are all nonzero. The matrix entries are explicit functions of the size n, a
o, and c; so the matrices can be used as a test matrices for eigenproblems, both forward and inverse. The matrix W
n for specified smallest eigenvalue a
o and gap c is unique up to the signs of the off-diagonal elements.In Section4, the form of W
n was used as an explicit solution of a spring-mass vibration model (Figure 1), and the inverse problem to determine the lumped masses and spring stiffnesses was solved explicitly. Both the lumped masses m
n
-
i given by (30) and spring stiffnesses k
n
-
i from (32) show superexponential growth. Consequently m
n
/
m
1, k
n
/
k
1 become vanishingly small as n
→
∞. As a result, the spring-mass system of Figure 1 cannot be used as a discretized model for a physical rod in longitudinal vibration, as the model becomes unrealistic in the limit as n
→
∞.



---

*Source: 515082-2014-05-26.xml*