Tag: Math

AM-GM Inequality

The Arithmetic Mean – Geometric Mean inequality says that if you have numbers a_1,\ldots,a_n\geq0, then (a_1\times a_2\times\ldots \times a_n)^{\frac{1}{n}}\leq\frac{1}{n}(a_1+\ldots+a_n). Another way to say this is that, given a set of nonnegative numbers, their geometric mean is always less than or equal to their arithmetic mean.

Before we look at some examples, let’s think about what this means geometrically. If you raise both sides to the n, you get (a_1\times a_2\times\ldots \times a_n) \leq \left(\frac{a_1+\ldots+a_n}{n}\right)^n. You can think of both sides of this as the area of an n-dimensional box. And this statement says that given sides lengths of a fixed sum, to maximize the volume of the box, you should make each side length the same. That side length is \frac{a_1+\ldots+a_n}{n}.

Now let’s look at some examples where we can apply this theorem.

If A is a positive semidefinite matrix (meaning that its eigenvalues \lambda_1,\ldots,\lambda_n are nonnegative), then (\lambda_1\times\ldots\times\lambda_n)^\frac{1}{n}\leq \frac{\lambda_1+\ldots+\lambda_n}{n}. The product of the eigenvalues of a matrix is det(A), and sum of the eigenvalues is tr(A). That means we can write that inequality as det(A)^{\frac{1}{n}}\leq\left(\frac{tr(A)}{n}\right). We can raise both sides to the n to get a bound on det(A). We get that, for a positive semidefinite matrix det(A) \leq \left(\frac{tr(A)}{n}\right)^n.

This is nice because the determinant is really expensive to calculate, but the trace is very easy to calculate as the sum of the diagonal entries of A. So this gives an upper bound on det(A) that is easy to obtain.

Let’s consider some positive semidefinite matrices that arise in applications and see what this inequality can tell us.

Let \vec{f}:\mathbb{R}^n\to\mathbb{R}^n be a nonlinear function. Then the Jacobian of this nonlinear transformation is J=\begin{bmatrix}\frac{\partial f_1}{\partial x_1}&\ldots&\frac{\partial f_1}{\partial x_n}\\ \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1}&\ldots&\frac{\partial f_n}{\partial x_n}\end{bmatrix}. If the Jacobian matrix is positive semidefinite we can apply the inequality from earlier. It will tell us that det(J)\leq \left(\frac{tr(J)}{n}\right)^n. The right hand side of this can be rewritten as \left(\frac{\frac{\partial f_1}{\partial x_1}+\ldots+\frac{\partial f_n}{\partial x_n}}{n}\right)^n, but this is the same thing as \left(\frac{div \vec{f}}{n}\right)^n, where div is the divergence of a vector field. So we get that det J \leq \left(\frac {div \vec{f}}{n}\right)^n. This is interesting because the determinant of a linear transformation essentially tells you the volume that its basis vectors occupy, and this inequality says that this quantity is bounded above by a function of div f. div f tells you whether f behaves like a source or a sink at a point, so this inequality relates the volume occupied by the linearization of f to extent to which f behaves like a source or a sink at a point.

Now, suppose g:\mathbb{R}^n\to \mathbb{R} is a convex function. Then the Hessian matrix H is given by H=\begin{bmatrix}\frac{\partial^2f}{\partial x_1^2}&\frac{\partial^2 f}{\partial x_1\partial x_2}&\ldots&\frac{\partial^2 f}{\partial x_1\partial x_n}\\ \frac{\partial^2 f}{\partial x_2\partial x_1}&\frac{\partial^2f}{\partial x_2^2}&\ldots&\frac{\partial^2 f}{\partial x_2\partial x_n}\\ \vdots & \vdots & \ddots&\vdots\\ \frac{\partial^2 f}{\partial x_n\partial x_1}&\frac{\partial^2 f}{\partial x_n\partial x_2}&\ldots&\frac{\partial^2 f}{\partial x_n^2}\end{bmatrix} is positive semidefinite. Therefore det(H)\leq \left(\frac{tr(H)}{n}\right)^n. Like in the previous example, we can simplify the numerator. The trace of H is \frac{\partial^2 f}{\partial x_1^2}+\ldots+\frac{\partial^2 f}{\partial x_n^2}, but this is just \Delta f, the Laplacian of f. So this shows that for a convex function (Hessian is positive semidefinite) with Hessian matrix H, det(H)\leq(\frac{\Delta f}{n})^n. If you compute det H at a critical point of the function f (a place where \nabla f=\vec{0}), you get the Gaussian curvature of the function at that point. That means that this inequality gives an upper bound on the Gaussian curvature at a critical point in terms of \Delta f.

