Householder reduction to Hessenberg form

Question

I've read somewhere that Hessenberg decomposition is not unique unless the first column of $Q$ in $Q^{T}AQ =H$ is specified. But then, if I am given a matrix $A \in R^{n \times n}$, I can apply the Householder reduction algorithm to reduce $A$ to Hessenberg form $H$ which is the unique output of the algorithm. Then how is that not unique?

Answer 1

Every $2\times 2$ matrix $A$ is already in Hessenberg form. If you choose a transformation matrix $Q$ (it can be also orthogonal) and compute

$$B = QAQ^{-1}\text{,}$$

then probably, $A\neq B$ for some $Q$s.