Diagonal matrix

From Linear
Jump to: navigation, search
This article defines a property that can be evaluated for a square matrix. In other words, given a square matrix (a matrix with an equal number of rows and columns) the matrix either satisfies or does not satisfy the property.
View other properties of square matrices

Definition

Verbal definition

A diagonal matrix is a square matrix for which all the off-diagonal entries are zero, or equivalently, all nonzero entries are on the main diagonal. Note that it is also possible that some (or even all) the diagonal entries are zero.

Algebraic description

Suppose is a positive integer. Suppose is a matrix. We say that is a diagonal matrix if the following holds:

In general, a diagonal matrix has the following appearance:

Note that for an actual diagonal matrix, the symbols will be replaced by values in the underlying set or ring the matrix is over.

Definition in terms of linear transformations

The matrix for a linear transformation in a given basis is a diagonal matrix if and only if the following equivalent conditions hold:

  • The linear transformation sends every basis vector to a scalar multiple of itself.
  • All the basis vectors are eigenvectors for the linear transformation.

Encoding

A matrix that is known to be diagonal may simply be encoded using an ordered list of its diagonal entries. For a matrix, this requires space for entries (in contrast with space for entries for an arbitrary square matrix).

Explicitly, the ordered list can be used to describe the diagonal matrix . Further:

  • This encoding rule takes times the space needed to store a single entry.
  • It is easy to convert back and forth between this encoding rule and the matrix description. In one direction, given this encoding rule, and numbers , we can easily determine . In the reverse direction, given a matrix encoded in the usual manner, we can look up the diagonal entries and construct the encoding. (To confirm that the matrix is diagonal, we need to look at all non-diagonal matrix entries).

Testing

Deterministic testing

Given a matrix, testing whether it is a diagonal matrix requires checking the values of off-diagonal entries. Explicitly, we check, for each entry not on the diagonal whether its value is zero. As soon as we encounter an nonzero value, we declare that the matrix is not diagonal. If all the values we encounter are zero, we declare that the matrix is diagonal. For a matrix, confirming that the matrix is diagonal requires checking a total of entries.

Randomized testing

Randomized testing does not save us much time. The reason is that it is quite possible for only a few of the off-diagonal entries to be zero, and therefore, randomized testing will not detect them easily. if there is one nonzero entry, and we check a fraction of the entries, then the probability that we'll detect that one nonzero entry is . Thus, randomized testing does not save us in the big-oh sense.

Small cases

General description of diagonal matrix Number of free parameters (equals )
1 1
2 2
3 3

Matrix operations

Invariant computation

Unless otherwise specified, diagonal matrices are diagonal matrices.

Matrix operation Description in terms of diagonal encoding: we use when there is only one matrix Arithmetic complexity: number of additions Arithmetic complexity: number of multiplications Number of inverse computations
Computation of the trace 0 0
Computation of the determinant 0 0

Operations

Matrix operation Description in terms of diagonal encoding: we denote matrices as and (if the operation is binary) Arithmetic complexity: number of additions Arithmetic complexity: number of multiplications Number of inverse computations Set of diagonal matrices closed under operation?
Addition of two diagonal matrices 0 0 Yes
Multiplication of two diagonal matrices 0 0 Yes
Computation of the inverse matrix (inverse does not exist if any 0 0 Yes, though not all diagonal matrices are invertible

The set of diagonal matrices has an algebraic structure of a ring. Explicitly, if the matrix entries are over a commutative unital ring , then the set of diagonal matrices form a commutative unital ring : an external direct product of copies of .

Relation with other properties

Stronger properties

Property Meaning Proof of implication Proof of strictness (reverse implication failure) Intermediate notions
scalar matrix diagonal matrix where all the diagonal entries are equal obvious A matrix such as is diagonal but not scalar. |

Weaker properties

Property Meaning Proof of implication Proof of strictness (reverse implication failure) Intermediate notions
diagonalizable matrix is similar to a diagonal matrix. Note that the notion of diagonalizability depends on the ring we are considering matrices over, so a given matrix may be diagonalizable in one ring but not in a smaller ring. (obvious) diagonalizable not implies diagonal |
upper triangular matrix all entries below the main diagonal are zero (obvious) The matrix is upper triangular but not diagonal |
lower triangular matrix all entries above the main diagonal are zero (obvious) The matrix is upper triangular but not diagonal |
tridiagonal matrix all nonzero entries are on the main diagonal, the first superdiagonal, or the first subdiagonal (obvious) any non-diagonal matrix is tridiagonal |
symmetric matrix equals its matrix transpose, or equivalently, for all diagonal implies symmetric The matrix is a counterexample. |

Non-binary properties where diagonal matrices are exemplars

Attribute Meaning Name for matrices that do "well" on this criterion Value for diagonal matrix
sparsity of a matrix fraction of matrix entries that are zero sparse matrix refers to a matrix whose sparsity is high (preferably close to 1). A family of matrices of size going to infinity is sparse if the sparsity of the family approaches 1. At least . In the limit as , this approaches 1.
bandwidth of a matrix the number of adjacent diagonals that are needed to cover all nonzero entries band matrix refers to a matrix of low bandwidth. At most 1 (0 only if it is the zero matrix, 1 otherwise). The left and right half bandwidths are both 0.