A matrix is said to be in upper Hessenberg form if its elements
for all 
. Therefore,
Given 
, let 
be the unitary matrix
where is formed by the Householder
transformation for the column vector
. Thus,
It is clear that 
does not change the first column of
. Repeating this procedure, 
is transformed by
orthogonal similarity transformations into an upper Hessenberg matrix.