# The Unapologetic Mathematician

## Decomposing Real Linear Transformations

Finally, we come to the analogue of Jordan normal form over the real numbers.

Given a linear transformation $T:V\rightarrow V$ on a real vector space $V$ of dimension $d$, we can find its characteristic polynomial. We can factor a real polynomial into the product of linear terms $(X-\lambda_i)$ and irreducible quadratic terms $(X^2-\tau_jX+\delta_j)$ with $\tau_j^2<4\delta$. These give us a list of eigenvalues and eigenpairs for $T$.

For each distinct eigenvalue $\lambda_i$ we get a subspace $U_i=\mathrm{Ker}\left((T-\lambda_iI_V)^d\right)\subseteq V$ of generalized eigenvectors, with $m$ distinct eigenvalues in total. Similarly, for each distinct eigenpair $(\tau_j,\delta_j)$ we get a subspace $V_j=\mathrm{Ker}\left((T^2-\tau_jT+\delta_jI_V)^d\right)\subseteq V$ of generalized eigenvectors, with $n$ distinct eigenpairs in total.

We know that these subspaces are mutually disjoint. We also know that the dimension of $U_i$ is equal to the multiplicity of $\lambda_i$, which is the number of factors of $(X-\lambda_i)$ in the characteristic polynomial. Similarly, the dimension of $V_j$ is twice the multiplicity of $(\tau_j,\delta_j)$, which is the number of factors of $(X^2-\tau_jX+\delta)$ in the characteristic polynomial. Since each linear factor contributes ${1}$ to the degree of the polynomial, while each irreducible quadratic contributes ${2}$, we can see that the sum of the dimensions of the $U_i$ and $V_j$ is equal to the degree of the characteristic polynomial, which is the dimension of $V$ itself.

That is, we have a decomposition of $V$ as a direct sum of invariant subspaces

$\displaystyle V=\bigoplus\limits_{i=1}^mU_i\oplus\bigoplus\limits_{j=1}^nV_j$

Further, we know that the restrictions $(T-\lambda_iI_V)|_{U_i}$ and $(T^2-\tau_jT+\delta_jI_V)|_{V_j}$ are nilpotent transformations.

I’ll leave it to you to work out what this last property implies for the matrix on the generalized eigenspace of an eigenpair, in analogy with a Jordan block for an eigenvalue.

April 9, 2009 Posted by | Algebra, Linear Algebra | 3 Comments

## The Multiplicity of an Eigenpair

As usual, let $T:V\rightarrow V$ be a linear transformation on a real vector space $V$ of dimension $d$. We know that $T$ can be put into an almost upper-triangular form

$\displaystyle\begin{pmatrix}A_1&&*\\&\ddots&\\{0}&&A_m\end{pmatrix}$

where each block $A_j$ is either a $1\times1$ matrix or a $2\times2$ matrix with no eigenvalues. Now I assert that

• If $\lambda$ is a real number, then exactly $\dim\left(\mathrm{Ker}\left((T-\lambda I_V)^d\right)\right)$ of the blocks are the $1\times1$ matrix whose single entry is $\lambda$.
• If $(\tau,\delta)$ is a pair of real numbers with $\tau^2<4\delta$, then exactly

$\displaystyle\frac{\dim\left(\mathrm{Ker}\left((T^2-\tau T+\delta)^d\right)\right)}{2}$

of the blocks are $2\times2$ matrices with characteristic polynomial $X^2-\tau X+\delta$. Incidentally, this shows that the dimension of this generalized eigenspace is even.

This statement is parallel to the one about multiplicities of eigenvalues over algebraically closed fields. And we’ll use a similar proof. First, let’s define the polynomial $p(X)$ to be $X-\lambda$ if we’re trying to prove the first part, and to be $X^2-\tau X+\delta$ if we’re trying to prove the second part, and let $n$ be the degree of $p$. We’ll proceed by induction on the number $m$ of blocks along the diagonal.

If $m=1$ then $V$ is either one- or two-dimensional. Then the statement reduces to what we worked out by cases earlier. So from here we’ll assume that $m>1$, and that the statement holds for all matrices with $m-1$ blocks.

Let’s define $U\subseteq V$ to be the subspace spanned by the first $m-1$ blocks, and $\hat{U}$ be the subspace spanned by the last block. That is, $U$ consists of all but the last one or two rows and columns of the matrix, depending on whether $A_m$ is $1\times1$ or $2\times2$. Clearly $U$ is invariant under $T$, and the restriction $T|_U$ of $T$ to $U$ has matrix

$\displaystyle\begin{pmatrix}A_1&&*\\&\ddots&\\{0}&&A_{m-1}\end{pmatrix}$

with $m-1$ blocks. Thus the inductive hypothesis tells us that exactly

$\displaystyle\frac{1}{n}\dim\left(\mathrm{Ker}\left(\left(p\left(T|_U\right)\right)^d\right)\right)$

of the blocks from $A_1$ to $A_{m-1}$ have characteristic polynomial $p$.

We’ll also define $\hat{T}:\hat{U}\rightarrow\hat{U}$ to be the linear transformation acting by the block $A_m$. This is essentially the action of $T$ on the quotient space $V/U$, but we’re viewing $\hat{U}$ as giving representatives in $V$ for vectors in the quotient space. This way, if $v\in\hat{U}$ is a vector in this subspace of representatives we can write $Tv=Sv+u_1$ for some $u_1\in U$. Further, $T^2v=S^2v+u_2$ for some other vector $u_2\in U$. No matter which form of $p$ we’re using, we can see that $p(T)v=p(S)v+u_3$ for some $u_3\in U$, and further that $p(T)^dv=p(S)^dv+u_4$ for some $u_4\in U$.

Now, either $A_m$ has characteristic polynomial $p$ or not. If not, then I say that $\mathrm{Ker}\left(p(T)^d\right)\subseteq U$. This implies that

$\displaystyle\mathrm{Ker}\left(\left(p(T)\right)^d\right)=\mathrm{Ker}\left(\left(p\left(T|_U\right)\right)^d\right)$

and thus that both the dimension of this kernel and the number of blocks with characteristic polynomial $p$ are the same as for $T|_U$.

So let’s assume $v\in\mathrm{Ker}\left(p(T)^d\right)$ and write $v=u+\hat{u}$ with $u\in U$ and $\hat{u}\in\hat{U}$. Then

$\displaystyle0=p(T)^dv=p(T)^du+p(T)^d\hat{u}=p(T)^du+u_5+p(S)^d\hat{u}$

for some $u_5\in U$. This implies that $p(S)^d\hat{u}=0$, but since $p$ is not the characteristic polynomial of $S$, it is invertible on $\hat{U}$. Thus $\hat{u}=0$ and $v\in\mathrm{Ker}\left(p\left(T|_U\right)^d\right)$.

On the other hand, if the characteristic polynomial of $A_m$ is $p$, then we want to show that

$\displaystyle\dim\left(\mathrm{Ker}\left(p(T)^d\right)\right)=\dim\left(\mathrm{Ker}\left(\left(p\left(T|_U\right)\right)^d\right)\right)+n$

The inclusion-exclusion principle tells us that

\displaystyle\begin{aligned}\dim\left(\mathrm{Ker}\left(p(T)^d\right)\right)&=\dim\left(U\cap\mathrm{Ker}\left(p(T)^d\right)\right)+\dim\left(U+\mathrm{Ker}\left(p(T)^d\right)\right)-\dim(U)\\&=\dim\left(\mathrm{Ker}\left(p\left(T|_U\right)^d\right)\right))+\dim\left(U+\mathrm{Ker}\left(p(T)^d\right)\right)-(d-n)\end{aligned}

We’ll show that $U+\mathrm{Ker}\left(p(T)^d\right)=V$, and so its dimension is $d$, and we have the result we want.

So take $\hat{u}\in\hat{U}$. Because the characteristic polynomial of $S$ is $p$, we know that $p(S)=0$. Thus $p(T)\hat{u}\in U$. Then

$\displaystyle p(T)^d\hat{u}=p(T)^d\left(p(T)\hat{u}\right)\in\mathrm{Im}\left(p\left(T|_U\right)^{d-1}\right)=\mathrm{Im}\left(p\left(T|_U\right)^d\right)$

where the last equality holds because the dimension of $U$ is $d-n$, and so the image has stabilized by this point. Thus we can choose $u\in U$ so that $p(T)^d\hat{u}=p\left(T|_U\right)^du$. And so

\displaystyle\begin{aligned}p(T)^d(\hat{u}-u)&=p(T)^d\hat{u}-p(T)^du\\&=p(T)^d\hat{u}-p\left(T|_U\right)^du\\&=0\end{aligned}

