Full-Rank design matrix from overdetermined linear model

Question

I'm trying to create a full-rank design matrix X for a randomized block design model starting from something like the example from page 3/8 of this paper (Wayback Machine) .

It's been suggested that I can go about this by eliminating one of each of the columns for treatment (column 5) and block (column 8) as shown in the example on the page marked 45 in this paper.

I'm not sure how this results in a full-rank design matrix though, for a 12x8 matrix wouldn't making it 12x6 mean that by definition there are still linear dependencies?

My understanding of the definition of a full-rank matrix would be that there are no linear dependencies, which would require a matrix to be square among other criteria. Perhaps this is a misconception on my part?

The goal is to end up with an invertible matrix from $X^T X$ which I can use to determine the least squares, I'm not sure if that's relevant to the issue.

Answer 1

Let's start from your goal (which hopefully I deduced correctly):
You are assuming a linear model is appropriate for your task. You decided to use the linear least-squares cost function, and so your goal is to find the weights and bias such that the cost is minimal.

In this blog post, Eli Bendersky showed how to derive a closed-form solution to this problem: $$\theta=\left(X^{T}X\right)^{-1}X^{T}y$$ (while $\theta$ is the vector of weights and bias, and $y$ is a vector of the given responses to the feature vectors (rows) in $X$.)

Of course, this solution makes sense only if $X^T X$ is invertible.
It turns out that $X^T X$ is invertible iff $X$ is full column rank. (See here for a short proof.)

Thus, in order to use the aforementioned closed-form solution, you have to make sure your matrix is full column rank.
According to the definition of "full rank" in wikipedia:

• If a matrix has more rows than columns, then it is full rank iff it is full column rank.
• Otherwise (the number of columns is greater or equal to the number of rows), it is full rank iff it is full row rank.

(If the definition hadn't allowed for linearly dependent rows/columns, then every non-square matrix would have been rank deficient (i.e. non-full-rank), which would have made the definition useless for such matrices.)

Finally, how to convert $X$ into a full column rank matrix?
As explained here, there is a straight-forward way:

• Calculate the rank of the matrix.
• If the matrix is not full rank, then for each of column:
  • Calculate the rank of the matrix without this column.
  • If the rank is the same with and without the column, remove the column from the matrix. (The unchanged rank reveals that the column is a linear combination of the other columns, i.e. it is redundant.)

Answer 2

The matrix $\mathbf{X}^\text{T} \mathbf{X}$ is called the Gramian matrix of the design matrix $\mathbf{X}$. It is invertible if and only if the columns of the design matrix are linearly independent ---i.e., if and only if the design matrix has full rank (see e.g., here and here). (So yes, these two things are closely related, as you suspected.) Before considering why removing columns gives you full rank, it is useful to see why the present design matrix is not of full rank. In its current form, you have the linear dependencies:

$$\begin{equation} \begin{aligned} \text{col}_5(\mathbf{X}) &= \text{col}_1(\mathbf{X}) - \text{col}_2(\mathbf{X}) - \text{col}_3(\mathbf{X}) - \text{col}_4(\mathbf{X}), \\[6pt] \text{col}_8(\mathbf{X}) &= \text{col}_1(\mathbf{X}) - \text{col}_6(\mathbf{X}) - \text{col}_7(\mathbf{X}). \\[6pt] \end{aligned} \end{equation}$$

If you remove columns $5$ and $8$ you remove these linear dependencies, and it turns out that there are no linear dependencies remaining. (If you're not sure, just try to find one.) To confirm this we can look at the reduced design matrix and :

$$\mathbf{X}_- = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \quad \quad \quad \mathbf{X}_-^\text{T} \mathbf{X}_- = \begin{bmatrix} 12 & 3 & 3 & 3 & 4 & 4 \\ 3 & 3 & 0 & 0 & 1 & 1 \\ 3 & 0 & 3 & 0 & 1 & 1 \\ 3 & 0 & 0 & 3 & 1 & 1 \\ 4 & 1 & 1 & 1 & 4 & 0 \\ 4 & 1 & 1 & 1 & 0 & 4 \\ \end{bmatrix}.$$

The Gram determinant of this reduced design matrix is $\det (\mathbf{X}_-^\text{T} \mathbf{X}_-) = 432 \neq 0$, so the reduced design matrix has linearly independent columns and is of full rank. The Gramian matrix for the reduced design matrix is invertible, with inverse:

$$(\mathbf{X}_-^\text{T} \mathbf{X}_-)^{-1} = \begin{bmatrix} \tfrac{1}{2} & -\tfrac{1}{3} & -\tfrac{1}{3} & -\tfrac{1}{3} & -\tfrac{1}{4} & -\tfrac{1}{4} \\ -\tfrac{1}{3} & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{1}{3} & 0 & 0 \\ -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} & \tfrac{1}{3} & 0 & 0 \\ -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} & 0 & 0 \\ -\tfrac{1}{4} & 0 & 0 & 0 & \tfrac{1}{2} & \tfrac{1}{4} \\ -\tfrac{1}{4} & 0 & 0 & 0 & \tfrac{1}{4} & \tfrac{1}{2} \\ \end{bmatrix}.$$