Received 24 March 2015; accepted 6 June 2015; published 9 June 2015

ABSTRACT

In this article, we determine the Eigen values and Eigen vectors of a square matrix by a new approach. This considers all the roots with their multiplicities are known, using only the simple matrix multiplication of a vector. This process does not even require matrix inversion.

Keywords:

Characteristic Equation, Minimal Polynomia, Eigen Values, Eigen Vectors, Vander Monde Matrices, Jordan Reduction

1. Introduction

There are many algorithms to determine the Eigen values and Eigen vectors of a square matrix [1] -[4] . Basically they are iterative, they either determine sequentially the largest Eigen values and associated Eigen vectors, or as in the case of positive definite matrices go for simultaneous iterative determination of all Eigen values and Eigen vectors by a succession of orthogonal transformations [1] [3] . Also, when one has multiple roots, the usual iterative approaches generally fail to work, unless additional properties of Eigen vectors of repeated roots are exploited. However, it is theoretically possible (and hence, in practice achievable with some success) to obtain all the Eigen vectors (including the generalized Eigen vectors connected with Jordan reduction) of a matrix if all the roots with their multiplicities are known using only the simple matrix multiplication of a vector. This process does not even require matrix inversion.

In what follows, we shall present the procedure through illustrative examples. Since the theory behind it is rather simple and becomes almost obvious once the way is pointed out, we shall not prove any result. Rather we shall only state a relevant new theorem in matrix theory. Implication of this theorem and its extensions in the general contexts are dealt with in a separate study.

2. Basic Points

To place the results of the present paper in a proper perspective, it is necessary to make the following points explicit before going to the theorem.

1) This procedure does require the knowledge of minimal polynomial [5] and the numerical value of the Eigen value for which the Eigen vector is to be obtained.

2) The only matrix operation involved in obtaining the Eigen vector is multiplication of a matrix and a vector.

3) One can obtain, with equal ease, the Eigen vectors for each known root, including the generalized vectors for multiple roots when they exist. In other words, Eigen vectors can be obtained for each value by itself without needing to determine either other root or the associated vectors.

4) When a multiple Eigen root has many roots, one can get them all by starting with different initial vectors.

® For convenience, we shall employ the following convention and notations:

a) A is a square matrix of order n with Eigen roots; unless stated otherwise, they are all assumed to be distinct.

b) is the matrix of Eigen columns of A.

c) 1) is the initial or starting vector and,.

2) is the n by r matrix with the as its columns.

d) is the Vander Monde matrix [6] of Eigen values

is the minimal polynomial of A and is the vector of coeff- icients in in reverse order. When the are all distinct, as is being assumed for the present, this is also the characteristic polynomial with as the corres- ponding coefficient vector. Thus, in the present situation.

As is well known, with the condition, a is unique if is of full rank. This will be the case when the characteristic and minimal polynomial are identical, otherwise the class of polynomials defined by this vector will have as their H.C.F. a polynomial which has the minimal polynomial as its (possibly trivial) factor.

e) is the quotient polynomial associated with the Eigen root, with the quotient vector.

3. Main Results

We can now state the new Eigen vector theorems and their obvious extensions which are at the heart of the procedures presented in the sequel.

THEOREM 1:

Proof is easy once it is noted that and, since the Eigen

vectors in general are unique upto scale and Eigen vectors associated with different Eigen values are linearly independent, the choice of above is not restrictive; unless one is extremely unlucky (or when the Eigen vectors are highly structured, as in a subsequent illustration), any vector, which may the arbitrarily chosen one, will be linear combination of all the’s.

THEOREM 2: The vector is an Eigen vector of A associated with the Eigen

values. This theorem is illustrated by the following examples.

3.1. Illustrations

We shall now illustrate the application of the above theorems in the determination of and the Eigen vectors. Different types of situations including the case of Jordan reducible matrices and generalized Eigen vectors will be illustrated by numerical examples. These examples will be interspersed with comments as required.

3.2. Illustration 1

, , ,

Hence a, such that, is and.

Since is of order 3, we have,

and

Similarly, , and

and.

3.3. Illustration 2

, , ,

Here, is of rank 2, hence through has non-trivial solutions, there is no unique solution “a” even with the requirement. Hence one cannot obtain by this approach. However, it is possible to get by using. Thus, solving the equation with, we get and .

Hence, , where is a 1st degree polynomial, say, since, one must have the coefficient of in equal to −7. Hence, only.

And, thus, has two distinct roots and; the root is a double root and has two independent eigenvectors.

Taking and, we get ;

Taking, we get .

A second eigenvector associated with is obtainable by taking new starting vector say.

We then get, giving

and.

As is to be expected, the obtained by using the two different’s are multiples of each other.

3.4. Illustration 3

, ,

Here again rank of is 2. Hence, solving with, we get .

Since, we have.

Thus is the triple Eigen root of but has two independent Eigen vectors and one generalized Eigen vector.

One Eigen vector is got by taking

;

Defining, we get, and .

It is easily verified that is a generalized Eigen vector of A with.

To obtain a second Eigen vector for,

we start with a different, say with

The new Eigen vectors are and.

With and.

Here, and we have.

Hence defining,

We have

Thus, is a second Eigen vector of, for.

Obviously, two independent Eigen vectors say, and Z above, are not unique; they are a basis for the two dimensional vector space of Eigen vectors of A for, viz., the solutions space of the equation.

