Diagonal matrix - Revision history

Vipul at 15:44, 1 May 2014

2014-05-01T15:44:59Z

@@ Line 25: / Line 25: @@
 * The linear transformation sends every basis vector to a scalar multiple of itself.
 * All the basis vectors are eigenvectors for the linear transformation.
 ==Small cases==
@@ Line 37: / Line 56: @@
 | 3 || <math>\begin{pmatrix} a_{11} & 0 & 0 \\ 0 & a_{22} & 0 \\ 0 & 0 & a_{33}\\\end{pmatrix}</math> || 3
 |}
 ==Matrix operations==

Vipul: /* Definition */

2014-05-01T15:37:36Z

Definition

← Older revision		Revision as of 15:37, 1 May 2014
Line 18:		Line 18:

	Note that for an ''actual'' diagonal matrix, the symbols <math>a_{11}, a_{22}, \dots, a_{nn}</math> will be replaced by values in the underlying set or ring the matrix is over.		Note that for an ''actual'' diagonal matrix, the symbols <math>a_{11}, a_{22}, \dots, a_{nn}</math> 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.

	==Small cases==		==Small cases==

Vipul: /* Verbal definition */

2014-05-01T15:36:01Z

Verbal definition

← Older revision		Revision as of 15:36, 1 May 2014
Line 5:		Line 5:
	===Verbal 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 diagonal. Note that it is also possible that some (or even all) the diagonal entries are zero.		A '''diagonal matrix''' is a [[square matrix]] for which all the off-diagonal entries are zero, or equivalently, all nonzero entries are on the [[defining ingredient::main diagonal]]. Note that it is also possible that some (or even all) the diagonal entries are zero.

	===Algebraic description===		===Algebraic description===

Vipul: /* =Non-binary properties where diagonal matrices are exemplars */

2014-04-29T20:26:27Z

=Non-binary properties where diagonal matrices are exemplars

← Older revision		Revision as of 20:26, 29 April 2014
Line 94:		Line 94:
	\|}		\|}

	===Non-binary properties where diagonal matrices are exemplars==		===Non-binary properties where diagonal matrices are exemplars===

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Operations */

2014-04-29T20:10:58Z

Operations

← Older revision		Revision as of 20:10, 29 April 2014
Line 67:		Line 67:

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

			==Relation with other properties==

			===Stronger properties===

			{\| class="sortable" border="1"
			! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
			\|-
			\| [[Weaker than::scalar matrix]] \|\| diagonal matrix where all the diagonal entries are equal \|\| obvious \|\| A matrix such as <math>\begin{pmatrix} 1 & 0 \\ 0 & 0 \\\end{pmatrix}</math> is diagonal but not scalar. \|\| {{intermediate notions short\|diagonal matrix\|scalar matrix}}
			\|}

			===Weaker properties===

			{\| class="sortable" border="1"
			! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
			\|-
			\| [[Stronger than::diagonalizable matrix]] \|\| is [[similar matrices\|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]] \|\| {{intermediate notions short\|diagonalizable matrix\|diagonal matrix}}
			\|-
			\| [[Stronger than::upper triangular matrix]] \|\| all entries ''below'' the main diagonal are zero \|\| (obvious) \|\| The matrix <math>\begin{pmatrix} 1 & 1 \\ 0 & 1 \\\end{pmatrix}</math> is upper triangular but not diagonal \|\| {{intermediate notions short\|upper triangular matrix\|diagonal matrix}}
			\|-
			\| [[Stronger than::lower triangular matrix]] \|\| all entries ''above'' the main diagonal are zero \|\| (obvious) \|\| The matrix <math>\begin{pmatrix} 1 & 0 \\ 1 & 1 \\\end{pmatrix}</math> is upper triangular but not diagonal \|\| {{intermediate notions short\|lower triangular matrix\|diagonal matrix}}
			\|-
			\| [[Stronger than::tridiagonal matrix]] \|\| all nonzero entries are on the main diagonal, the first superdiagonal, or the first subdiagonal \|\| (obvious) \|\| any non-diagonal <math>2 \times 2</math> matrix is tridiagonal \|\| {{intermediate notions short\|tridiagonal matrix\|diagonal matrix}}
			\|-
			\| [[Stronger than::symmetric matrix]] \|\| equals its [[matrix transpose]], or equivalently, <math>a_{ij} = a_{ji}</math> for all <math>i,j</math> \|\| [[diagonal implies symmetric]] \|\| The matrix <math>\begin{pmatrix} 0 & 1 \\ 1 & 0 \\\end{pmatrix}</math> is a counterexample. \|\| {{intermediate notions short\|symmetric matrix\|diagonal matrix}}
			\|}

			===Non-binary properties where diagonal matrices are exemplars==

			{\| class="sortable" border="1"
			! 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 <math>1 - (1/n)</math>. In the limit as <math>n \to \infty</math>, 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.
			\|}