which shows that $\hat{u}-u\in\mathrm{Ker}\left(p(T)^d\right)$. And thus $\hat{u}=u+(\hat{u}-u)$ is in $U+\mathrm{Ker}\left(p(T)^d\right)$. Since $\hat{u}$ was arbitrary, the whole subspace $\hat{U}\subseteq U+\mathrm{Ker}\left(p(T)^d\right)$, which shows that $V=U+\hat{U}\subseteq U+\mathrm{Ker}\left(p(T)^d\right)\subseteq V$, which completes our proof.

Now, all of that handled we turn to calculate the characteristic polynomial of $T$, only to find that it’s the product of the characteristic polynomials of all the blocks $A_m$. That is, we will have $\dim\left(\mathrm{Ker}\left((T-\lambda I_V)^d\right)\right)$ factors of $(X-\lambda)$ and $\frac{1}{2}\dim\left(\mathrm{Ker}\left((T^2-\tau T+\delta)^d\right)\right)$ factors of $(X^2-\tau X+\delta)$. We can thus define this half-dimension to be the multiplicity of the eigenpair. Like the multiplicity of an eigenvalue, it counts both the number of times the corresponding factor shows up in the characteristic polynomial of $T$, and the number of blocks on the diagonal of an almost upper-triangular matrix for $T$ that have this characteristic polynomial.

April 8, 2009

## Generalized Eigenspaces are Still Invariant and Disjoint

When working over an algebraically closed field we found that generalized eigenspaces are invariant and disjoint from each other. The same holds now that we’re allowing eigenpairs for transformations on real vector spaces.

First off, the generalized eigenspace of an eigenpair $(\tau,\delta)$ is the kernel $\mathrm{Ker}\left((T^2-\tau T+\delta I_V)^d\right)$ of a polynomial in $T$. Just like before, this kernel is automatically invariant under $T$, just like the generalized eigenspace $\mathrm{Ker}\left((T-\lambda I_V)^d\right)$ is.

Generalized eigenspaces of distinct eigenvalues are disjoint, as before. But let $\lambda$ be an eigenvalue, $(\tau,\delta)$ be an eigenpair, and $v$ be a vector in both generalized eigenspaces. The invariance of $\mathrm{Ker}\left((T^2-\tau T+\delta I_V)^d\right)$ under $T$ shows that if $u$ is a generalized eigenvector of $(\tau,\delta)$, then so is $Tu-\lambda u$. Just like we did before, we can keep hitting $v$ with $T-\lambda I_V$ until one step before it vanishes (which it eventually must, since it’s a generalized eigenvector of $\lambda$). So without loss of generality we can assume that $v$ is an actual eigenvector of $\lambda$ and a generalized eigenvector of $(\tau,\delta)$.

Now we can use the generalized eigenvector property to write

$\displaystyle(T^2-\tau T+\delta I_V)^dv=0$

but since $v$ is an eigenvector with eigenvalue $\lambda$, this says

$\displaystyle(\lambda^2-\tau\lambda+\delta)^dv=0$

If $v$ is nonzero, this can only be true if $\lambda$ is a root of $X^2-\tau X+\delta$, which we assumed not to be the case.

Finally we consider two distinct eigenpairs $(\tau_1,\delta_1)$ and $(\tau_2,\delta_2)$, and a generalized eigenvector of both, $v$. Another argument like that above shows that without loss of generality we can assume $v$ is an actual eigenvector of $(\tau_2,\delta_2)$. This eigenspace is the kernel $\mathrm{Ker}(T^2-\tau_2T+\delta_2I_V)$, which is thus invariant, and another argument like before lets us assume that $v$ is an actual eigenvector of both eigenpairs. Thus we have

\displaystyle\begin{aligned}(T^2-\tau_1T+\delta_1I_V)v&=0\\(T^2-\tau_1T+\delta_1I_V)v&=0\end{aligned}

Subtracting, we find

$\displaystyle -(\tau_1-\tau_2)Tv+(\delta_1-\delta_2)v=0$

If $\tau_1-\tau_2\neq0$, this makes $v$ an eigenvector with eigenvalue $\frac{\delta_1-\delta_2}{\tau_1-\tau_2}$. On the other hand, if $\tau_1=\tau_2$ then $\delta_1\neq\delta_2$, and we conclude that $v=0$.

