Golub-Kahan Bidiagonalization Step

Problem

Perform one Golub-Kahan bidiagonalization step on a 3x3 matrix A.

First build the Householder vector for column 0 with alpha = -sign(A[0][0]) * ||column||, apply H = I - 2*v*v^T on the left to zero the entries below A[0][0]. Then build the Householder vector for row 0 restricted to columns 1..2 and apply the corresponding reflection on the right to zero A[0][2]. Return the transformed matrix.

Hint

Alternating left and right Householder reflections reduces a matrix toward bidiagonal form.

Test cases

case 1

in: [[[1,2,3],[4,5,6],[7,8,9]]]

expected: [[-8.12403840463596,14.659777996582722,0],[0,0.18622796258629076,-0.0476397113592843],[0,1.9506304625241173,-0.4989984904131466]]

case 2

in: [[[2,1,0],[1,3,1],[0,1,2]]]

expected: [[-2.23606797749979,2.280350850198276,0],[0,-2.368056652128979,0.4385290096535146],[0,-1.3728129459672882,1.7650452162436563]]

case 3

in: [[[1,0,0],[0,1,0],[0,0,1]]]

expected: [[-1,0,0],[0,1,0],[0,0,1]]

case 4

in: [[[4,1,2],[1,3,0],[2,0,5]]]

expected: [[-4.58257569495584,4.214487485081046,0],[0,-0.336871404178687,-2.771882313769431],[0,-3.1590885991341624,1.8604947074836544]]

Starter codePython

def bidiagonal_step(A):
    # Your code here
    pass

4 test cases · run your code against them in the editor