Eigenvalues and Eigenvectors

Balancing a Matrix

Balancing a Matrix

The errors in calculating the eigenvalues of a square matrix are proportional to the Frobenius norm of the matrix. The process of producing a matrix which is diagonally similar to a given matrix which reduces the matrix norm is called balancing the matrix. Similar matrices have the same eigenvalues. This routine first permutes to rows and columns by moving the rows with zero off-diagonal elements to the bottom of the matrix and by moving the columns with zero off-diagonal elements to the left of the matrix. The matrix is then such that the upper and lower diagonal blocks are upper triangular. The diagonal matrix is then chosen to reduce the norm of this permutted matrix.

Function List

  • void Balance_Matrix( double *A, double d[ ], int p[ ], int n )

    Given the n×n matrix A, the routine Balance_Matrix determines the diagonal matrix D with diagonal returned in the array d[] and the permutation matrix P with permutations returned in the array p[ ] such that the product D-1 PT A P D balances the matrix A. The arrays d and p should be dimensioned at least n in the calling routine. The original matrix A is replaced with the balanced matrix.

  • void Balance_Matrix_Back_Transform( double *x, double d[ ], int p[ ], int ncols, int n )

    After the matrix A is balanced, the routine Balance_Matrix_Back_Transform multiplies the n×ncol matrix x on the right by P D, where P is the permutation matrix given in the array p[ ] calculated in routine Balance_Matrix and D is the diagonal matrix whose diagonal is given in the array d[ ] likewise calculated in the routine Balance_Matrix. If the matrix x contains ncols eigenvectors of the balanced matrix stored along the columns of x, then P D x replaces the eigenvectors of the balanced matrix with the eigenvectors of the original matrix. After calling Balance_Matrix_Back_Transform the matrix x is replaced with the product the right hand side, P D x.

C Source Code

  • The file, balance_matrix.c, contains the routines Balance_Matrix( ) and Balance_Matrix_Back_Transform( ).