# Prove that any Hermitian Matrix is a real linear combination of Pauli operators [duplicate]

This is an important result in Quantum Computing because it means that the Hamiltonian of a Quantum System can be encoded as a sequence of real numbers and their corresponding Pauli Operator.

How do we prove this result?

(Note I am assuming that the Hermitian is of size $$2^n \times 2^n$$, and so by Pauli Operator I mean n-fold tensor products of the 2x2 Pauli Matrices)

Consider an arbitrary $$2\times 2$$ matrix: $$M=\left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$$ What does it mean to impose that $$M$$ is Hermitian, $$M=M^\dagger$$? $$a=a^\star, b=c^\star,d=d^\star$$ By that token, $$a$$ and $$d$$ are real and, if we write $$c=x+iy$$ for real $$x,y$$, then $$b=x+iy$$. Thus, we can write the matrix as $$M=\left(\begin{array}{cc} a & x-iy \\ x+iy & d \end{array}\right).$$ You can readily verify that this is the same as $$\frac{a+d}{2}I+xX+yY+\frac{a-d}{2}Z.$$ All four coefficients are real.
To think about the general case of $$n$$ qubits, realise that we can use a basis of $$x\in\{0,1\}^n$$. There are diagonal terms like $$a|x\rangle\langle x|$$ which you can show how to construct from Paulis: $$\bigotimes_{i=1}^n\frac{I+(-1)^{x_i}Z}{2}$$ Then there are terms $$(a+ib)|x\rangle\langle y|+(a-ib)|y\rangle\langle x|)$$. For these, use the construction $$|0\rangle\langle 1|=\frac12(X+iY)$$ for qubits $$i$$ where $$x_i\neq y_i$$, and the same construction as for the diagonal case whenever $$x_i=y_i$$. It should quickly be clear that we can use just tensor products of Paulis. It might take a little more care to be clear that the imaginary components all vanish.