3.5. Illustration 4

With and

Since is of full rank, we get the solution vector of as

Hence. Thus, has a triple Eigen root,

But has only one Eigen vector. Defining,

and,

We get; and.

Giving, and.

As is to be expected, we have; and.

3.6. Illustration 5

, , gives

Since is of rank 4, we have solution of as,

Giving the minimal polynomial

Thus, is a triple root with two Eigen vectors and one generalized Eigen vector while is a dou- ble root with one Eigen vector and one generalized eigenvector.

Since, , , we get

, with and.

Similarly with,

We get and

With and.

Thus, we have obtained four vectors for A; one more Eigen vector is yet to be obtained corresponding to the triple Eigen value.

3.7. Case 1

With the starting we have

This is obviously of rank 2 only.

Solving the homogeneous equations X₃y = 0 we get a polynomial since is a solution. Thus we know that A has as a multiple root with a multiplicity of at least 2.

Using and we get

And and hence as generalized vector itself.

To illustrate the complexity of the situation one has to be prepared to encounter, we shall in turn present the results with five different starting vectors.

3.8. Case 2

Has rank 2. Hence, and

3.9. Case 3

have rank 3.

Hence. i.e., is also an Eigen value of A.

Taking and and

And, we get.

3.10. Case 4

is of rank 3.

Hence. Thus A has also as repeated root of multi- plicity at least 2. Combining the information from Case 3, we see that the matrix A has and as repeated roots, each of multiplicity at least 2. Since trA = 5, it follows that is actually a triple root and is a double root of the characteristic equation of A. Since in this case also, we get etc the same as in Case 3 with as the eigenvector for, using and for and the corresponding generalized vector by taking; giving; and.

3.11. Case 5

is of rank 2,

With, confirming that is at least a double root.

Taking and, we get and with,.

It is also instructive to examine the result of multiplication of an X matrix with the coefficient vector got by dividing the characteristic polynomial by any of its factors. With the of Case 5, taking, we get, the generalized vector for; taking we get, the Eigen vector for. It can also be verified that if is constructed using as the starting vector and is taken as and respectively, we get, the Eigen vector for and. This behavior is decided by the composition of in terms of s.

For the matrix A, we have one representation as

In Case 5, we have and by X from this initial vector, we can only get and. If has as a factor, the corresponding vector will be zero vector. If it has but not as a factor, then u will be an Eigen vector for while, if has only factors of other than, it will be a generalized Eigen vector associated with.

Similarly, in Case 2, we have, for which the associated Eigen root is, with multiplicity 3 but with only one super diagonal unity and hence and are eigenvectors for while is a generalized eigenvector.

Hence, as is to be expected, the X for this case viz,

Is of rank 2, giving with, the polynomial Any factor of which in- cludes gives the;

Any Q which includes only as a factor gives a V which is an Eigen vector for while any Q which has no factor at all gives a generalized vector of A for.

These results, of course, are the consequences of the second Eigen vector theorem presented elsewhere.

4. Summary

Some general observations regarding the problem of determining the Eigen values and corresponding Eigen vectors of a matrix are now in order. Though, theoretically obvious, significance of the procedure presented above in the case of computation of the same perhaps needs to be reiterated. However, in the present study we have not gone into the important questions regarding the approximations in practical computations and effect of consequent noise on the final results observed.

1) If one has the ability to solve a set of linear equations, one can obtain the characteristic polynomial of a matrix provided, it is also the minimal polynomial. This fact is, of course, well known. However, the same is true regarding the determination of minimal polynomial in general.

In the above notation, we compute sequentially the ranks of. Let k be the smallest integer such that. Then, the minimal polynomial of degree k and its coefficients are propor- tional to the solutions of the equation.

This is the case when is a nontrivial linear combination of all generalized Eigen vectors and one each of Eigen vectors connected with the Eigen roots of the matrix. Otherwise, the polynomial will be a proper factor of the minimal polynomial.

If is the minimal polynomial, say then A has k distinct Eigen values viz, , , with a minimum multiplicity of. However, since the minimal polynomial will have every root of as its root as well, it follows that where. Also, will have independent Eigen vectors and generalized Eigen vectors. Also, by using information on the trace of A, one can, by solving appropriate linear Diophantine equations, determine the values of s.

2) Since the highest common factors of a polynomial and its derivative have each of the roots of the polynomial,

multiplicity of each being reduced by 1, it follows that will have

each of the roots occurring exactly once. Hence, given, one can determine all the roots of the polynomial; their multiplicities, as noted earlier, can be determined by solving appropriate linear Diophantine equations.

3) Since real symmetric matrices are fully diagonalizable by an orthogonal matrix, their minimal polynomial will have no repeated root. This fact is of great help especially in situations where a dispersion matrix has signal Eigen values which are relatively large and possible distinct and a “noise Eigen value” which is hopefully small and will be of high multiplicity. A good estimation of the minimal polynomial will be possible with relatively less computational effort by the present approach. Using the same computational product by, one can get the Eigen vectors for these “Signal Eigen values”.

4) The present approach enables one also to tackle complex Eigen values and Eigen vectors, especially when A is real and hence Eigen values and vectors occur in conjugate pairs.

Acknowledgements

We are highly thankful to Late Prof. S. N. Narahari Pandit for suggesting this problem, we are indebted to him. The author 1, acknowledges UGC, India for financial support.

References

NOTES

^*Corresponding author.