At the end of the day, no nonzero vector can be a generalized eigenvector of more than one eigenvalue or eigenpair.

April 7, 2009 Posted by | Algebra, Linear Algebra | 1 Comment

## Generalized Eigenvectors of an Eigenpair

Just as we saw when dealing with eigenvalues, eigenvectors alone won’t cut it. We want to consider the kernel not just of one transformation, but of its powers. Specifically, we will say that $v$ is a generalized eigenvector of the eigenpair $(\tau,\delta)$ if for some power $n$ we have

$\displaystyle(T^2-\tau T+\delta I_V)^nv=0$

The same argument as before tells us that the kernel will stabilize by the time we take $d=\dim(V)$ powers of an operator, so we define the generalized eigenspace of an eigenpair $(\tau,\delta)$ to be

$\displaystyle\mathrm{Ker}\left((T^2-\tau T+\delta I_V)^d\right)$

Let’s look at these subspaces a little more closely, along with the older ones of the form $\mathrm{Ker}\left((T-\lambda I_V)^d\right)$, just to make sure they’re as well-behaved as our earlier generalized eigenspaces are. First, let $V$ be one-dimensional, so $T$ must be multiplication by $\lambda_0$. Then the kernel of $T-\lambda I_V$ is all of $V$ if $\lambda=\lambda_0$, and is trivial otherwise. On the other hand, what happens with an eigenpair $(\tau,\delta)$? Well, one application of the operator gives

$\displaystyle(T^2-\tau T+\delta I_V)v=(\lambda_0^2-\tau\lambda_0+\delta)v$

for any nonzero $v$. But this will always be itself nonzero, since we’re assuming that the polynomial $X^2-\tau X+\delta$ has no roots. Thus the generalized eigenspace of $(\tau,\delta)$ will be trivial.

Next, if $V$ is two-dimensional, either $T$ has an eigenvalue or it doesn’t. If it does, then this gives a one-dimensional invariant subspace. The argument above shows that the generalized eigenspace of any eigenpair $(\tau,\delta)$ is again trivial. But if $T$ has no eigenvalues, then the generalized eigenspace of any eigenvalue $\lambda$ is trivial. On the other hand we’ve seen that the kernel of $T^2-\tau T+\delta I_V$ is either the whole of $V$ or nothing, and the former case happens exactly when $\tau$ is the trace of $T$ and $\delta$ is its determinant.

Now if $V$ is a real vector space of any finite dimension $d$ we know we can find an almost upper-triangular form. This form is highly non-unique, but there are some patterns we can exploit as we move forward.

April 6, 2009

## Eigenvectors of an Eigenpair

