Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Mostre que se cada elemento \( k \) em uma 'orthogonal array' for substituído por \( e^{2 \pi k i / n} \), as linhas viram vetores ortogonais no sentido usual (seu produto interno e igual a zero).

0 votos
27 visitas
perguntada Ago 23 em Matemática por VITOR B BORGES (1 ponto)  

A pergunta corresponde ao exercício 20 localizado na página 37 do Capítulo 7 - Combinatorial Searching do livro "The Art of Computer Programming - Volume 4A" de Donald Ervin Knuth.

Compartilhe

1 Resposta

0 votos
respondida Ago 23 por VITOR B BORGES (1 ponto)  
editado Ago 24 por VITOR B BORGES

O livro define a estrutura matemática 'orthogonal array' da seguinte maneira:

A string \( x_1 x_2 ... x_N \) é chamada \( n-ária \) se cada elemento \( x_j \) pertence ao conjunto \( \{0, 1, ..., n - 1\} \) de dígitos \( n-ários \). As duas strings \( x_1 x_2 ... x_N \) e \( y_1 y_2 ... y_N \) são ditas \( ortogonais \) se os \( N \) pares \( (x_j,y_j) \) são distintos para \( 1 \leq j \leq N \). (Consequentemente, duas strings \( n-árias \) não podem ser ortogonais se o seu comprimento superar \( n^2 \).) Uma matriz \( n-ária \) com \( m \) linhas e \( n^2 \) colunas cujas linhas são ortogonais entre si é chamada 'orthogonal array' de ordem \( n \) e profundidade \( m \).

Esta definição abstrata fica mais clara com um exemplo de 'orthogonal array' de ordem 4 e profundidade 5:

A imagem será apresentada aqui.

Se aplicarmos a transformação \( k = e^{2k\pi i / n} \) em todos os elementos, o produto interno entre dois vetores linhas \( \textbf x, \textbf y \) quaisquer pode ser expresso por:

\[ \begin{split} \textbf x \cdot \textbf y & = \sum_{k=1}^{n^2} e^{(\frac{2\pi i}{n} \cdot x_k)} \cdot e^{(\frac{2\pi i}{n} \cdot y_k)}\\ & = \sum_{k=1}^{n^2} e^{( \frac{2\pi i}{n} \cdot x_k + \frac{2\pi i}{n} \cdot y_k )} \\ & = \sum_{k=1}^{n^2} e^{\frac{2\pi i}{n} (x_k + y_k)} \end{split} \]

Note que todos os pares ordenados \( \{ (h, j) | h,j \in \{ 0, 1, ..., n - 1 \} \} \) vão aparecer neste somatório, então a ordem que nós somamos eles não importa, por isso podemos escrever:

\[ \sum_{k=1}^{n^2} e^{\frac{2\pi i}{n} (x_k + y_k)} = \sum_{h = 0}^{n - 1} \sum_{j = 0}^{n - 1} e^{\frac{2\pi i}{n} (h + j)} \]

À partir de agora \( e^{\frac{2\pi i}{n} } = \beta \), para facilitar a notação.

Vamos representar este duplo somatório da seguinte forma para melhorar a visualização do problema:

\[ \Rightarrow \sum_{h = 0}^{n - 1} \sum_{j = 0}^{n - 1} \beta^{(h + j)} = \\ \begin{matrix} & j = 0 & j = 1 & j = 2 & ... & j = n-3 & j = n-2 & j = n-1 \\ h = 0 & \beta^{0} & \beta^{1} & \beta^{2} & ... & \beta^{n-3} & \beta^{n-2} & \beta^{n-1} \\ h = 1 & \beta^{1} & \beta^{2} & \beta^{3} & ... & \beta^{n-2} & \beta^{n-1} & \beta^{n}\\ h = 2 & \beta^{2} & \beta^{3} & \beta^{4} & ... & \beta^{n-1} & \beta^{n} & \beta^{n+1}\\ ... & & ... & & & & ... \\ h = n-3 & \beta^{n-3} & \beta^{n-2} & \beta^{n-1} & ... & \beta^{n+n-6} & \beta^{n+n-5} & \beta^{n+n-4} \\ h = n-2 & \beta^{n-2} & \beta^{n-1} & \beta^{n} & ... & \beta^{n+n-5} & \beta^{n+n-4} & \beta^{n+n-3} \\ h = n-1 & \beta^{n-1} & \beta^{n} & \beta^{n+1} & ... & \beta^{n+n-4} & \beta^{n+n-3} & \beta^{n+n-2} \\ \end{matrix} \]

