Notebook 9 – Math 2121, Fall 2020

There is a bounded region of space in $R^{n}$ that we naturally associate to an $n \times n$ matrix: namely, consider the $n$ -dimensional parallelogram (called a parallelepiped when $n = 3$ ) whose edges are the columns of your matrix. Define the volume of a matrix to be the volume of this region.

2.7 ms

1.1 μs

Our goal today is to uncover a formula for this volume. But first we need to better understand what the $n$ -dimensional parallelogram associated to an $n \times n$ matrix looks like and what "volume" means for a region in $R^{n}$ .

15.4 μs

974 ns

A $1 \times 1$ matrix is just a scalar.

However our definitions work, they should associate a volume of $| a |$ to $A = [a]$ when $n = 1$ .

13.5 μs

751 ns

The $n = 2$ case is more informative.

In $2$ dimensions, we usually refer to volume as area.

Consider the following $2 \times 2$ matrix:

16.5 μs

2×2 Array{Float64,2}:
 3.76  -0.68
 0.54   1.37

xxxxxxxxxx
 
A = rand(-5:0.01:5, 2, 2)

22.7 μs

Here is a picture of the parallelogram spanned by the columns of $M$ :

12.5 μs

326 ms

How can we characterize this parallelogram?

Well, every point inside the parallelogram has the form $A v$ for some vector

$v = [\begin{matrix} v_{1} \\ v_{2} \end{matrix}] \in R^{2}$

with $0 \leq v_{1} \leq 1$ and $0 \leq v_{2} \leq 1$ . This suggests a general definition:

The $n$ -dimensional parallelogram of an $n \times n$ matrix $A$ is the set of all points

${A v : v = [\begin{matrix} v_{1} \\ v_{2} \\ ⋮ \\ v_{n} \end{matrix}] \in R^{n} with 0 \leq v_{i} \leq 1 for i = 1, 2, \dots, n} .$

Then we define the volume of an $n \times n$ matrix to be the volume of this region.

26.5 μs

941 ns

Next issue: how is volume defined in $R^{n}$ ?

The definition should obey our intuition that the volume of a rectangular region is

$length \times width \times height \times \dots$

and volume should be invariant under translation.

That is, if $L_{1}, L_{2}, \dots, L_{n}$ are positive numbers then the region

$r e c t (L_{1}, L_{2}, \dots, L_{n}) = {v \in R^{n} : 0 \leq v_{i} \leq L_{i} for i = 1, 2, \dots, n}$

should have volume $L_{1} \cdot L_{2} \dots L_{n}$ . Moreover, any translate of this region

$u + r e c t (L_{1}, L_{2}, \dots, L_{n}) = {u + v \in R^{n} : 0 \leq v_{i} \leq L_{i} for i = 1, 2, \dots, n}$

where $u \in R^{n}$ is some given element should have the same volume.

Finally, if we have two regions in $R^{n}$ that don't overlap, then the volume of their union should be the sum of their individual volumes.

21.5 μs

1 μs

Here is one definition of the volume of a region $S$ in $R^{n}$ that satisfies these properties: choose small positive numbers $L_{1}, L_{2}, \dots, L_{n} > 0$ and fill up as much of $S$ as possible with nonoverlapping translates of the $n$ -dimensional rectangle $r e c t (L_{1}, L_{2}, \dots, L_{n})$ . If you can fit $N$ such regions completely inside $S$ without any overlap, then you say your estimated volume is

$N \cdot L_{1} \cdot L_{2} \dots L_{n} .$

The true volume of $S$ is then the limit superior of all possible estimated volumes.

To define limit superior, we need calculus; you can think of this as just the maximum.

23.8 μs

1.3 μs

This conforms with our usual definiton of area in two dimensions.

But in $R^{2}$ we can also calculate area more directly:

14.3 μs

48.2 ms

3.76

0.54

-0.68

1.37

3.08

1.91

xxxxxxxxxx
 
A[1,1], A[2,1], A[1,2], A[2,2], A[1,1] + A[1,2], A[2,1] + A[2,2]

12.9 μs

5.518399999999999

x
 
# outer rectangle - triangles
(3.76 + 0.68) * 1.91 - 0.54 * 3.76 - 0.68 * 1.37

15.3 μs

790 ns

Here is an alternate, probabilistic definition of volume that is more amenable to estimation.

Consider a region $S$ in $R^{n}$ . Define the volume of

$R = u + r e c t (L_{1}, L_{2}, \dots, L_{n}) = {u + v \in R^{n} : 0 \leq v_{i} \leq L_{i} for i = 1, 2, \dots, n}$

to be $L_{1} \cdot L_{2} \dots L_{n}$ as usual. Choose $u$ and $L_{1}, L_{2}, \dots, L_{n}$ such that

$S \subseteq R .$

Now sample many points uniformly at random from the region $R$ . The volume of $S$ should then be (close to) the volume of $R$ times the fraction of these points that are contained in $S$ .

With enough random points, this approximate volume will converge to the true volume.

21.3 μs

1.4 μs

When our matrix $A$ is invertible and $S$ is the $n$ -dimensional parallelogram associated to $A$ , then there is an easy way for us to test whether a random point $w \in R$ belongs to $S$ :

We just check if $A^{- 1} w$ has all coordinates between $0.0$ and $1.0$ .

Thus, we can try to implement the probabilistic definition to estimate the matrix volume.

13 μs

volume_estimates (generic function with 1 method)

xxxxxxxxxx
 
function volume_estimates(A, lower_bound, upper_bound, trials)
    # the region R being used in this method is u + rect(L1, L2, ..., Ln) where
    #
    #   L1 = L2 = ... = Ln = upper_bound - lower_bound
    #   u = [lower_bound; lower_bound; ...; lower_bound]
    #
    
    (n, p) = size(A)
    @assert n == p
    
    estimates = []
    sample_region_size = (upper_bound - lower_bound)^n
    
    # let's only record the cumulative estimate every 1000 trials
    interval = maximum([Int(floor(trials/1000)) 1])
    
    count = 0
    v = rand(lower_bound:0.00001:upper_bound, n, trials)
    w = A^-1 * v
    
    for j=1:trials
        # column j of v belongs to the matrix volume if and only if 
        # column j of w = A^-1 * v has all entries between 0.0 and 1.0
        if 0.0 <= minimum(w[1:end,j]) && maximum(w[1:end,j]) <= 1.0
            count += 1
        end
        
        if j % interval == 0
            append!(estimates, count / j * sample_region_size)
        end
    end
    
    return estimates
end

129 μs

estimate_bounds (generic function with 2 methods)

xxxxxxxxxx
 
function estimate_bounds(A, trials=1000)
    # we get more accurante volume estimates but using a smaller region R
    # this method estimates optimal choices for lower_bound, upper_bound
    # so that R is as small as possible while containing the paralllelogram of A
    lower_bound, upper_bound = 0.0, 0.0
    for i=1:trials
        w = A * rand(0:1, size(A)[1], 1)
        lower_bound = minimum([lower_bound minimum(w)])
        upper_bound = maximum([upper_bound maximum(w)])
    end
    return (lower_bound, upper_bound)
end

90.7 μs

trials

xxxxxxxxxx
 
trials = 5000

3.2 μs

matrix

2×2 Array{Float64,2}:
 3.76  -0.68
 0.54   1.37

xxxxxxxxxx
 
matrix = A

1.2 μs

-0.68

3.76

xxxxxxxxxx
 
lower, upper = estimate_bounds(matrix)

427 μs

884 ns

The following graph shows what happens when we sample a large number $N$ of points from a rectangular region $R$ containing the $n$ -dimensional parallelogram $S$ of our matrix $A$ , and then multiply the faction of the points that are in $S$ by the volume of $R$ .

The resulting plots should estimate the volume of our matrix.

16.1 μs

5.9 ms

51.6 ms

5.606547839999998

xxxxxxxxxx
 
estimates[end]

6.4 μs

5.5184

xxxxxxxxxx
 
det(A)

10.8 μs

The punchline in this last graph: the volume of our matrix is the absolute value of the determinate.

Thus the physical interpretation of $det (A)$ is as the signed volume of $A$ .

This works in any dimension, not just $n = 2$ .

19.9 μs

4×4 Array{Float64,2}:
 -3.399  -3.273  -3.141  -1.812
 -4.421  -4.434  -4.815  -2.708
  4.941   4.193  -3.494  -1.508
  0.11    0.338   0.775   4.577

xxxxxxxxxx
 
M = rand(-5:0.001:5, 4, 4)

14.8 μs

-16.378

9.134

xxxxxxxxxx
 
hlower, hupper = estimate_bounds(M)

918 μs

htrials

10000000

xxxxxxxxxx
 
htrials = 10000000

1.5 μs

5.9 s

-14.494864906292989

xxxxxxxxxx
 
det(M)

15.5 μs

14.869115720278915

xxxxxxxxxx
 
hestimates[end]

5.5 μs

Next time: what is the physical interpretation of the sign of $det (A)$ ?

23 μs