An eigenvalue $\lambda$ of a linear transformation $T$ is the same thing as a root of the characteristic polynomial of $T$. That is, the characteristic polynomial has a factor $(X-\lambda)$. We can evaluate this polynomial at $T$ to get the linear transformation $(T-\lambda I_V$. Vectors in the kernel of this space are the eigenvalues corresponding to the eigenvector $\lambda$.

Now we want to do the same thing with an eigenpair $(\tau,\delta)$. This corresponds to an irreducible quadratic factor $(X^2-\tau X+\delta)$ in the characteristic polynomial of $T$. Evaluating this polynomial at $T$ we get the transformation $T^2-\tau T+\delta I_V$, which I assert has a nontrivial kernel. Specifically, I want to focus in on some two-dimensional invariant subspace on which $T$ has no eigenvalues. This corresponds to a $2\times2$ block in an almost upper-triangular representation of $T$. So we’ll just assume for the moment that $V$ has dimension $2$.

What I assert is this: if $p$ is a monic polynomial (with leading coefficient ${1}$) of degree two, then either $p$ is the characteristic polynomial of $T$ or it’s not. If it is, then $p(T)=0$, and its kernel is the whole of $V$. If not, then the kernel is trivial, and $p(T)$ is invertible.

In the first case we can just pick a basis, find a matrix, and crank out the calculation. If the matrix of $T$ is

$\displaystyle\begin{pmatrix}a&b\\c&d\end{pmatrix}$

then the characteristic polynomial is $X^2-(a+d)X+(ad-bc)$. We substitute the matrix into this polynomial to find

\displaystyle\begin{aligned}&\begin{pmatrix}a&b\\c&d\end{pmatrix}\begin{pmatrix}a&b\\c&d\end{pmatrix}-(a+d)\begin{pmatrix}a&b\\c&d\end{pmatrix}+(ad-bc)\begin{pmatrix}{1}&{0}\\{0}&{1}\end{pmatrix}=\\&\begin{pmatrix}a^2+bc&ab+bd\\ac+cd&bc+d^2\end{pmatrix}-\begin{pmatrix}a^2+ad&ab+bd\\ac+cd&ad+d^2\end{pmatrix}+\begin{pmatrix}ad-bc&{0}\\{0}&ad-bc\end{pmatrix}=\\&\begin{pmatrix}{0}&{0}\\{0}&{0}\end{pmatrix}\end{aligned}

On the other hand, if $q$ is the characteristic polynomial and $p$ is any other monic polynomial of degree two, then $q(T)=0$, as we just showed. Then we can calculate

$\displaystyle p(T)=p(T)-q(T)=aT+bI_V$

for some constants $a$ and $b$, at least one of which must be nonzero. If $a=0$, then $p(T)$ is a nonzero multiple of the identity, which is invertible as claimed. On the other hand, if $a\neq0$, then

$\displaystyle p(T)=a(T-\frac{b}{a}I_V)$

which must be invertible since we assumed that $T$ has no eigenvalues.

So for any $2\times2$ block, the action of an irreducible quadratic polynomial in $T$ either kills off the whole block or has a trivial kernel. This makes it reasonable to define an eigenvector of the eigenpair $(\tau,\delta)$ to be a vector in the kernel $\mathrm{Ker}\left(T^2-\tau T+\delta I_V\right)$, in analogy with the definition of an eigenvector of a given eigenvalue.

April 3, 2009 Posted by | Algebra, Linear Algebra | 2 Comments

## The Characteristic Polynomial of a Real Linear Transformation

We continue working over the field $\mathbb{R}$ of real numbers. Again, let $T:V\rightarrow V$ be a linear transformation from a real vector space $V$ of dimension $d$ to itself. We want to find the characteristic polynomial of this linear transformation.

When we had an algebraically closed field, this was easy. We took an upper-triangular matrix, and then the determinant was just the product down the diagonal. This gave one factor of the form $(\lambda-\lambda_j)$ for each diagonal entry $\lambda_j$, which established that the diagonal entries of an upper-triangular matrix were exactly the eigenvalues of the linear transformation.

Now we don’t always have an upper-triangular matrix, but we can always find a matrix that’s almost upper-triangular. That is, one that looks like

$\displaystyle\begin{pmatrix}A_1&&*\\&\ddots&\\{0}&&A_m\end{pmatrix}$

where the blocks $A_j$ are all either $1\times1$ matrices

$\displaystyle A_j=\begin{pmatrix}\lambda_j\end{pmatrix}$

or $2\times2$ matrices

$\displaystyle A_j=\begin{pmatrix}a_j&b_j\\c_j&d_j\end{pmatrix}$

In this latter case, we define $\tau_j$ to be the trace $a_j+d_j$, and $\delta_j$ to be the determinant $a_jd_j-b_jc_j$. We must find that $\tau_j^2<4\delta_j$, otherwise we can find another basis which breaks $A_j$ up into two $1\times1$ blocks. Let’s go a step further and insist that all the $2\times2$ blocks show up first, followed by all the $1\times1$ blocks.

Now we can start calculating the determinant of $\lambda I_V-T$, summing over permutations. Just like we saw with an upper-triangular matrix, if we have a $1\times1$ block in the lower-right we have to choose the rightmost entry in the bottom column, or the whole term will be zero. So we start racking up factors $(\lambda-\lambda_j)$ just like before. Each $1\times1$ block, then, gives us a root of the characteristic polynomial, which is an eigenvalue. So far everything is the same as in the upper-triangular case.

Once we get to the $2\times2$ blocks we have to be a bit more careful. We have two choices of a nonzero entry in the lowest row: $\lambda-d_j$ or $-c_j$. But if we choose $\lambda-d_j$ then we can only choose $\lambda-a_j$ on the next row up to have a chance of a nonzero term. On the other hand, if we choose $-c_j$ on the lowest row we are forced to choose $-b_j$ next. The choice between these two is independent of any other choices we might make in calculating the determinant. The first always gives a factor of $(\lambda-a_j)(\lambda-d_j)$ to the term corresponding to that permutation, while the second always gives a factor of $(-b_j)(-c_j)$ to its term. These permutations (no matter what other choices we might make) differ by exactly one swap, and so they enter the determinant with opposite signs.

Now we can collect together all the permutations where we make one choice in block $A_j$, and all the permutations where we make the other choice. From the first collection we can factor out $(\lambda-a_j)(\lambda-d_j)$, and from the second we can factor out $(-b_j)(-c_j)$. What remains after we pull these factors out is the same in either case, so the upshot is that the $2\times2$ block $A_j$ contributes a factor of $(\lambda-a_j)(\lambda-d_j)-(-b_j)(-c_j)$ to the determinant. Some calculation simplifies this:

\displaystyle\begin{aligned}(\lambda-a_j)(\lambda-d_j)-(-b_j)(-c_j)&=\lambda^2-(a_j+d_j)\lambda+(a_jd_j-b_jc_j)\\&=\lambda^2-\tau_j\lambda+\delta_j\end{aligned}

which is a quadratic factor with no real roots (since we assumed that $\tau_j^2<4\delta_j$).

But a factor of the characteristic polynomial of this formula is exactly what we defined to be an eigenpair. That is, just as eigenvectors — roots of the characteristic polynomial — correspond to one-dimensional invariant subspaces, so too do eigenpairs — irreducible quadratic factors of the characteristic polynomial — correspond to two-dimensional invariant subspaces. The $2\times2$ blocks that show up along the diagonal of the almost upper-triangular matrix give rise to the eigenpairs of $T$.

April 2, 2009 Posted by | Algebra, Linear Algebra | 4 Comments

## Almost Upper-Triangular Matrices

Over an algebraically closed field we can always find an upper-triangular matrix for any linear endomorphism. Over the real numbers we’re not quite so lucky, but we can come close.

Let $T:V\rightarrow V$ be a linear transformation from a real vector space $V$ of dimension $d$ to itself. We might not be able to find an eigenvector — a one-dimensional invariant subspace — but we know that we can find either a one-dimensional or a two-dimensional invariant subspace $U_1\subseteq V$. Just like before we get an action of $T$ on the quotient space $V/U_1$. Why? Because if we have two representatives $v$ and $w$ of the same vector in the quotient space, then we can write $w=v+u$. Acting by $T$, we find $Tw=Tv+Tu$. And since $Tu\in U_1$, the vectors $Tv$ and $Tw$ are again equivalent in the quotient space.

Now we can find a subspace $\hat{U}_2\subseteq V/U_1$ which is invariant under this action of $T$. Is this an invariant subspace of $V$? No, it’s not even a subspace of $V$. But we could pick some $U_2\subseteq V$ containing a unique representative for each vector in $\hat{U}_2$. For instance, we could pick a basis of $\hat{U}_2$, a representative for each basis vector, and let $U_2$ be the span of these representatives. Is this an invariant subspace? Still, the answer is no. Let’s say $u\in U_2$ is the identified representative of $\hat{u}\in\hat{U}_2$. Then all we know is that $Tu$ is a representative of $T\hat{u}$, not that it’s the identified representative. It could have some components spilling out into $U_1$.

As we proceed, picking up either a one- or two-dimensional subspace at each step, we can pick a basis of each subspace. The action of $T$ sends each basis vector into the current subspace and possibly earlier subspaces. Writing it all out, we get a matrix that looks like

$\displaystyle\begin{pmatrix}A_1&&*\\&\ddots&\\{0}&&A_m\end{pmatrix}$

where each $A_j$ is either a $1\times1$ matrix or a $2\times2$ matrix with no eigenvalues. The $1\times1$ blocks come from the one-dimensional invariant subspaces in the construction, while the $2\times2$ blocks come from the two-dimensional invariant subspaces in the construction, though they may not be invariant once we put them back into $V$. Above the diagonal we have no control (yet) over the entries, but below the diagonal almost all the entries are zero. The only exceptions are in the $2\times2$ blocks, where we poke just barely down by one row.

We can note here that if there are $n\leq m$ two-dimensional blocks and $m-n$ one-dimensional blocks, then the total number of columns will be $2n+(m-n)=n+m=d$. Thus we must have at least $\lceil\frac{d}{2}\rceil$ blocks, and at most $d$ blocks. The latter extreme corresponds to an actual upper-triangular matrix.

April 1, 2009 Posted by | Algebra, Linear Algebra | 8 Comments