Particle Hole Symmetry of BdG Hamiltonians It is straight-forward to verify that any Hermitian BdG Hamiltonian of the form
$$
\mathcal{H} = (c_1^\dagger, c_1, c_2^\dagger, c_2,...) 
\begin{pmatrix}
H_{11} & H_{12} & \cdots \\ 
H_{21} & H_{22} & \cdots \\
\vdots & \vdots & \ddots
\end{pmatrix}
\begin{pmatrix}
c_1 \\ c_1^\dagger\\ c_2 \\ c_2^\dagger \\ \vdots
\end{pmatrix}
$$
with $2\times2$ blocks $H_{ij}$ satisfies the the particle-hole symmetry $\sigma^x H_{ij}^* \sigma^x = -H_{ij}$. This is for example als confirmed in this question or this answer.
Because of the fermionic relations $\{c_i, c_j\} = \{c_i^\dagger, c_j^\dagger\}=0$ and $\{c_i, c_j^\dagger\}=\delta_{ij}$ the entries of the $2 \times 2$ blocks are not uniquely determined. Consider a $i \neq j$ term of the form $A c_i^\dagger c_j + B c_i c_j + h.c.$ with complex coefficients $A$ and $B$. Then we have
$$
2A c_i^\dagger c_j + h.c. = 2A c_i^\dagger c_j + 2A^\star c_j^\dagger c_i = A c_i^\dagger c_j + A^\star c_j^\dagger c_i - A c_j c_i^\dagger - A^\star c_i c_j^\dagger
$$
and
$$
2B c_i c_j + h.c. = 2B c_i c_j + 2B^\star c_j^\dagger c_i^\dagger = B c_i c_j + B^\star c_j^\dagger c_i^\dagger - B c_j c_i - 2B^\star c_i^\dagger c_j^\dagger
$$
and hence get
$$
H_{ij} = \begin{bmatrix} A & -B^\star \\ B &-A^\star \end{bmatrix}
$$
and
$$
 H_{ji} = \begin{bmatrix} A^\star & -B \\ B^\star & -A \end{bmatrix}.
$$
The same is true for $H_{ii}$ where the relations $c_i^2 = c_i^{\dagger,2}$ imply that the off-diagonal entries are 0.
Now one easily sees that we have the anti-commuting, anti-unitary symmetry
$$
 \sigma^x H_{ij}^\star \sigma^x = - H_{ij}
$$
since conjugation with $\sigma^x$ is simply point-mirroring the matrix
around the center.
This implies that all superconductors have this PHS, since they are written with such Hamiltonians.
Now my question is: What stops me from taking any single-particle Hamiltonian like
$$\mathcal{H} = (c_1^\dagger, c_2^\dagger, ...) 
\begin{pmatrix}
H_{11} & H_{12} & \cdots \\ 
H_{21} & H_{22} & \cdots \\
\vdots & \vdots & \ddots
\end{pmatrix}
\begin{pmatrix}
c_1 \\ c_2 \\ \vdots
\end{pmatrix}
$$
with single matrix elements $H_{ij}$, write it in the first form with a BdG Hamiltonian (without any $c_i c_j$ or $c_i^\dagger c_j^\dagger$ terms) and say it also has above PHS? Wouldn't this defintion of PHS imply that all Hamiltonians of non-interacting fermions are particle-hole symmetric?
edit:
Added explanation why all hermitian BdG Hamiltonians are particle-hole symmetric.
 A: In a sense you are correct: one can always use the BdG trick to write
