Werner's Question about COND



#2

Werner asked if it is possible to have a square matrix whose condition number computed by COND (1-norm condition number) is two orders of magnitude greater than the condition number computed as the ratio of the largest to smallest singular value (2-norm condition number) of the matrix.

The answer is yes.

Here is a 4x4 matrix whose (1-norm CN)/(2-norm CN) is 4.

[[ 1  1  1  1]
[ 1 1 -1 -1]
[ 1 -1 -1 1]
[ 1 -1 1 -1]]

I found it by numerical experiments. I knew such a matrix would have to have 4 identical singular values, so that the 2-norm CN would be 1, the smallest possible, and that helped in the search. This matrix is very interesting. If you multiply it by itself, you get 4 * the identity matrix. Or, if you divide it by 2 first, then you have a square root of the identity matrix. Divide it by 2 first and its eigenvalues are [-1 1 1 -1].

Here's an order 8 matrix whose (1-norm CN)/(2-norm CN) is 8. I found in my numerical experiments that the maximum (1-norm CN)/(2-norm CN) ratio seems to be N, where N is the dimension of the matrix. I can construct such matrices with elements which are only 1 or -1 if the dimension is a power of 2, but I don't yet know if it can be done with just 1 and -1 for other dimensions.

[[ 1  1  1  1  1  1  1  1]
[ 1 1 1 1 -1 -1 -1 -1]
[ 1 1 -1 -1 1 1 -1 -1]
[ 1 1 -1 -1 -1 -1 1 1]
[ 1 -1 1 -1 1 -1 1 -1]
[ 1 -1 1 -1 -1 1 -1 1]
[ 1 -1 -1 1 1 -1 -1 1]
[ 1 -1 -1 1 -1 1 1 -1]]

This matrix is also a square root of the identity matrix if you divide it by SQRT(8) first. Divide it by SQRT(8) first and its eigenvalues are [-1 1 -1 1 1 -1 1 -1].

The maximum (1-norm CN)/(2-norm CN) ratio is N for an N x N square matrix where N is a power of 2, so a 128 x 128 matrix could have a condition number computed by COND which is more than two orders of magnitude greater than the 2-norm condition number.

If anyone wants to join the fun, try to find a matrix whose (1-norm CN)/(2-norm CN) ratio is N, where N is the dimension of a square matrix, and N is not a power of two. For extra points, find a general procedure to do this for any N. :-)


Forum Jump: