  Polar codes were recently introduced by Ar\i kan. They achieve the capacity
of arbitrary symmetric binary-input discrete memoryless channels under a low
complexity successive cancellation decoding strategy. The original polar code
construction is closely related to the recursive construction of Reed-Muller
codes and is based on the $2 \times 2$ matrix $\bigl[ 1 &0 1& 1 \bigr]$. It was
shown by Ar\i kan and Telatar that this construction achieves an error exponent
of $\frac12$, i.e., that for sufficiently large blocklengths the error
probability decays exponentially in the square root of the length. It was
already mentioned by Ar\i kan that in principle larger matrices can be used to
construct polar codes. A fundamental question then is to see whether there
exist matrices with exponent exceeding $\frac12$. We first show that any $\ell
\times \ell$ matrix none of whose column permutations is upper triangular
polarizes symmetric channels. We then characterize the exponent of a given
square matrix and derive upper and lower bounds on achievable exponents. Using
these bounds we show that there are no matrices of size less than 15 with
exponents exceeding $\frac12$. Further, we give a general construction based on
BCH codes which for large $n$ achieves exponents arbitrarily close to 1 and
which exceeds $\frac12$ for size 16.