Vipul: /* Matrix operations */

2014-04-29T19:49:18Z

Matrix operations

← Older revision		Revision as of 19:49, 29 April 2014
Line 41:		Line 41:

	==Matrix operations==		==Matrix operations==

			===Invariant computation===

	Unless otherwise specified, diagonal matrices are <math>n \times n</math> diagonal matrices.		Unless otherwise specified, diagonal matrices are <math>n \times n</math> diagonal matrices.
Line 50:		Line 52:
	\|-		\|-
	\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math> \|\| 0 \|\| <math>n - 1</math> \|\| 0		\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math> \|\| 0 \|\| <math>n - 1</math> \|\| 0
			\|}

			===Operations===

			{\| class="sortable" border="1"
			! Matrix operation !! Description in terms of diagonal encoding: we denote matrices as <math>(a_{11}, a_{22}, \dots, a_{nn})</math> and (if the operation is binary)<math>(b_{11},b_{22},\dots,b_{nn})</math>!! Arithmetic complexity: number of additions !! Arithmetic complexity: number of multiplications !! Number of inverse computations !! Set of diagonal matrices closed under operation?
	\|-		\|-
	\| Addition of two ~~such~~ matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0 \|\| 0		\| Addition of two diagonal matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0 \|\| 0 \|\| Yes
	\|-		\|-
	\| Multiplication of two ~~such~~ matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn})(b_{11},b_{22},\dots,b_{nn}) = (a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})</math> \|\| 0 \|\| <math>n</math> \|\| 0		\| Multiplication of two diagonal matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn})(b_{11},b_{22},\dots,b_{nn}) = (a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})</math> \|\| 0 \|\| <math>n</math> \|\| 0 \|\| Yes
	\|-		\|-
	~~\| Multiplication by a <math>n \times p</math> rectangular matrix (we allow <math>n = p</math>) \|\| ? \|\| 0 \|\| <math>np</math>~~		\| Computation of the [[inverse matrix]] \|\| <math>(a_{11},a_{22},\dots,a_{nn})^{-1} = (a_{11}^{-1},a_{22}^{-1},\dots,a_{nn}^{-1})</math> (inverse does not exist if any <math>a_{ii} = 0</math> \|\| 0 \|\| 0 \|\| <math>n</math> \|\| Yes, though not all diagonal matrices are invertible
	\|-
	\| Computation of the [[inverse matrix]] \|\| <math>(a_{11}^{-1},a_{22}^{-1},\dots,a_{nn}^{-1}</math> \|\| 0 \|\| 0 \|\| <math>n</math>
	\|}		\|}

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

Vipul: /* Matrix operations */

2014-04-29T19:43:51Z

Matrix operations

← Older revision		Revision as of 19:43, 29 April 2014
Line 45:		Line 45:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Matrix operation !! Description in terms of diagonal encoding <math>(a_{11}, a_{22}, \dots, a_{nn})</math> Arithmetic complexity: number of additions !! Arithmetic complexity: number of multiplications		! Matrix operation !! Description in terms of diagonal encoding: we use <math>(a_{11}, a_{22}, \dots, a_{nn})</math> when there is only one matrix !! Arithmetic complexity: number of additions !! Arithmetic complexity: number of multiplications !! Number of inverse computations
	\|-		\|-
	\| Computation of the [[trace]] \|\| <math>\sum_{i=1}^n a_{ii}</math> \|\| <math>n - 1</math> \|\| 0		\| Computation of the [[trace]] \|\| <math>\sum_{i=1}^n a_{ii}</math> \|\| <math>n - 1</math> \|\| 0 \|\| 0
	\|-		\|-
	\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math> \|\| 0 \|\| <math>n - 1</math>		\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math> \|\| 0 \|\| <math>n - 1</math> \|\| 0
	\|-		\|-
	\| Addition of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0		\| Addition of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0 \|\| 0
	\|-		\|-
	\| Multiplication of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn})(b_{11},b_{22},\dots,b_{nn}) = (a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})</math> \|\| 0 \|\| <math>n</math>		\| Multiplication of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn})(b_{11},b_{22},\dots,b_{nn}) = (a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})</math> \|\| 0 \|\| <math>n</math> \|\| 0
	\|-		\|-
	\| Multiplication by a <math>n \times p</math> rectangular matrix (we allow <math>n = p</math>) \|\| ? \|\| 0 \|\| <math>np</math>		\| Multiplication by a <math>n \times p</math> rectangular matrix (we allow <math>n = p</math>) \|\| ? \|\| 0 \|\| <math>np</math>
			\|-
			\| Computation of the [[inverse matrix]] \|\| <math>(a_{11}^{-1},a_{22}^{-1},\dots,a_{nn}^{-1}</math> \|\| 0 \|\| 0 \|\| <math>n</math>
	\|}		\|}

Vipul: /* Matrix operations */

2014-04-29T19:42:09Z

Matrix operations

← Older revision		Revision as of 19:42, 29 April 2014
Line 49:		Line 49:
	\| Computation of the [[trace]] \|\| <math>\sum_{i=1}^n a_{ii}</math> \|\| <math>n - 1</math> \|\| 0		\| Computation of the [[trace]] \|\| <math>\sum_{i=1}^n a_{ii}</math> \|\| <math>n - 1</math> \|\| 0
	\|-		\|-
	\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math>0 \|\| <math>n - 1</math>		\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math> \|\| 0 \|\| <math>n - 1</math>
	\|-		\|-
	\| Addition of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0		\| Addition of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0

Vipul: /* Matrix operations */

2014-04-29T19:41:47Z

Matrix operations

← Older revision		Revision as of 19:41, 29 April 2014
Line 45:		Line 45:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Matrix operation !! Arithmetic complexity: number of additions !! Arithmetic complexity: number of multiplications		! Matrix operation !! Description in terms of diagonal encoding <math>(a_{11}, a_{22}, \dots, a_{nn})</math> Arithmetic complexity: number of additions !! Arithmetic complexity: number of multiplications
	\|-		\|-
	\| Computation of the [[trace]] \|\| <math>n - 1</math> \|\| 0		\| Computation of the [[trace]] \|\| <math>\sum_{i=1}^n a_{ii}</math> \|\| <math>n - 1</math> \|\| 0
	\|-		\|-
	\| Computation of the [[determinant]] \|\| 0 \|\| <math>n - 1</math>		\| Computation of the [[determinant]] \|\| <math>\prod_{i=1}^n a_{ii}</math>0 \|\| <math>n - 1</math>
	\|-		\|-
	\| Addition of two such matrices \|\| <math>n</math> \|\| 0		\| Addition of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn}) + (b_{11},b_{22},\dots,b_{nn}) = (a_{11} + b_{11}, a_{22} + b_{22}, \dots, a_{nn} + b_{nn})</math> \|\| <math>n</math> \|\| 0
	\|-		\|-
	\| Multiplication of two such matrices \|\| 0 \|\| <math>n</math>		\| Multiplication of two such matrices \|\| <math>(a_{11},a_{22},\dots,a_{nn})(b_{11},b_{22},\dots,b_{nn}) = (a_{11}b_{11}, a_{22}b_{22}, \dots, a_{nn}b_{nn})</math> \|\| 0 \|\| <math>n</math>
	\|-		\|-
	\| Multiplication by a <math>n \times p</math> rectangular matrix (we allow <math>n = p</math>) \|\| 0 \|\| <math>np</math>		\| Multiplication by a <math>n \times p</math> rectangular matrix (we allow <math>n = p</math>) \|\| ? \|\| 0 \|\| <math>np</math>
	\|}		\|}

Vipul: /* Encoding */

2014-04-29T19:39:18Z

Encoding

← Older revision		Revision as of 19:39, 29 April 2014
Line 38:		Line 38:

	* This encoding rule takes <math>n</math> times the space needed to store a single entry.		* This encoding rule takes <math>n</math> 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 <math>i,j \in \{ 1,2,\dots,n\}</math>, we can easily determine <math>a_{ij}</math>. 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'' matrix entries).		* 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 <math>i,j \in \{ 1,2,\dots,n\}</math>, we can easily determine <math>a_{ij}</math>. 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).

	==Matrix operations==		==Matrix operations==