Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Full Rank Matrices

Theorem

A matrix A in mathbf{R}^{m times n} is

  • full column rank if and only if A^TA is invertible.

  • full row rank if and only if AA^T is invertible.

Proof: The matrix is full column rank if and only if its nullspace if reduced to the singleton {0}, that is,

Ax = 0 Longrightarrow x = 0.

If A^TA is invertible, then indeed the condition Ax=0 implies A^TAx = 0, which in turn implies x=0.

Conversely, assume that the matrix is full column rank, and let x be such that A^TAx = 0. We then have x^TA^TAx = |Ax|_2^2 = 0, which means Ax=0. Since A is full column rank, we obtain x=0, as desired.

The proof for the other property follows similar lines.