Householder Similarity Transforms

In [2]:
import numpy as np
import numpy.linalg as la

np.set_printoptions(precision=2, linewidth=150)
In [3]:
n = 8

e1 = np.zeros(n); e1[0] = 1
e2 = np.zeros(n); e2[1] = 1

A = np.random.randn(n, n)
A
Out[3]:
array([[ 1.05,  1.08,  0.77, -1.41,  0.85, -0.34,  0.67, -2.02],
       [-1.52,  0.4 , -1.08, -0.08,  0.12,  0.43,  1.04,  2.06],
       [ 1.06,  0.4 , -0.85,  1.81, -0.25, -0.65, -0.06,  0.56],
       [-2.18, -1.83,  1.19, -0.21, -1.18, -1.2 ,  0.35,  1.22],
       [-0.21, -0.8 ,  0.2 ,  0.9 , -0.8 , -0.28,  2.3 ,  1.56],
       [ 1.55,  1.55,  1.03, -0.91,  0.05,  0.3 , -0.41,  0.43],
       [-0.44, -0.92, -1.14, -0.43, -0.6 , -1.05, -1.9 , -0.5 ],
       [ 1.19, -0.66, -1.39, -1.35,  0.83, -1.2 ,  1.76, -0.72]])

Now try to zero the first column with a similarity transform.

Starting in the first row

In [4]:
a = A[:, 0].copy()
v = a-la.norm(a)*e1

H1 = np.eye(n) - 2*np.outer(v, v)/(v@v)
In [5]:
H1@A
Out[5]:
array([[  3.66e+00,   1.95e+00,  -1.71e-01,  -5.52e-01,   1.24e+00,   1.29e-01,   2.61e-02,  -2.09e+00],
       [  2.24e-16,   9.07e-01,  -1.63e+00,   4.23e-01,   3.42e-01,   7.02e-01,   6.64e-01,   2.02e+00],
       [ -1.14e-16,   4.67e-02,  -4.70e-01,   1.46e+00,  -4.03e-01,  -8.46e-01,   2.05e-01,   5.92e-01],
       [  3.85e-16,  -1.10e+00,   3.98e-01,   5.12e-01,  -8.57e-01,  -8.08e-01,  -1.83e-01,   1.17e+00],
       [  3.34e-17,  -7.27e-01,   1.25e-01,   9.67e-01,  -7.66e-01,  -2.40e-01,   2.24e+00,   1.55e+00],
       [ -1.88e-16,   1.02e+00,   1.60e+00,  -1.42e+00,  -1.82e-01,   2.04e-02,  -3.10e-02,   4.73e-01],
       [  3.06e-17,  -7.74e-01,  -1.29e+00,  -2.87e-01,  -5.34e-01,  -9.70e-01,  -2.01e+00,  -5.13e-01],
       [ -1.46e-16,  -1.06e+00,  -9.55e-01,  -1.74e+00,   6.56e-01,  -1.42e+00,   2.06e+00,  -6.85e-01]])
In [6]:
H1@A@H1.T
Out[6]:
array([[-0.18, -0.29,  1.39, -3.77,  0.92,  2.42, -0.62, -0.33],
       [-0.25,  0.76, -1.53,  0.22,  0.32,  0.85,  0.62,  2.14],
       [-1.19, -0.65,  0.02,  0.46, -0.5 , -0.13,  0.01,  1.14],
       [ 0.38, -0.88,  0.24,  0.83, -0.83, -1.03, -0.12,  0.99],
       [-0.06, -0.76,  0.15,  0.92, -0.77, -0.21,  2.23,  1.58],
       [ 1.06,  1.64,  1.17, -0.53, -0.1 , -0.61,  0.15, -0.01],
       [-0.19, -0.89, -1.22, -0.45, -0.55, -0.86, -2.04, -0.42],
       [ 0.1 , -1.01, -1.  , -1.66,  0.66, -1.47,  2.07, -0.73]])

Starting in the second row

In [7]:
a = A[:, 0].copy()
a[0] = 0
v = a-la.norm(a)*e2

H2 = np.eye(n) - 2*np.outer(v, v)/(v@v)
In [8]:
H2 @ A
Out[8]:
array([[  1.05e+00,   1.08e+00,   7.72e-01,  -1.41e+00,   8.52e-01,  -3.42e-01,   6.65e-01,  -2.02e+00],
       [  3.50e+00,   1.71e+00,  -4.11e-01,  -1.52e-01,   1.04e+00,   2.38e-01,  -1.73e-01,  -1.57e+00],
       [ -1.64e-16,   1.25e-01,  -9.96e-01,   1.82e+00,  -4.40e-01,  -6.14e-01,   2.00e-01,   1.33e+00],
       [  9.81e-17,  -1.26e+00,   1.48e+00,  -2.38e-01,  -7.81e-01,  -1.28e+00,  -1.73e-01,  -3.54e-01],
       [ -2.17e-18,  -7.42e-01,   2.30e-01,   8.94e-01,  -7.59e-01,  -2.86e-01,   2.24e+00,   1.41e+00],
       [ -9.33e-17,   1.14e+00,   8.27e-01,  -8.85e-01,  -2.36e-01,   3.60e-01,  -3.79e-02,   1.56e+00],
       [ -3.71e-17,  -8.06e-01,  -1.08e+00,  -4.36e-01,  -5.19e-01,  -1.07e+00,  -2.01e+00,  -8.16e-01],
       [  3.82e-17,  -9.77e-01,  -1.55e+00,  -1.33e+00,   6.14e-01,  -1.16e+00,   2.05e+00,   1.46e-01]])
In [9]:
H2 @ A @ H2.T
Out[9]:
array([[  1.05e+00,  -3.30e-01,   1.07e+00,  -2.02e+00,   7.93e-01,   9.28e-02,   5.44e-01,  -1.68e+00],
       [  3.50e+00,  -1.25e+00,   2.14e-01,  -1.44e+00,   9.11e-01,   1.15e+00,  -4.29e-01,  -8.72e-01],
       [ -1.64e-16,  -1.31e+00,  -6.93e-01,   1.20e+00,  -5.01e-01,  -1.71e-01,   7.60e-02,   1.67e+00],
       [  9.81e-17,   5.23e-01,   1.10e+00,   5.37e-01,  -7.06e-01,  -1.84e+00,  -1.85e-02,  -7.78e-01],
       [ -2.17e-18,  -4.56e-02,   8.30e-02,   1.20e+00,  -7.29e-01,  -5.01e-01,   2.31e+00,   1.24e+00],
       [ -9.33e-17,   1.01e+00,   8.53e-01,  -9.38e-01,  -2.41e-01,   3.98e-01,  -4.86e-02,   1.59e+00],
       [ -3.71e-17,  -1.74e-01,  -1.21e+00,  -1.62e-01,  -4.92e-01,  -1.26e+00,  -1.95e+00,  -9.66e-01],
       [  3.82e-17,   3.19e-02,  -1.76e+00,  -8.97e-01,   6.57e-01,  -1.47e+00,   2.14e+00,  -9.35e-02]])
In [ ]: