Login
Login

Krawtchouk matrices

In mathematics, Krawtchouk matrices are matrices whose entries are values of Krawtchouk polynomials at nonnegative integer points.{{cite book |first=N. |last=Bose |title=Digital Filters: Theory and Applications |publisher=North-Holland Elsevier |location=New York |year=1985 |isbn=0-444-00980-9 }}{{cite book |arxiv=quant-ph/0702073 |first1=P. |last1=Feinsilver |first2=J. |last2=Kocik |title=Krawtchouk polynomials and Krawtchouk matrices |series=Recent Advances in Applied Probability |publisher=Springer-Verlag |year=2004 |bibcode=2007quant.ph..2073F }} The Krawtchouk matrix K(N) is an {{nobr|(N + 1) × (N + 1)}} matrix. The first few Krawtchouk matrices are:

:

K^{(0)} = \begin{bmatrix}

1

\end{bmatrix},

\qquad

K^{(1)} = \left[ \begin{array}{rr}

1 & 1 \\

1 & -1

\end{array} \right],

\qquad

K^{(2)} = \left[ \begin{array}{rrr}

1 & 1 & 1 \\

2 & 0 & -2 \\

1 & -1 & 1

\end{array} \right],

\qquad

K^{(3)} = \left[ \begin{array}{rrrr}

1 & 1 & 1 & 1 \\

3 & 1 & -1 & -3 \\

3 & -1 & -1 & 3 \\

1 & -1 & 1 & -1

\end{array} \right],

:

K^{(4)} = \left[ \begin{array}{rrrrr}

1 & 1 & 1 & 1 & 1 \\

4 & 2 & 0 & -2 & -4 \\

6 & 0 & -2 & 0 & 6 \\

4 & -2 & 0 & 2 & -4 \\

1 & -1 & 1 & -1 & 1

\end{array} \right],

\qquad

K^{(5)} = \left[ \begin{array}{rrrrrr}

1 & 1 & 1 & 1 & 1 & 1 \\

5 & 3 & 1 & -1 & -3 & -5 \\

10 & 2 & -2 & -2 & 2 & 10 \\

10 & -2 & -2 & 2 & 2 & -10 \\

5 & -3 & 1 & 1 & -3 & 5 \\

1 & -1 & 1 & -1 & 1 & -1

\end{array} \right].

Definition

In general, for positive integer N, the entries K^{(N)}_{ij} are given by the generating function:

: (1 + v)^{N-j}\,(1 - v)^j = \sum_i v^i K^{(N)}_{ij},

where the row and column indices i and j run from 0 to N. Explicitly:

: K^{(N)}_{ij} = \sum_k (-1)^k \binom{j}{k} \binom{N - j}{i - k},

or in terms of the Krawtchouk polynomials:

: K^{(N)}_{ij} = \kappa_i(j, N).

The values of a Krawchouk matrix can also be calculated using a recurrence relation. Filling the top row with ones and the rightmost column with alternating binomial coefficients, the other entries are each given by the sum of the neighbouring entries to the top, topright and right.{{cite arXiv |last1=Feinsilver |first1=P. |last2=Kocik |first2=J. |date=2007 |title=Krawtchouk matrices from classical and quantum random walks |eprint=quant-ph/0702173}}

Properties

The Krawtchouk polynomials are orthogonal with respect to symmetric binomial distributions, p = 1/2.{{cite web |url=http://dlmf.nist.gov/18.19 |title=Hahn Class: Definitions |work=Digital Library of Mathematical Functions }}

As a transformation, a Krawtchouk matrix is an involution up to scaling:

: (K^{(N)}_{ij})^2 = 2^N I.

Krawchouk matrices have an LDU decomposition involving triangular Pascal matrices and a diagonal matrix of the powers of 2.{{Cite journal |last1=Boyd |first1=Geoff |last2=Micchelli |first2=Charles A. |last3=Strang |first3=Gilbert |last4=Zhou |first4=Ding-Xuan |date=2001 |title=Binomial Matrices |url=https://www.academia.edu/9731547 |journal=Advances in Computational Mathematics |language=en |volume=14 |issue=4 |pages=379–391 |doi=10.1023/A:1012207124894 |s2cid=36314402 |issn=1572-9044}}

The eigenvalues are \pm \sqrt{2^n}, and the determinant is (-2)^{n(n+1)/2}.

See also

References

{{reflist}}

External links

  • [http://chanoir.math.siu.edu/kravchyk/Introduction Krawtchouk encyclopedia]

{{Matrix classes}}

Category:Matrices (mathematics)

{{matrix-stub}}