Precisamos somar todos os elementos acima, olhando para a diagonal secundária note que o elemento \( \beta^{n - 1} \) aparece \( n \) vezes, na verdade isto acontece para todos os elementos que ficam em cima da diagonal secundária, podemos escrever esta parte da soma como:

\[ \sum_{k = 0}^{n-1} (k + 1)\beta^k \]

Ohando agora para o que está em baixo da diagonal secundária, percebemos que cada termo \( \{ \beta^{n + y} | y \in \{ 0, 1, ..., n-2 \} \} \) aparece \( (n - z - 1) \) vezes, tal que \( z \in \{ 0, 1, ..., n-2 \} \), podemos escrever esta parte da soma como:

\[ \sum_{k = 0}^{n-2} (n - k - 1)\beta^{n + k} \]

Somando estas duas partes temos:

\[ \begin{align*} \textbf x \cdot \textbf y & = \sum_{k = 0}^{n-1} (k + 1)\beta^k + \sum_{k = 0}^{n-2} (n - k - 1)\beta^{n + k} \\ & = \sum_{k = 0}^{n-1} (k + 1)e^{\frac{2\pi i}{n} k} + \sum_{k = 0}^{n-2} (n - k - 1)e^{\frac{2\pi i}{n}(n + k)} \\ \end{align*} \]

Aplicando a identidade de Euler: \( e^{xi} = \cos(x) + i\sin(x) \)

\[ \begin{align*} \textbf x \cdot \textbf y & = \sum_{k = 0}^{n-1} (k + 1)\left(\cos\left(k\frac{2\pi}{n}\right) + i\sin\left(k\frac{2\pi}{n}\right)\right) \\ & + \sum_{k = 0}^{n-2} (n - k - 1)\left(\cos\left((n + k)\frac{2\pi}{n}\right) + i\sin\left((n + k)\frac{2\pi}{n}\right)\right) \\ & = \sum_{k = 0}^{n-1} (k + 1)\cos\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\cos\left((n + k)\frac{2\pi}{n}\right) \\ & + i \left( \sum_{k = 0}^{n-1} (k + 1)\sin\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\sin\left((n + k)\frac{2\pi}{n}\right) \right) \end{align*} \]

Vamos decompor a simplificação desta expressão em PARTE REAL e PARTE IMAGINÁRIA, começando pela PARTE REAL:

\[ \begin{align*} & = \sum_{k = 0}^{n-1} (k + 1)\cos\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\cos\left((n + k)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-1} (k + 1)\cos\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\cos\left(2\pi + k\frac{2\pi}{n}\right) \\ \\ & \cos(2\pi + x) = \cos(x) \\ \\ & = \sum_{k = 0}^{n-1} (k + 1)\cos\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\cos\left(k\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} (k + 1)\cos\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\cos\left(k\frac{2\pi}{n}\right) +n\cos\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( (k + 1)\cos\left(k\frac{2\pi}{n}\right) + (n - k - 1)\cos\left(k\frac{2\pi}{n}\right) \right) +n\cos\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( (k + 1 + n - k - 1)\cos\left(k\frac{2\pi}{n}\right) \right) + n\cos\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( n\cos\left(k\frac{2\pi}{n}\right) \right) + n\cos\left((n - 1)\frac{2\pi}{n}\right) \\ & = n\sum_{k = 0}^{n-1} \cos\left(k\frac{2\pi}{n}\right) \\ \end{align*} \]

A mesma simplificação pode ser feita para a PARTE IMAGINÁRIA:

\[ \begin{align*} & = \sum_{k = 0}^{n-1} (k + 1)\sin\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\sin\left((n + k)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-1} (k + 1)\sin\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\sin\left(2\pi + k\frac{2\pi}{n}\right) \\ \\ & \sin(2\pi + x) = \sin(x) \\ \\ & = \sum_{k = 0}^{n-1} (k + 1)\sin\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\sin\left(k\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} (k + 1)\sin\left(k\frac{2\pi}{n}\right) + \sum_{k = 0}^{n-2} (n - k - 1)\sin\left(k\frac{2\pi}{n}\right) +n\sin\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( (k + 1)\sin\left(k\frac{2\pi}{n}\right) + (n - k - 1)\sin\left(k\frac{2\pi}{n}\right) \right) +n\sin\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( (k + 1 + n - k - 1)\sin\left(k\frac{2\pi}{n}\right) \right) + n\sin\left((n - 1)\frac{2\pi}{n}\right) \\ & = \sum_{k = 0}^{n-2} \left( n\sin\left(k\frac{2\pi}{n}\right) \right) + n\sin\left((n - 1)\frac{2\pi}{n}\right) \\ & = n\sum_{k = 0}^{n-1} \sin\left(k\frac{2\pi}{n}\right) \\ \end{align*} \]

Podemos juntar as duas partes para chegar em:

\[ \begin{align*} \textbf x \cdot \textbf y & = n\sum_{k = 0}^{n-1} \cos\left(k\frac{2\pi}{n}\right) + ni\sum_{k = 0}^{n-1} \sin\left(k\frac{2\pi}{n}\right) \\ & = n\sum_{k = 0}^{n-1} \left( \cos\left(k\frac{2\pi}{n}\right) + i \sin\left(k\frac{2\pi}{n}\right) \right) \\ & = n\sum_{k = 0}^{n-1} e^{i\frac{2\pi k}{n}} \end{align*} \]

Note que provar que \( n\sum_{k = 0}^{n-1} e^{i\frac{2\pi k}{n}} = 0 \)é a mesma coisa que provar que \( \sum_{k = 0}^{n-1} e^{i\frac{2\pi k}{n}} = 0 \). Chamaremos então esse somatório de:

\[ \begin{align*} S_N & = \sum_{k = 0}^{n-1} e^{i\frac{2\pi k}{n}} \\ S_n e^{i\frac{2\pi}{n}} & = \sum_{k = 0}^{n-1} e^{i\frac{2\pi (k + 1)}{n}} \\ S_n e^{i\frac{2\pi}{n}} - S_N & = \sum_{k = 0}^{n-1} e^{i\frac{2\pi (k + 1)}{n}} - \sum_{k = 0}^{n-1} e^{i\frac{2\pi k}{n}} \\ S_N(e^{i\frac{2\pi}{n}} - 1) & = e^{i2\pi} + \sum_{k = 0}^{n-2} e^{i\frac{2\pi (k + 1)}{n}} - e^0 - \sum_{k = 1}^{n-1} e^{i\frac{2\pi k}{n}} \\ & = e^{i2\pi} - 1 + \sum_{k = 0}^{n-2} e^{i\frac{2\pi (k + 1)}{n}} - \sum_{k = 0}^{n-2} e^{i\frac{2\pi (k + 1)}{n}}\\ & = e^{i2\pi} - 1 \\ \\ \Rightarrow S_N & = \frac{(e^{i2\pi} - 1)}{(e^{i\frac{2\pi}{n}} - 1)} \\ \\ & = \frac{(\cos(2\pi) + i\sin(2\pi) - 1)}{\left( cos(\frac{2\pi}{n}) + i\sin(\frac{2\pi}{n}) - 1 \right)} \\ \\ &\cos(2\pi) = 1 \\ &\sin(2\pi) = 0 \\ \\ & = \frac{(1 + i0 - 1)}{\left( cos(\frac{2\pi}{n}) + i\sin(\frac{2\pi}{n}) - 1 \right)} \\ \\ & = \frac{(0)}{\left( cos(\frac{2\pi}{n}) + i\sin(\frac{2\pi}{n}) - 1 \right)} \\ \\ & = 0 \end{align*} \]

CONCLUSÃO: \( \textbf x \cdot \textbf y = 0 \), portanto as linhas são ortogonais.

...