Density of a matrix

Definition

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

$\frac{| {(i, j) \in {1, 2, \dots, m} \times {1, 2, \dots, n} : a_{i j} \neq 0} |}{m n}$

The density of the matrix can also be defined as 1 minus its sparsity.

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

Matrix operations

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 $m \times n$ matrices $A$ and $B$ with densities $d_{A}$ and $d_{B}$ respectively	$\| d_{A} - d_{B} \|$	For all positions where both entries are nonzero, they are negatives of one another.	$d_{A} + d_{B}$ Can be refined to $min {d_{A} + d_{B}, 1}$	$d_{A} + d_{B}$ occurs when the set of positions with nonzero entries for $A$ is disjoint from the corresponding set for $B$ .
Multiplication of a $m \times n$ matrix $A$ and a $n \times p$ matrix $B$	$d_{A} d_{B} < / m a t h . i f < m a t h > n = 1$ 0 if $n > 1$	The $n = 1$ case boils down to a Hadamard product computation. For $n > 1$ , we can arrange for a zero product regardless of density by choosing the rows of $A$ and the columns of $B$ to be orthogonal.	$n^{2} d_{A} d_{B}$ Can be refined to $min {n^{2} d_{A} d_{B}, 1}$	This occurs if there is exactly one column with nonzero entries in $A$ , and exactly one row with nonzero entries in $B$ , and the index number of the column and row coincide. The product $A B$ in this case coincides with the Hadamard product of the nonzero column and the nonzero row.
Matrix transpose of a $m \times n$ matrix $A$ , giving a $n \times m$ matrix $A^{T}$	$d_{A}$	bound always attained precisely	$d_{A}$	bound always attained precisely
Inverse matrix of a $n \times n$ matrix $A$	? (at least $1 / n$ )	?	?	?

|}