Hopefully this gives some insight into how the Arithmetic Mean – Geometric Mean Inequality comes up in different areas of math!

Rank-Nullity Theorem and First Isomorphism Theorem

In this post, I want to talk about the connection between the Rank-Nullity Theorem from Linear Algebra and the First Isomorphism Theorem, which comes up in Abstract Algebra. We talked about the Rank-Nullity Theorem in the last post, but here’s a quick overview.

The Rank-Nullity theorem relates the dimension of the column space of an m\times n matrix A to the dimension of the null space of that matrix. Specifically, it says that the sum of these two values is equal to the number of columns of A. That is, rank(A)+nul(A) = n.

Before we talk about the First Isomorphism Theorem and relate it to linear transformations, let’s just define a few things that we’ll need to know to understand it.

Definition 1: The kernel of a transformation f:A\to B is the set \{x\in A \vert f(x)=0 \}. Note that 0\in B.

Note that the kernel is a generalization of the null space of a matrix that is defined for both linear and nonlinear transformations.

Definition 2: An element b is in the image of a transformation f:A\to B if there exists some a\in A such that f(a)=b.

The image of a transformation is a generalization of the column space that holds for both linear and nonlinear transformations. That is, the image of matrix transformation is the column space of that matrix.

Definition 3: A group homomorphism from (G,*) to (H,\cdot) is a function h:G\to H such that for all u and v in G, it holds that h(u*v) = h(u)\cdot h(v)

A good way to think about a group homomorphism is that it’s a transformation between groups that maintains the relationship between the groups elements. You will get the same result if you multiply two elements in G and apply the function h as if you apply the function h to them both separately and then multiply the two outputs in the group H together. This is interesting because the group composition rules are not necessarily the same.

Now, let’s state the specific case of First Isomorphism Theorem we’ll talk about.

First Isomorphism Theorem: Let \phi:G\to H be a surjective homomorphism. Then, H is isomorphic to G/ker(\phi). Since \phi is surjective, H=im(\phi).

Hold on…What’s does G/ker(\phi) mean? That notation is a quotient group. There is a formal definition of it, but for now, let’s think about it as a way to separate elements in G into classes (called cosets) depending on their relationship with ker(\phi). This quotient group will have two cosets: one containing everything in G that IS IN ker(\phi) and one containing everything in G that IS NOT IN ker(\phi).

Because of the way quotient groups work, if \phi goes between spaces of the same dimension, the original group G can be written as the union of two sets: G = ker(\phi) \cup im(\phi).

Since G can be written in this way, it must be true that the size of G is equal to the sum of the sizes of ker(\phi) and im(\phi).

What does this say about linear transformations represented by square matrices? Since you can’t both be in a set AND not be in a set, it says that for a linear transformation from \mathbb{R}^n to \mathbb{R}^n, the null space and column space must be disjoint (except they’ll both have the zero vector in them).

Let’s look at a few examples and see why this makes sense.

Example: Let C be an n \times n invertible matrix. This means that the columns map onto \mathbb{R}^n and also that the null space has only the zero vector, meaning that these two sets share only the zero vector.

Example: Consider the non-invertible matrix \begin{pmatrix}1&2\\2&4\end{pmatrix}, which has the vector \begin{pmatrix} 2 \\ -1 \end{pmatrix} in its null space. If you try to solve \begin{pmatrix}1&2\\2&4\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}2\\-1\end{pmatrix} , you won’t be able to!

So, what have we learned? The First Isomorphism Theorem generalizes the Rank-Nullity Theorem in a way that lets us handle transformations between groups that are not necessarily Euclidean spaces. There is a tradeoff between having elements in the kernel of a transformation and elements in the image of a transformation. The larger the kernel is, the smaller the image is, and vice versa.

Let’s talk about the progression of these three theorems. The Invertible Matrix Theorem draws connections between the algebraic properties of a square matrix to the geometry of the transformation it represents. The Rank-Nullity theorem makes claims about the geometry of transformations between Euclidean spaces with potentially different dimensions. And the First Isomorphism Theorem makes claims about transformations between groups in general (note that \mathbb{R}^n and \mathbb{R}^m are groups for any integers n and m).

In the next post, we’ll talk more about what the First Isomorphism Theorem is actually saying and a neat application of it to transformations between different dimensions.

Stay tuned!