The Simultaneous Reduction of Matrices to the Block-Triangular Form

Yuri N. Bazilevich^{*}

Department of Applied Mathematics, Prydniprovsk State Academy of Civil Engineering and Architecture, Dnipropetrovs'k, Ukraine

Abstract

The solution of the problem of several *n*´*n* matrices reduction to the same upper block-triangular form by a similarity transformation with the greatest possible number of blocks on the main diagonal is given. In addition to the well-known "method of commutative matrix" a new "method of invariant subspace" is used.

Keywords

Matrix, Block-Triangular Form, Similarity Transformation, the Centralizer, Algebra over the Field, Radical Ideal

Received: July 10, 2015

Accepted: July 25, 2015

Published online: August 8, 2015

@ 2015 The Authors. Published by American Institute of Science. This Open Access article is under the CC BY-NC license. http://creativecommons.org/licenses/by-nc/4.0/

Contents

1. Introduction 2. The General Calculation Scheme 3. The Method of Commutative Matrix 4. The Method of Invariant Subspace 4.1. Construction of Algebra 4.2. Calculation of an Algebra Radical Ideal 4.3. Finding of Invariant Subspace 4.4. Construction of the Transformation Matrix 5. The Uniqueness Theorem 6. Special Case 7. Examples 7.1. The First Example 7.2. The Second Example 7.3. The Third Example 8. Generalizations 9. Conclusion 10. Next Directions of Investigation

1. Introduction

At first, let us consider the case when the number of matrices *d* = 2.

(1)

There are two square matrices *B*_{1} and *B*_{2} over the field of complex numbers. We need to find the similarity transformation (1) reducing both matrices to the equal block-triangular form. Here is a block of matrix *B** _{n}* located in the

It is necessary that the number *l* of diagonal blocks to be the maximum possible.

The idea of the method was published in the author's monograph [1]. Corresponding computational algorithms and results of calculations on handling of applied problems are presented in papers [2,3]. In this paper a detailed theoretical basis of the developed methods is given.

There exists a solution for the case of only one matrix. One matrix can be reduced to its Jordan form. There is a famous unsolved problem — to create a canonical form for a pair of matrices. This problem and the equivalent problems are called wild problems [4].

2. The General Calculation Scheme

We use the "method of commutative matrix" and the "method of invariant subspace." The first one allows you to find the similarity transformation, reducing both matrices to a block-diagonal form with two (at least) blocks on the main diagonal, or to determine that such reduction is impossible for these matrices. The other method is intended to reduce such two matrices that are not reduced to the block-diagonal form, to a block-triangular form, or to determine that they cannot be reduced to a "strict" block-triangular form either. There is also used a method of overcoming the special case (see Section 6).

This approach is consistently applied firstly to the initial pair of matrices, then to pairs of blocks that appear on the main diagonal. The process continues until we obtain the pairs of blocks that are irreducible to the same block-triangular form. From the uniqueness theorem it follows that this approach gives the solution of the problem.

3. The Method of Commutative Matrix

Possibility of application of commutative matrix for decoupling of system of equations was described in the textbooks on quantum mechanics (for example, see the book by Fermi [5]). The method of commutative matrix as such was proposed simultaneously by A.K. Lopatin [6] and E.D. Yakubovich [7].

Let us consider set of all matrices that are commutative with matrices *B*_{1}, *B*_{2}. This set is an algebra over the field of complex numbers. is called a centralizer of matrices {*B** _{n}*}.

*Theorem 1. *Let matrices *A* and *X* be commutative:

*AХ** = ХA,*

matrix *X* has the block-diagonal form of , where the spectra of the blocks are mutually disjoint. Then the matrix *А* also has the block-diagonal form

*А =** *diag*.*

This theorem is given in [8] — Ch. VIII, Theorem 3. See also [1] § 2.5.

*Corollary.* Let a matrix exist, having at least two different eigenvalues. Let the column of matrix* S* be the vectors of canonical basis of matrix *X*. Then similarity transformation reduces both matrices to the block-diagonal form with two (at least) blocks on the main diagonal.

*Proof*. Property of matrices commutation is preserved under the similarity transformation. Indeed:

,

where *S* is the non-singular matrix.

Let the matrix *X* have at least two different eigenvalues and commute with matrices *B*_{1}, *B*_{2} and let the columns of the matrix *S *be the vectors of the canonical basis of the matrix *X*. In this case the transformation reduces matrix *X* to its Jordan form. Therefore, , where *X*_{1} is a Jordan block corresponding to the first eigenvalue of the matrix *X*, and *X*_{2} — to the second and the subsequent (if any) eigenvalues. Both blocks are not empty and they have no common eigenvalues. The matrices commute with the matrix. From Theorem 1 it follows that they have the block-diagonal form.

*Theorem 2.* If matrices *B*_{n} are reduced to the block-diagonal form with two (at least) blocks on the main diagonal by similarity transformation, then there exists a matrix with at least two different eigenvalues.

*Proof.* Let. Let us compose the matrix, where *E*_{1} and *E*_{2} are the identity matrices. Matrix commutes with *B** _{n}* and has two different eigenvalues l

So, for the simultaneous reduction of two matrices to the block-diagonal form it is necessary and sufficient that the centralizer of the matrix to contain the matrix *X* with different eigenvalues.

To find the centralizer (or more precisely — its basis), you can declare all the elements of the matrix *X* as unknown numbers and create a system of linear homogeneous algebraic equations corresponding to the matrix equations

*B*_{1}*Х* = *ХB*_{1}, *B*_{2}*Х* = *ХB*_{2}. (2)

We have 2*n*^{2} equations with *n*^{2} unknowns. If *n* is small, then general solution of this system of equations can be made by known methods. Computing method of coping with large *n* is given in [9].

Let *W*_{1}, *W*_{2},…,* **W _{r}* matrices form a basis of centralizer Λ(

We draw up a matrix of similarity transformation of the column-vectors of the canonical basis of the matrix *X*.

The special case, where *r* > 1, but all matrices of the basis do not have different eigenvalues, is discussed below (see Section 6).

4. The Method of Invariant Subspace

The idea of the method is proposed in [1] (Chapter 7).

Let us consider matrices* B** _{n}* (

4.1. Construction of Algebra

The first step of the method is the construction of algebra with unit generated by the initial matrices.** **You can do as follows [2]: firstly, we choose linearly independent elements of the matrix {*E*, *B*_{1}, *B*_{2}} and call them "assumed basis". Then we consider all the possible products of these matrices. If the next product does not belong to the linear span of the "assumed basis", we add it to this set and consider the elements products of a new "assumed basis". We continue this process until none of the products goes beyond the linear span. The indication that the element does not belong to the linear span of the "assumed basis" is that the addition of a new element gives a linearly independent set of elements. Verification of linear independence is possible using program SLAU5 [1].

The possibility of matrices reduction to the block-triangular form is equivalent to the reducibility of algebra. The criterion of reducibility of algebra: the rank of the algebra j(*В** _{n}*) is smaller than

4.2. Calculation of an Algebra Radical Ideal

*Theorem 3. *If rank *r* of algebra j(В_{n}) is smaller than *n*^{2} and if centralizer Λ(*B*_{n}) does not contain any matrix *X* with different eigenvalues, then the algebra j(*В*_{n}) is non-semisimple.

*Proof.* The condition *r* < *n*^{2} means that the algebra j(*В** _{n}*) is reducible [10,11]. A reducible algebra may be semisimple or non-semisimple. Algebra is not semisimple because the matrices (including {

A non-semisimple algebra has a nontrivial radical ideal. There are formulas to find it [11]: the coordinates a = [a_{1}, a_{2}, …, a* _{r}*]

*D*a = 0, *D* = {*d _{ij}*}, (3)

where *d _{ij}* = Sp(

The general solution of equation (3) can be obtained by known methods. You can, for example, use the program SLAU5 [1]. Consequently, it is possible to obtain a basis of radical ideal.

4.3. Finding of Invariant Subspace

Let *Z-set* be intersection of all kernels of radical ideal elements of the algebra j(*В*_{n}). We can find *Z*-set (its basis) as a general solution of the corresponding system of algebraic equations.

*Theorem 4.* *Z-set is a subspace of space .*

*Proof.** *This set can be found with only elements of the basis. The calculation corresponds to finding a solution of the system of linear homogeneous algebraic equations. The general solution of this system, as we know, is a subspace.

*Theorem 5.* If algebra is non-semisimple, then Z-set is a nontrivial subspace.

*Proof.* In this case, a non-zero radical ideal is a set of matrices , where **t** is the parameters vector. The radical ideal is a nilpotent subalgebra because all its elements are nilpotent (see [11, § 7, Theorem 2]). Hence, , . Let be nonzero matrix of the set , and — its nonzero column. Then , since . So, the equation has nontrivial solutions.

*Theorem 6.* The subspace *Z-set* is an invariant with respect to the matrices {B_{}}.

*Proof.* Radical ideal of algebra j(*В*_{}) is its ideal. Matrices are members of algebra j(*В*_{}). Hence, we obtain where , i.e. *Z*-set is invariant with respect to the set of matrices {*B _{i}*}.

Thus, for the case when the matrices are not reduced to the block-diagonal form, but the rank of the algebra j(*В*_{n}) is less than *n ^{2}*, we have a method of construction of nontrivial subspace that is invariant with respect to these matrices.

4.4. Construction of the Transformation Matrix

*Theorem 7.* The simultaneous reduction of a pair of matrices to the block-triangular form is possible if and only if there exists a nontrivial invariant with respect to both matrices subspace .

*Proof.* . Let

where are matrices of order *m*. Then the set of vectors , where , is invariant with respect to matrices , i.e. if then . Let *V* consist of all vectors of the form , . From the invariance of the matrices, it follows that. Therefore,

.

Suppose there exists a nontrivial subspace *V* that is invariant with respect to the matrices . Let be a basis of the subspace *V*. Let be its addition to the basis of . Let the columns of matrix* S* be the vectors . From the rules of matrix multiplication, it follows that the equality is an equivalent to similarity transformation , and this equality can be written as

, (4)

where are the elements of the matrix , *A* is an arbitrary matrix.

The condition of invariance of the subspace *V* means that any element of the basis after multiplication by any of the matrix remains in the subspace *V* and, therefore, is a linear combination of elements:

.

Comparing the last equality with (4) and taking into account the linear independence of vectors, we obtain, . These equations are performed at all. Consequently, the corresponding elements of matrices are equal to zero, i.e. modified matrices have the block-triangular form.

We form the transformation matrix *S* from the basis vectors of this subspace and a subspace being a direct complement to it. We locate vectors as columns (see the proof of Theorem 7).

Direct sum to the subspace can be found as a general solution **x** of the linear homogeneous algebraic equations

.

Here, T is a sign of transposition.

To find the general solution, you can use the program SLAU5 [1].

5. The Uniqueness Theorem

There is the uniqueness theorem.

*Theorem 8.* *Let the matrices , i = 1, 2, be reduced to the block-triangular form*

by some similarity transformation and further reduction for each pair of blocks {*B*_{1kk}, *B*_{2kk}} is impossible. If there exists another similarity transformation such that for the resulting blocks further reduction is impossible:

then and we can determine the correspondence between the numbers of blocks such that the blocks B_{ikk} are similar to blocks .

*Proof*. This theorem follows from Theorem of Jordan — Holder (see, also [12], Theorem 1).

6. Special Case

Let us consider the case when the basis of the centralizer contains more than one matrix (*r* > 1), but each of these matrices has no different eigenvalues. There is an assumption that in this case all the matrices of the centralizer have no different eigenvalues and, accordingly, the initial matrices are not reduced to the block-diagonal form simultaneously. It turns out that this assumption is valid if the algebra has a rank *r* ≤ 3 and is not valid if rank *r* = 4 (see [1], Theorem 6.6).

This Section shows how in this case to reduce the matrices to the block-triangular form, without discussing the possibility of reducing them to the block-diagonal form.

*Theorem 9.* If the rank of the centralizer of the matrices is greater than one: *r* >1, then the matrices are reduced to the block-triangular form.

*Proof.* Let *W*_{1},…,_{ }*W*_{r} be the basis of algebra and *W*_{1}=*E*. If *W*_{2} matrix have two (or more) different eigenvalues, then we can reduce initial matrices to the block-diagonal form by method of commutative matrix. Otherwise eigenvalue is unique. Therefore matrix is nilpotent. Matrix *G* is nilpotent and nonzero, therefore subspace is nontrivial. Besides , i.e. subspace *L* is invariant with respect of matrices *. *Consequently, we can reduce matrices to the block-triangular form in this case too (Theorem 7).

We need to create a matrix and find the vectors as the basis of kernel matrix *G* to construct the transformation matrix S. Further construction is the same as in Subsection 4.4.

*Note.* The condition is not necessary to reduce the matrices to the block-triangular form.

7. Examples

7.1. The First Example

(see [1], example 1.6).

We use the method of commutative matrix. All the elements *x _{ij}* of matrix

where *x*_{11} and *x*_{21} are free unknowns. Or in other way

If *x*_{11} = 0, *x*_{21} =1 the eigenvalues of *X* are: l_{1} = l_{2} = – 0.25; l_{3} = 0.25. Then we obtain eigenvectors of matrix *X* and build the transformation matrix

The initial matrix is reduced to the block-diagonal form:

(5)

Next, we consider the blocks For them a set of commuting matrices is a*E*, where a is an arbitrary number. So reduction of these blocks to the diagonal form is impossible (Theorem 2). We verify the possibility of reducing by the method of invariant subspace. Matrices *E*, *B*_{111} and *B*_{211} are linearly independent. Products of any of these matrices to the identity matrix *E* belong to the linear span of the first three matrices. Matrix is a member of this set too. We consider the product *U* = *B*_{111} *B*_{211}. Using the equality a*E* + b *B*_{111} + g *B*_{211} + l *U* = 0 we obtain: a = b = g = l = 0, i.e. matrix U does not belong to the linear span of the first three matrices. We obtain that *r* = 4 and the condition *r* < *n*^{2} is not performed.

Further simplification of the matrices is impossible (see Subsection 4.1). Therefore the final result is the matrices (5).

7.2. The Second Example

, (see [1], example 7.3).

Direct verification shows that the corresponding centralizer consists only of matrices . Therefore, reduction of matrices to diagonal form is impossible.

Let us build algebra . Matrices *E*, *B*_{1}, *B*_{2} are linearly independent. Let us denote these matrices* W*_{1}, *W*_{2}, *W*_{3 }respectively. Let us consider all possible products of matrices *W _{k}W_{j}* and verify whether the resulting matrices are the linear combination of the original. Since multiplication by

We have found that all products belong to the linear span of the matrices *W*_{1}, *W*_{2}, *W*_{3}. Consequently, these matrices form the basis of algebra . The number of elements of the basis *r* = 3, i.e. . This means that the reduction to triangular form is possible.

Let us compose the matrix *D* = {Sp(*W _{j}W_{k}*)}. All products

Let us form the system of equations *D*a = 0. The general solution of this system includes: *a*_{1} = –6*a*_{3}, *a*_{2} = 3a_{3}, where *a*_{3} is a free variable. Let *a*_{3} = 1. We obtain. We compute the matrix *G*: The equations are of the form: Hence: . We put: . Therefore, the basis of *Z-set* consists of one vector: . This vector and the vector are linearly independent. Therefore: . Then we obtain

; ;

;

7.3. The Third Example

. These matrices describe the motion of the system from [13].

It is clear, that we can reduce the matrix *B*_{2} to its Jordan form. But let us consider the approach set forth above.

Let us find matrix *X* that commutes with the initial matrices. As a result of calculations we obtain:* X *= a*E*, where a is an arbitrary parameter. Since matrix *X* has no different eigenvalues, reduction of the initial matrices to the block-diagonal form is impossible.

Next, we use the method of invariant subspace.

We act as in the previous example. We obtain: *r* = 2. The condition is performed. Next: *D *= *.*

The system of equations *D*y* *= 0 takes the form: 2*y*_{1} + 2*y*_{2} = 0*, *2*y*_{1} + 2*y*_{2} = 0. As a result, we obtain: **y **= . Basis of radical ideal is a matrix

*.*

Equation *G***x*** *= 0 takes the form: x_{1} – x_{2} = 0, x_{1} – x_{2} = 0. The basis of general solutions of the system consists of the vector . This vector and the vector are linearly independent. Therefore, . We obtain the triangular matrices:

, .

Peculiarity of this example is that here exists a non-compact group of matrices commuting with the initial matrices.

8. Generalizations

The problem of getting the best block-triangle form can be formulated in another way: to find a transformation matrix S such that the maximum of the orders of the diagonal blocks will be the lowest possible. The uniqueness theorem implies that by solving the problem of getting the maximum number of blocks we simultaneously obtain the block having the lowest possible order.

It is clear that there can be more than two initial matrices. In this case course of solution will have no changes. Only the number of matrix equations (2) or the amount of the initial matrices for composition of the algebra j(*В*_{n}) will be increased.

Let us consider the problem of reduction of matrices to the block-triangular form by transformation , where *H* and *S* are non-singular square matrices. This transformation is more effective than the similarity transformation (1). The problem is solved in the case, where one of the initial matrices is nonsingular.

Next, we need Theorem 10 by A.K. Lopatin. Refined formulation and proof of the result is as follows (see [1], Theorem 7.4).

*Theorem **10. *There exists a similarity transformation reducing matrix to the block-triangular form with *l* blocks on the main diagonal if and only if there exists a set of matrices such that

,

, (6)

where .

*Proof*. Let matrices be block-triangular. Let blocks on the main diagonal be of the order and . We choose a set of matrices in the form , where the matrices have the same kind of block as ; all the blocks of the variable matrices standing above the main diagonal are filled with parameters , and other elements of this matrix are zero. Then

,

where .

It is clear that . After the transformations , , this equality is still valid.

The condition means that , i.e. a subspace is invariant with respect to the matrix .

Let us denote as the number of blocks on the main diagonal of the matrices reduced to the block-triangular form. Let

.

*Theorem **11. *Let be matrices. If , then , where *N* is any non-singular matrix.

Proof. Let and be the transformation matrices, whereby the initial matrices are reduced to the block-triangular form by formula and have the maximum possible number of blocks on the main diagonal. In this case matrices have the same block-diagonal form. According to Theorem 10, there must be the matrices such that

,

, ,

where *.*

Let us perform a similarity transformation , , and replacement of vectors into . Equations (6) are retained. Moreover, :

.

Using Theorem 10, we obtain .

For finding a transformation with the greatest possible number of blocks on the main diagonal it is sufficient to solve this problem by a similarity transformation for supportive matrices , , .

9. Conclusion

Thus, the problem is completely solved. A method to bring a set of matrices to the best block-triangular form has been developed.

This result is of practical significance. This method can simplify a system of linear differential equations containing several matrices of coefficients [1,14]. Equations decoupling to independent subsystems corresponds to reducing matrices to the block-diagonal form. Reduction of matrices to the block-triangular form corresponds to "hierarchic" (vertical) decoupling. Thus, first subsystem does not contain variables of other subsystems. Only variables of the first and the second subsystems are present in the second subsystem, etc. The number of such subsystems can be greater than at ordinary decoupling.

10. Next Directions of Investigation

It would be helpful to solve the following problems as well.

• The solution of the same problem for matrices over other fields (real numbers, rational numbers, etc.).

• More detailed study of the special case is considered in Section 6.

• Using the transformation without requiring non-singularity of one of the matrices.

• Reduction to the best block-triangular form *n**n*-matrix *A* and *n**n*-matrix* m*-matrix *B* by transformation. Here *S*_{1} and *S*_{2} are nonsingular square matrices of corresponding orders. This problem and others, similar to it, are necessary for the hierarchic decoupling of systems of equations with rectangular coefficient matrices (see [1] Сhapter 8 and [12]).

References

*Bazilevich Yu.**N.,*Numerical decoupling methods in the linear problems of mechanics, Kyiv, Naukova Dumka, 1987 (in Russian).*Bazilevich Yu.**N., Korotenko M.L. and Shvets I.V.,*Solving the problem on hierarchical decoupling the linearmathematical models of mechanical systems,*Tekhnicheskaya Mekhanika*, 2003, N 1, 135–141 (in Russian).*Bazilevich Yu.**N.,*The exact decoupling of linear systems,Electronic Journal "Issledovano v Rossii", 2006, 018, 182–190, http://www.sci-journal.ru/articles/2006/018.pdf(in Russian).*Drozd Yu. A.,*Tame and wild matrix problems, Lect.*Notes Math.,*832, 242-258 (1980).*Fermi Enrico,*Notes on quantum mechanics/ The University of Chicago Pres*Lopatin A.K.,*The algebraic reducibility of systems of linear differential equations. I,*Diff. Uravn.*, 1968,V.4, 439–445 (in Russian).*Yakubovich E.D.,*Construction of replacement systems for a class of multidimensional linear automaticcontrol systems,*Izv. Vuzov, Radiofizika*, 1969, V.12, N 3, 362–377 (in Russian).*Gantmacher F. R.,*The Theory of Matrices / Chelsea: New York. 1960.*Bazilevich Yu.**N., Buldovich A.L.,*Algorithm for finding the general solution of the system of linear homogeneous algebraic equations in the case of very large-scale sparse matrix coefficients // Mathematical models and modern technology. Coll. scientific. tr. / NAS. Institute of Mathematics. - Kyiv, 1998. — 12, 13(inRussian).*Van Der Waerden*Algebra.vols.IandII. Springer-Verlag.*Chebotariov N.G.,*Introduction to theory of algebras, Moscow: Editorial URSS, 2003 (inRussian).*Belozerov V.E., Mozhaev G.**V.,*The uniqueness of the solution of problems of decoupling and aggregation of linear systems of automatic control // Teoriya slozhnyih sistem i metodyi ih modelirovaniya.— M: VNIISI, 1982.—4-13(inRussian).*Bazilevich Yu.**N.*Hidden Symmetry Exposure. The Mechanical Systems with the Hard Structure of Forces// Proceedings of Institute of Mathematics of NAS of Ukraine. — V. 50. — Part 3. — Kyiv: Institute of Mathematics of NAS of Ukraine, 2004 /—P.1261—1265.*Pavlovsky Yu.**N., Smirnova T.G.,*The problem of decomposition in the mathematical modeling.— M .: FAZIS, 1998. VI + 266(inRussian).

Journals

Copyright © 2014 - 2016 American Institute of Science except certain content provided by third parties.