OnLine Geometric Modeling Notes
EIGENVALUES AND EIGENVECTORS
OF THE
REFINEMENT MATRIX
Overview
The basic operation in the development of
subdivision curves is the refinement
procedure. In the cubic case, the
points of the refinement can be specified as vertex
and edge
points
and the refinement procedure can be specified by a matrix operation.
In this case the refinement matrix
is defined to be
In these notes, we develop the eigenvalues and eigenvectors of the
refinement matrix which play an important role in the analysis of
subdivision curves. This matrix is also diagonalizable and we use the
eigenvalues and eigenvectors to calculate this
diagonal decomposition.
Finally, the diagonal decomposition allows an easy calculation of the
inverse of the matrix.
For a pdf version of these notes look
here
The Eigenvalues of the Refinement Matrix
One of the eigenvalues is easy to calculate.
Since the rows of
all sum to one, we have
and so
is an eigenvalue
of , with corresponding
eigenvector
.
The other eigenvalues can be calculated from the
characteristic polynomial
and turn out to be
and
.
The (right) eigenvectors
for the
eigenvalues
can be calculated to be
respectively, and in a similar fashion
the left eigenvectors
turn out to be
Diagonalization of the Matrix
We will let
be the
matrix whose rows are the
left eigenvectors
of ,
and
be the
matrix whose columns
are the right eigenvectors
of ,
noting that
Then since the
matrix
has 3 distinct eigenvalues, it is
diagonalizable
[1]
and can be written as
where
is the diagonal matrix whose diagonal elements are
the eigenvalues of .
The Inverse of the Refinement Matrix
Since the refinement matrix can be written as
, it is
easy to generate the inverse of .
since . The matrix
is just
The inverse of
then works out to be
Summary
The eigenvalues and eigenvectors of the refinement matrix are
straightforward to calculate. Since this matrix is well conditioned
it can be diagonalized and written in form
which will be
very useful when analyzing subdivision curves.
 1

GOLUB, G. H., AND VAN LOAN, C. F.
Matrix Computations, 2nd ed.
Johns Hopkins University Press, 1989.
 2

HALSTEAD, M., KASS, M., AND DEROSE, T.
Efficient, fair interpolation using CatmullClark surfaces.
In Computer Graphics (SIGGRAPH '93 Proceedings) (Aug. 1993),
J. T. Kajiya, Ed., vol. 27, pp. 3544.
Ken Joy
20001128