Vipul at 16:22, 1 May 2014

2014-05-01T16:22:17Z

← Older revision		Revision as of 16:22, 1 May 2014
Line 8:		Line 8:

	The density of a matrix can be any rational number in <math>[0,1]</math>. For a <math>m \times n</math> matrix, the rational number must be expressible as an integer divided by <math>mn</math>.		The density of a matrix can be any rational number in <math>[0,1]</math>. For a <math>m \times n</math> matrix, the rational number must be expressible as an integer divided by <math>mn</math>.

			==Relation with other matrix measures==

			{\| class="sortable" border="1"
			! Measure !! Numerical relationship with density for a <math>m \times n</math> matrix (<math>n \times n</math> if it is required to be square)
			\|-
			\| [[sparsity of a matrix]] \|\| The density and sparsity add up to 1.
			\|-
			\| [[rank of a matrix]] \|\| The density is at least equal to rank<math>/(mn)</math>.
			\|-
			\| [[bandwidth of a matrix]] (for a square matrix) \|\| The bandwidth is at least equal to <math>n</math> times the density (this can be improved somewhat by a constant order of magnitude of about 2).
			\|}

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

Vipul: Created page with "==Definition== Suppose $m,n$ are positive integers and $A$ is a $m \times n$ matrix. The '''density''' of $A$ is defined as the fr..."

2014-05-01T16:17:18Z

Created page with "==Definition== Suppose <math>m,n</math> are positive integers and <math>A</math> is a <math>m \times n</math> matrix. The '''density''' of <math>A</math> is defined as the fr..."

New page

==Definition==

Suppose <math>m,n</math> are positive integers and <math>A</math> is a <math>m \times n</math> matrix. The '''density''' of <math>A</math> is defined as the fraction of entries of <math>A</math> that have nonzero value. Explicitly, it is the ratio:

<math>\frac{|\{ (i,j) \in \{ 1,2,\dots,m\} \times \{1,2,\dots,n \} : a_{ij} \ne 0 \}|}{mn}</math>

The density of the matrix can also be defined as 1 minus its [[sparsity of a matrix|sparsity]].

The density of a matrix can be any rational number in <math>[0,1]</math>. For a <math>m \times n</math> matrix, the rational number must be expressible as an integer divided by <math>mn</math>.

==Matrix operations==

{| class="sortable" border="1"
! Matrix operation !! Lower bound on density of result !! Case where this occurs !! Upper bound on density of result !! Case where this occurs
|-
| Addition of two <math>m \times n</math> matrices <math>A</math> and <math>B</math> with densities <math>d_A</math> and <math>d_B</math> respectively || <math>|d_A - d_B|</math> || For all positions where both entries are nonzero, they are negatives of one another. || <math>d_A + d_B</math><br>Can be refined to <math>\min \{ d_A + d_B, 1 \}</math> || <math>d_A + d_B</math> occurs when the set of positions with nonzero entries for <math>A</math> is disjoint from the corresponding set for <math>B</math>.
|-
| Multiplication of a <math>m \times n</math> matrix <math>A</math> and a <math>n \times p</math> matrix <math>B</math> || <math>d_Ad_B</math. if <math>n = 1</math><br>0 if <math>n > 1</math> || The <math>n = 1</math> case boils down to a [[Hadamard product]] computation. For <math>n > 1</math>, we can arrange for a zero product regardless of density by choosing the rows of <math>A</math> and the columns of <math>B</math> to be orthogonal. || <math>n^2d_Ad_B</math><br>Can be refined to <math>\min \{ n^2d_Ad_B, 1 \}</math> || This occurs if there is exactly one column with nonzero entries in <math>A</math>, and exactly one row with nonzero entries in <math>B</math>, and the index number of the column and row coincide. The product <math>AB</math> in this case coincides with the [[Hadamard product]] of the nonzero column and the nonzero row.
|-
| [[Matrix transpose]] of a <math>m \times n</math> matrix <math>A</math>, giving a <math>n \times m</math> matrix <math>A^T</math> || <math>d_A</math> || bound always attained precisely || <math>d_A</math> ||bound always attained precisely
|-
| [[Inverse matrix]] of a <math>n \times n</math> matrix <math>A</math> || ? (at least <math>1/n</math>) || ? || ? || ?
|}
|}

Density of a matrix - Revision history

Vipul at 16:22, 1 May 2014

Vipul: Created page with "==Definition== Suppose m,n are positive integers and A is a m \times n matrix. The '''density''' of A is defined as the fr..."

Vipul: Created page with "==Definition== Suppose $m,n$ are positive integers and $A$ is a $m \times n$ matrix. The '''density''' of $A$ is defined as the fr..."