$$
\psi^\dagger H \psi = \frac 12 (\psi^\dagger, \psi)\left(\matrix{ H&0\cr 0 &-H^T}\right)\left(\matrix{\psi \cr \psi^\dagger}\right)+ \frac 12 {\rm Tr}\{ H\}\\
= \frac 12 (\psi^\dagger, \psi)\left(\matrix{ H&0\cr 0 &-H^*}\right)\left(\matrix{\psi \cr \psi^\dagger}\right)+ \frac 12 {\rm Tr}\{ H\} .
$$
If we ignore the  ${\rm Tr}\{ H\}$ this satisfies
$$
\left(\matrix{0&1\cr 1&0}\right) \left(\matrix{ H&0\cr 0 &-H^*}\right)\left(\matrix{0&1\cr 1&0}\right)= \left(\matrix{ -H^*&0\cr 0 &H}\right)
$$
which is the particle-hole symmetry condition.   Of course we have artificially doubled the number of degrees of freedom in the one-particle hamiltonian $H$ but at the same time introduced a Majorana condition
$$
\Psi^\dagger = \left(\matrix{0&1\cr 1&0}\right)\Psi, \quad \Psi =\left(\matrix{\psi\cr \psi^\dagger}\right)
$$
on the many-body system. In the new system there  is  a $-E_n$ one-particle state for each $E_n$ state, and in the new many-body ground ground state  all the negative energy levels are filled.  If we empty a negative energy state this is the same as occupying one of the original positive energy states, and at the level of the many body system (and taking note of the ${\rm Tr}\{ H\}$ that cancels the energy of the new negative energy filled ground state) we have exactly the same system as before.
So the bottom line is that at the level of one-particle physics, the BdG particle-hole symmetry is an artificial thing, but one that is useful in the superconductor case as long as one is careful not to overcount doubled contributions, and to   always bult excitations on the  new BdG Cooper-pair ground state and not the original one.
A: Your first statement is a little ambiguous, let me rephrase it.
Any Hermitian Hamiltonian of the form
$$
\mathcal{H} = (c_1^\dagger, c_1, c_2^\dagger, c_2,...) 
\begin{pmatrix}
H_{11} & H_{12} & \cdots \\ 
H_{21} & H_{22} & \cdots \\
\vdots & \vdots & \ddots
\end{pmatrix}
\begin{pmatrix}
c_1 \\ c_1^\dagger\\ c_2 \\ c_2^\dagger \\ \vdots
\end{pmatrix}
$$
is particle-hole symmetric, and therefore represent a BdG Hamiltonian,
if and only if $\sigma^x H_{ij}^* \sigma^x = -H_{ij}$.
Analogously, your second Hamiltonian
$$\mathcal{H} = (c_1^\dagger, c_2^\dagger, ...) 
\begin{pmatrix}
H_{11} & H_{12} & \cdots \\ 
H_{21} & H_{22} & \cdots \\
\vdots & \vdots & \ddots
\end{pmatrix}
\begin{pmatrix}
c_1 \\ c_2 \\ \vdots
\end{pmatrix}
$$
has particle-hole symmetry, and therefore can be thought as a BdG Hamiltonian, if and only if $\sigma^x H_{ij}^* \sigma^x = -H_{ij}$.
Not all Hermitian Hamiltonians satisfy this condition. For example if you take one of the block to be
$$
H_{11}=\begin{pmatrix} E & W \\ W^*& E' \end{pmatrix}
$$ you do not have particle-hole symmetry in the general case $E\neq-E'$, but only if $E=-E'$.
In summary, not all Hermitian Hamiltonians of non-interacting fermions are particle-hole symmetric. A simple counterexample is
$$\mathcal{H} = (c_1^\dagger, c_2^\dagger, ...) 
\begin{pmatrix}
H_{11} & H_{12}  \\ 
H_{12}^\dagger & H_{22}  \\
\end{pmatrix}
\begin{pmatrix}
c_1 \\ c_2 \\ \vdots
\end{pmatrix}
$$ where
$$
H_{ii}=\begin{pmatrix} E_i & W_i \\ W_i^*& E_i' \end{pmatrix}
$$ with $E'_i\neq-E_i$. Same argument apply to bosonic Hamiltonians, and to interacting Hamiltonians (in this case the Hamiltonian has a little more complicated form).
A: First of all, in your last paragraph, you make references to fermions. BdG hamiltonians may also represent bosonic systems.
The particle-hole symmetry is necessary to ensure that the time-evolved creation and annihilation operators are related by the adjoint operation, i. e. $c_j(t)^{\dagger} = c_j^{\dagger}(t)$. Mathematically speaking, time-evolution and taking the adjoint commute with one another. To see this, you can write out the equation of motion for $\bigl ( c_1(t) , \ldots , c_n(t) , c_1^{\dagger}(t) , \ldots , c_n^{\dagger}(t) \bigr )$ and use bosonic or fermionic commutation relations.
So it is better to think of the particle-hole “symmetry” as a consistency constraint that can never be broken. Any mathematical representation of your system needs to be consistent with this constraint.
Edit: Clarified that my arguments apply to bosonic and fermionic BdG systems alike; hat tip to @sintetico for the correction.
