% Copyright (C) Volker Diels-Grabsch % Compile with: xelatex kraehenfuesse.tex && xelatex kraehenfuesse.tex \documentclass[paper=a4,twoside=semi,toc=bib,obeyspaces]{scrartcl} \usepackage{xltxtra} \usepackage{polyglossia} \setdefaultlanguage[spelling=new,babelshorthands=true]{german} \usepackage{xcolor} \usepackage{graphicx} \usepackage{longtable} \usepackage{array} \usepackage{enumitem} \usepackage{amsmath} \usepackage{amssymb} \usepackage{hyperxmp} % For "ntheorem" versus amsthm, see: % https://tex.stackexchange.com/questions/5599/theorem-packages-which-to-use-which-conflict %\usepackage[hyperref]{ntheorem} \usepackage{amsthm} % Don't use "hypcap" package, instead use "caption" package with "hypcap", see: % http://tex.stackexchange.com/questions/141931/clickable-hyperlinks-wrong-for-sidewaysfigure \usepackage[hypcap=true]{caption} \usepackage[hidelinks]{hyperref} \usepackage[capitalise,nameinlink,noabbrev]{cleveref} \usepackage{comment} \usepackage{mathtools} \usepackage{icomma} % Correct spacing for german decimal numbers, e.g. "109,5" \usepackage{easylist} \usepackage{xifthen} \usepackage{tikz} \usetikzlibrary{calc} \usepackage{setspace} \usepackage{textcomp} \usepackage{gensymb} \usepackage{etoolbox} \usepackage{multicol} \usepackage{endnotes} \usepackage{colonequals} \usepackage{adjustbox} \usepackage{rotating} \usepackage{quoting} \usepackage{float} \usepackage{scrhack} % Fix KOMA-Script warning caused by the "float" package \usepackage{tocstyle} \usepackage[markup=nocolor,deletedmarkup=xout]{changes} \hypersetup{pdflang={de}} % Must be specified before \begin{document} % This fixes "Underfull \hbox" issues in the bibliography, see: % http://tex.stackexchange.com/a/10928 % http://tex.stackexchange.com/q/266621 \apptocmd{\sloppy}{\hbadness 4000\relax}{}{} % Configuration of endnotes \renewcommand{\notesname}{Referenzen} \renewcommand{\makeenmark}{[\theenmark] } % Increase maximum number of rows and columns in pmatrix environments \setcounter{MaxMatrixCols}{12} \theoremstyle{plain} \newtheorem*{lemma}{Lemma} \newtheorem*{theorem}{Satz} \theoremstyle{definition} \newtheorem*{definition}{Definition} \newtheorem*{example}{Beispiel} \newcommand{\ip}[2]{\langle{#1},{#2}\rangle} \newcommand{\norm}[1]{\lVert{#1}\rVert} \newcommand{\smalllegendre}[2]{\big(\frac{#1}{#2}\big)} \newcommand{\TODO}[2]{\begin{center}$\vdots$\par\fcolorbox{black}{yellow}{TODO:~{#1}}\par$\vdots$\end{center}} \begin{document} \title{Ganzzahlige Krähenfüße} \author{Volker Diels-Grabsch} \date{6.~Januar~2018} \maketitle \tableofcontents \section{Einleitung} Der Artikel \emph{Höherdimensionale Krähenfüße}~\endnote{% Höherdimensionale Krähenfüße, Armin Singer, Wurzel 1/2017, S.~12-17} warf viele interessante Fragen auf, von denen wir einige beantworten wollen. Unser Plan sieht wie folgt aus: Zuerst machen wir uns ganz genau klar, was Krähenfüße sind und wie wir diese als Matrizen notieren. Auf Basis dieser Notation präzisieren wir unsere Fragestellung nach "`ganzzahligen"' Krähenfuß-Matrizen. Dann schlagen wir eine Brücke zu den Orthonormalbasen (ONB), denn bestimmte ONB entsprechen 1:1 unseren Krähenfüßen. Dieser Zusammenhang erweist sich als äußerst fruchtbar, denn im Gegensatz zu Krähenfüßen sind ONB sehr gut erforscht. Unter anderem wurden dort die sogenannten Hadamard-Matrizen entdeckt, die wir leicht auf unsere Krähenfüße übertragen können. Zum Schluss werden wir einen alternativen Ansatz betrachten, der zusätzliche ganzzahlige Matrizen liefert, die keine Hadamard-Matrizen sind. \section{Krähenfüße} \label{Krähenfüße} Zunächst wiederholen wir, was ein Krähenfuß ist, und bemühen uns um eine möglichst einfache, klare Definition. \begin{definition}[Krähenfuß] Unter einem \emph{$n$-Krähenfuß} verstehen wir eine Menge von $n$~Einheitsvektoren $v_1, v_2, \ldots, v_n$ in einem $(n-1)$-dimensionalen Raum, die paarweise das gleiche Skalarprodukt $\ip{v_i}{v_j} = {-}\frac{1}{n-1}$ haben.\footnote{% Der Wert ${-}\frac{1}{n-1}$ ist nicht so willkürlich, wie es zunächst scheint. Übungsaufgabe: Gegeben seien $n$~Einheitsvektoren $v_1, \ldots, v_n$ im $(n-1)$-dimensionalen Raum $\mathbb{R}^{n-1}$, die paarweise das gleiche Skalarprodukt haben. Das heißt, $\ip{v_i}{v_i} = 1$ für alle $i$ und $\ip{v_i}{v_j} = c$ für alle $i \ne j$. Zeige, dass dann $c = {-}\frac{1}{n-1}$ gelten muss.} \end{definition} Da es sich um Einheitsvektoren handelt, ist dies gleichbedeutend damit, dass die Vektoren paarweise den gleichen Winkel \begin{align*} \measuredangle(v_i,v_j) &= \arccos\left({-}\frac{1}{n-1}\right) \end{align*} zueinander haben. In Koordinaten-Schreibweise notieren wir einen Krähenfuß als Liste von Spalten-Vektoren, die wir zu einer Matrix zusammenfassen. Dabei nehmen wir uns die Freiheit, "`krumme"' Vorfaktoren $\lambda$ auszuklammern: \begin{align*} K_n & = \lambda \cdot \begin{pmatrix} \vdots & & \vdots \\ v_1' & \cdots & v_n' \\ \vdots & & \vdots \\ \end{pmatrix} \end{align*} Dies sehen wir uns kurz am Beispiel der kleinsten Krähenfüße genauer an. \begin{flushleft} \begin{tikzpicture}[>=latex,scale=1.9] \path (0,-1.0) rectangle (0,1.5); % ensure vertical alignment with the other tikzpictures \draw[->,gray] (-1.2,0) -- (1.2,0) node[label=right:$x$] {}; \draw[->,very thick] (0,0) to [edge label=$v_1$] (1,0); \draw[->,very thick] (0,0) to [edge label'=$v_2$] (-1,0); \fill (0,0) circle[radius=0.04]; \end{tikzpicture} \begin{tikzpicture}[>=latex,scale=1.9] \path (0,-1.0) rectangle (0,1.5); % ensure vertical alignment with the other tikzpictures \draw[->,gray] (-1,0) -- (1,0) node[label=right:$x$] {}; \draw[->,gray] (0,-0.5) -- (0,1.2) node[label=above:$y$] {}; \draw[->,very thick] (0,0) to [edge label=$v_1$] (90:1); \draw[->,very thick] (0,0) to [edge label=$v_2$] (210:1); \draw[->,very thick] (0,0) to [edge label'=$v_3$] (330:1); \fill (0,0) circle[radius=0.04]; \end{tikzpicture} \begin{tikzpicture}[>=latex,scale=1.9] \pgfsetzvec{\pgfpoint{-0.5cm}{-0.3cm}} \path (0,-1.0) rectangle (0,1.5); % ensure vertical alignment with the other tikzpictures \draw[->,gray] (-1,0,0) -- (1,0,0) node[label=right:$x$] {}; \draw[->,gray] (0,-1,0) -- (0,1,0) node[label=above:$y$] {}; \draw[->,gray] (0,0,-1) -- (0,0,1) node[label=above:$z$] {}; \draw[->,very thick] (0,0,0) to ($1/sqrt(3)*(1,1,1)$) node[label=$v_1$] {}; \draw[->,very thick] (0,0,0) to [edge label=$v_2$] ($1/sqrt(3)*(-1,1,-1)$); \draw[->,very thick] (0,0,0) to [edge label=$v_3$] ($1/sqrt(3)*(-1,-1,1)$); \draw[->,very thick] (0,0,0) to [edge label'=$v_4$] ($1/sqrt(3)*(1,-1,-1)$); \end{tikzpicture} \nopagebreak\\ \begin{tabular}{p{4.4cm}p{4.4cm}p{4.4cm}} {\begin{align*} \begin{pmatrix}1 & -1\end{pmatrix} \end{align*}} & {\begin{align*} \frac{1}{2}\cdot \begin{pmatrix} 0 & -\sqrt{3} & \sqrt{3} \\ 2 & -1 & -1 \\ \end{pmatrix} \end{align*}} & {\begin{align*} \frac{1}{\sqrt{3}}\cdot \begin{pmatrix} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ \end{pmatrix} \end{align*}} \end{tabular} \end{flushleft} Ein 2-Krähenfuß besteht einfach aus 2~Einheitsvektoren im 1-dimensionalen Raum, die in entgegen gesetzte Richtungen zeigen, das heißt, in einem Winkel von $\arccos\left(-1\right) = 180\degree$ zueinander stehen. Die Vektoren in Koordinatenschreibweise sind $v_1=\begin{pmatrix}1\end{pmatrix}$ und $v_2=\begin{pmatrix}-1\end{pmatrix}$. Ein 3-Krähenfuß besteht aus 3~Einheitsvektoren in der Ebene, die paarweise in einem Winkel von $\arccos\left(-\frac{1}{2}\right) = 120\degree$ zueinander stehen. Wählen wir ohne Beschränkung der Allgemeinheit die Einheitsvektoren mit den Winkeln $90\degree$, $210\degree$ und $330\degree$ bezüglich der $x$-Achse, so ergeben sich folgende Vektoren: \begin{align*} v_1 = \begin{pmatrix}\cos 90\degree \\ \sin 90\degree\end{pmatrix} &= \begin{pmatrix}0 \\ 1\end{pmatrix} & v_2 = \begin{pmatrix}\cos 210\degree \\ \sin 210\degree\end{pmatrix} &= \frac{1}{2}\cdot\begin{pmatrix}-\sqrt{3} \\ -1\end{pmatrix} & v_3 = \begin{pmatrix}\cos 330\degree \\ \sin 330\degree\end{pmatrix} &= \frac{1}{2}\cdot\begin{pmatrix}\sqrt{3} \\ -1\end{pmatrix} \end{align*} Der 4-Krähenfuß beschreibt die Form des realen Krähenfußes, der in der Geschichte viel als Defensivwaffe genutzt wurde und auch heute immer noch verwendet wird.~\endnote{% Krähenfuß, deutschsprachige Wikipedia, \url{https://de.wikipedia.org/wiki/Krähenfuß}} Er besteht aus 4~Einheitsvektoren im 3-dimensionalen Raum, die paarweise in einem Winkel von $\arccos\left(-\frac{1}{3}\right) \approx 109,5\degree$ zueinander stehen. Hierzu stellt man sich am besten ein regelmäßiges Tetraeder vor. Der Krähenfuß besteht dann genau aus den vier Vektoren vom Umkugel-Mittelpunkt\footnote{% Dieser ist zugleich Schwerpunkt, Inkugel-Mittelpunkt, und so weiter. Aber für unsere Betrachtungen ist nur wichtig, dass es der Umkugelmittelpunkt ist, das heißt, dass alle Ecken des Tetraeders gleich weit von diesem Punkt entfernt sind.} zu den vier Ecken. \section{Fragestellung} An den vorherigen Beispielen sehen wir, dass sich bestimmte 2- und 4-Krähenfüße durch recht einfache Matrizen beschreiben lassen: Es gibt zwar einen gewissen Vorfaktor,\footnote{% Dieser Vorfaktor stört uns nicht, weil er uns lediglich die Krähenfuß-Vektoren zu Einheitsvektoren normiert. Ein Krähenfuß ohne Vorfaktor sähe grafisch genauso aus, nur entsprechend vergrößert.} der meist irrational ist, aber die nachfolgenden Matrix-Einträge sind ganzzahlig, sie bestehen sogar nur aus den Einträgen $1$ und $-1$. Für 3-Krähenfüße hingegen erscheint es sehr schwer, eine solche Darstellung zu finden.\footnote{% Übungsaufgabe: Beweise, dass es keine ganzzahligen 3-Krähenfüße gibt.} Präzise ausgedrückt suchen wir nach folgendem: \begin{definition} Ein \emph{ganzzahliger $n$-Krähenfuß} ist ein $n$-Krähenfuß, dessen Matrix-Darstellung die folgende Form besitzt: \begin{align*} K_n & = \lambda \cdot (a_{ij}) & \text{mit } & \lambda \in \mathbb{R} \\ & & \text{und } & a_{ij} \in \mathbb{Z} \text{ für alle } i \in \{1,\ldots,n-1\} \text{, } j \in \{1,\ldots,n\} \end{align*} \end{definition} Die Frage lautet nun, wie wir für möglichst viele $n$ einen ganzzahligen $n$-Krähenfuß finden. Bevor wir uns jedoch auf die Suche begeben, machen wir einen Abstecher zu den Orthonormalbasen, die uns unsere Arbeit erleichtern werden und, soviel sei schon einmal verraten, uns eine Schatztruhe der mathematischen Forschung zugänglich machen. \section{Orthonormalbasen} Der gedankliche Sprung von Krähenfüßen zu Orthonormalbasen ist gar nicht so groß, denn ihre Definitionen sind sehr ähnlich. Zur Erinnerung: \begin{definition}[Orthonormalbasis] Eine $n$-dimensionale ONB ist eine Menge von $n$~Einheitsvektoren $b_1, b_2, \ldots, b_n$ die paarweise senkrecht aufeinander stehen, das heißt, deren paarweises Skalarprodukt~$0$ ist. Formal: \begin{align*} b_i & \in \mathbb{R}^n & \text{für alle } i \in \{1, \ldots, n\} \\ \ip{b_i}{b_i} & = 1 & \text{für alle } i \in \{1, \ldots, n\} \\ \ip{b_i}{b_j} & = 0 & \text{für alle } i,j \in \{1, \ldots, n\} \text{ mit } i \ne j \end{align*} \end{definition} Anschaulich ist eine ONB also ein Koordinatensystem, das beliebig verdreht im Raum liegt. Eine ONB erhält im Gegensatz zum Krähenfuß zusätzliche Freiheitsgrade, da die Vektoren eine Dimension mehr haben ($n$ statt $n-1$). Weiterhin ist der Wert des gemeinsamen Skalarproduktes $0$ statt ${-}\frac{1}{n-1}$. Wie üblich notieren wir $b_1, b_2, \ldots, b_n$ als Spaltenvektoren und fassen diese zu einer Matrix~$B$ zusammen:\footnote{% In dieser Notation ist obige Definition gleichbedeutend damit, dass $B$ eine orthogonale Matrix ist, das heißt: $B^T\!B = I$. Dabei bezeichnen wir wie üblich mit $I$ die $n$-dimensionale Einheitsmatrix.} \begin{align*} B = \begin{pmatrix} \vdots & & \vdots \\ b_1 & \cdots & b_n \\ \vdots & & \vdots \\ \end{pmatrix} \end{align*} Die folgenden Eigenschaften einer ONB werden für uns nützlich sein: \begin{lemma} Vertauschen wir zwei Spalten einer ONB, so bleibt das Ergebnis eine ONB. \end{lemma} \begin{proof} Dies folgt direkt aus der Tatsache, dass die Reihenfolge der Vektoren in der ONB-Definition keine Rolle spielt. \end{proof} \begin{lemma}[Vorzeichen-Lemma] Kehren wir in einer Spalte einer ONB sämtliche Vorzeichen um, so ist das Ergebnis weiterhin eine ONB. \end{lemma} \begin{proof} Anschaulich lassen wir lediglich einen der Einheitsvektoren in die entgegengesetzte Richtung zeigen. Damit ist es immer noch ein Einheitsvektor, der immer noch senkrecht auf allen anderen steht. Wir können dies auch formal zeigen: Wie betrachten die $k$-te Spalte und kehren dort alle Vorzeichen um. Das heißt, wir ersetzen den Einheitsvektor $b_k$ durch $b_k'$, wobei $b_k' = -b_k$. Dann gilt: \begin{align*} b_k' & = -b_k \in \mathbb{R}^n \\ \ip{b_k'}{b_k'} & = \ip{-b_k}{-b_k} = (-1)\cdot(-1)\cdot\ip{b_k}{b_k} = \ip{b_k}{b_k} = 1 \\ \ip{b_k'}{b_j} & = \ip{-b_k}{b_j} = -\ip{b_k}{b_j} = 0 \quad \text{für alle } j \in \{1, \ldots, n\} \text{ mit } j \ne k \end{align*} Also bleiben alle Eigenschaften der ONB-Definition erfüllt. \end{proof} \section{ONB mit konstanter Höhe und Krähenfüße} Im vorherigen Abschnitt haben wir uns kurz mit ONB beschäftigt und einige wichtige Eigenschaften kennengelernt. Doch was haben ONB denn nun wirklich mit Krähenfüßen zu tun, abgesehen von ihrer ähnlichen Definition? Bevor wir mathematisch präzise werden, versuchen wir eine anschauliche Beschreibung: Schauen wir uns den 3-Krähenfuß genauer an, erinnert uns dieses Bild stark an die Koordinaten-Achsen im 3-dimensionalen Raum. Das ist kein Zufall, denn der 3-Krähenfuß ist genau die isometrische Projektion\footnote{% Die isometrische Projektion dürfte den meisten sehr bekannt vorkommen, denn sie wird in vielen Strategie-Computerspielen verwendet.} eines ONB. Hierzu wird das ONB zunächst in die $xy$-Ebene projiziert, wobei wir voraussetzen, dass jeder Vektor der ONB die gleiche Höhe, also $z$-Koordinate, hat. So werden die Winkel zwischen den Vektoren gleichmäßig verzerrt, und die Bild-Vektoren stehen immer noch paarweise im gleichen Winkel zueinander, wenn auch nicht mehr im rechten Winkel. Hierbei werden die Vektoren gestaucht, jeweils um den gleichen Faktor. Um zum 3-Krähenfuß zu gelangen, müssen alle Vektoren nachträglich durch Multiplikation mit einem gemeinsamen Faktor auf Länge~$1$ gestreckt werden. \begin{flushleft} \begin{tikzpicture}[>=latex,scale=2] \draw[->,gray] (-1,0) -- (1,0) node[label=right:$x$] {}; \draw[->,gray] (0,-0.5) -- (0,1.2) node[label=above:$y$] {}; \draw[->,very thick] (0,0) to [edge label=$v_1$] (90:1); \draw[->,very thick] (0,0) to [edge label=$v_2$] (210:1); \draw[->,very thick] (0,0) to [edge label'=$v_3$] (330:1); \fill (0,0) circle[radius=0.04]; \end{tikzpicture} \hfill \begin{tikzpicture}[>=latex,scale=3] \pgfsetyvec{\pgfpoint{0.3cm}{0.5cm}} \pgfsetzvec{\pgfpoint{0cm}{1cm}} \draw[->,gray] (-1.0,0,0) -- (1.0,0,0) node[label=right:$x$] {}; \draw[->,gray] (0,-0.3,0) -- (0,1.5,0) node[label=above:$y$] {}; \draw[->,gray] (0,0,-0.2) -- (0,0,1.2) node[label=above:$z$] {}; \draw[->] (0,0,0) to (+0.000,+0.816,+0.577) node[label=above:$b_1$] {}; \draw[->] (0,0,0) to (-0.707,-0.408,+0.577) node[label=left:$b_2$] {}; \draw[->] (0,0,0) to (+0.707,-0.408,+0.577) node[label=right:$b_3$] {}; \draw[thick,dotted] (+0.000,+0.816,+0.577) to (+0.000,+0.816,0); \draw[thick,dotted] (-0.707,-0.408,+0.577) to (-0.707,-0.408,0); \draw[thick,dotted] (+0.707,-0.408,+0.577) to (+0.707,-0.408,0); \draw[->,very thick] (0,0,0) to (90:1) node[label=right:$v_1$] {}; \draw[->,very thick] (0,0,0) to (210:1) node[label=above:$v_2$] {}; \draw[->,very thick] (0,0,0) to (330:1) node[label=above:$v_3$] {}; \draw[->,very thick,gray] (0,0,0) to (+0.000,+0.816,0); \draw[->,very thick,gray] (0,0,0) to (-0.707,-0.408,0); \draw[->,very thick,gray] (0,0,0) to (+0.707,-0.408,0); \fill (0,0,0) circle[radius=0.25mm]; \end{tikzpicture} \end{flushleft} Kommen wir nun zu der präzisen Beschreibung. Diese wird uns zeigen, dass das Verfahren nicht nur anschaulich, sondern auch tatsächlich funktioniert, und zwar in beliebiger Dimension~$n$, nicht nur für $n=3$. Da dies nur mit bestimmten ONB funktioniert, führen wir für diese zuerst den Begriff \emph{ONB mit konstanter Höhe} ein. Deren eineindeutige Zuordnung zu den Krähenfüßen formulieren wir dann als Satz und beweisen diesen. \begin{definition} Eine $n$-dimensionale \emph{ONB mit konstanter Höhe} ist eine $n$-dimensionale ONB, deren Vektoren alle den Wert $\frac{1}{\sqrt{n}}$ als $n$-te Koordinate haben.\footnote{% Der Wert $\frac{1}{\sqrt{n}}$ ist nicht so willkürlich, wie es zunächst scheint. Übungsaufgabe: Ist in einem ONB der Wert aller $n$-ten Koordinaten gleich, so ist dieser gemeinsame Wert entweder $\frac{1}{\sqrt{n}}$ oder $-\frac{1}{\sqrt{n}}$.} In Matrix-Schreibweise: \begin{align*} B = \begin{pmatrix} * & \cdots & * \\ \vdots & \ddots & \vdots \\ * & \cdots & * \\ \tfrac{1}{\sqrt{n}} & \cdots & \tfrac{1}{\sqrt{n}} \\ \end{pmatrix} \end{align*} \end{definition} \begin{theorem} Jeder $n$-dimensionalen ONB mit konstanter Höhe entspricht genau ein $n$-Krähenfuß und umgekehrt. \begin{enumerate} \item Einer ONB mit konstanter Höhe wird derjenige Krähenfuß zugeordnet, der entsteht, indem jedem Vektor die $n$-Koordinate entfernt wird und das Ergebnis mit $\frac{\sqrt{n}}{\sqrt{n-1}}$ multipliziert wird. \item Einem Krähenfuß wird diejenige ONB mit konstanter Höhe zugeordnet, die entsteht, indem jeder Vektor mit $\frac{\sqrt{n-1}}{\sqrt{n}}$ multipliziert wird und anschließend der Wert $\frac{1}{\sqrt{n}}$ als $n$-te Koordinate hinzugefügt wird. \end{enumerate} \end{theorem} \begin{proof} Offenbar ist jede Zuordnung jeweils die Umkehrung der anderen. Es bleibt zu zeigen, dass das Ergebnis jeweils tatsächlich ein $n$-Krähenfuß bzw. eine $n$-dimensionale ONB ist. Sei $b_1,\ldots,b_n$ eine $n$-dimensionale ONB mit konstanter Höhe. Die Koordinaten von $b_i$ seien ($i=1,\ldots,n$): \begin{align*} b_i &= \begin{pmatrix} b_{1,i} \\ \vdots \\ b_{n-1,i} \\ \frac{1}{\sqrt{n}} \\ \end{pmatrix} \end{align*} Dann ist: \begin{align*} v_i &= \frac{\sqrt{n}}{\sqrt{n-1}} \begin{pmatrix} b_{1,i} \\ \vdots \\ b_{n-1,i} \\ \end{pmatrix} \end{align*} Daraus folgt für alle $i \in \{1,\ldots,n\}$: \begin{align*} \ip{v_i}{v_i} &= \frac{n}{n-1} \cdot \left( b_{1,i}^2 + \cdots + b_{n-1,i}^2 \right) \\ &= \frac{n}{n-1} \cdot \left( \ip{b_i}{b_i} - \left(\frac{1}{\sqrt{n}}\right)^2 \right) = \frac{n}{n-1} \cdot \left( 1 - \frac{1}{n} \right) = 1 \end{align*} Weiterhin folgt für alle $i,j \in \{1,\ldots,n\}$ mit $i \ne j$: \begin{align*} \ip{v_i}{v_j} &= \frac{n}{n-1} \cdot \left( b_{1,i}b_{1,j} + \cdots + b_{n-1,i}b_{n-1,j} \right) \\ &= \frac{n}{n-1} \cdot \left( \ip{b_i}{b_j} - \frac{1}{n} \right) = \frac{n}{n-1} \cdot \left( 0 - \frac{1}{n} \right) = - \frac{1}{n-1} \end{align*} Also ist $v_1,\ldots,v_n$ ein $n$-Krähenfuß, denn alle $v_i$ sind Einheitsvektoren, die paarweise das gleiche Skalarprodukt $\ip{v_i}{v_j} = {-}\frac{1}{n-1}$ haben. Sei nun umgekehrt $v_1,\ldots,v_n$ ein $n$-Krähenfuß mit: \begin{align*} v_i &= \begin{pmatrix} v_{1,i} \\ \vdots \\ v_{n-1,i} \\ \end{pmatrix} \end{align*} Dann ist: \begin{align*} b_i &= \begin{pmatrix} \frac{\sqrt{n-1}}{\sqrt{n}} v_{1,i} \\ \vdots \\ \frac{\sqrt{n-1}}{\sqrt{n}} v_{n-1,i} \\ \frac{1}{\sqrt{n}} \\ \end{pmatrix} = \frac{\sqrt{n-1}}{\sqrt{n}} \begin{pmatrix} v_{1,i} \\ \vdots \\ v_{n-1,i} \\ \frac{1}{\sqrt{n-1}} \\ \end{pmatrix} \end{align*} Analog zu den obigen Rechnungen erhalten wir $\ip{b_i}{b_i} = 1$ und $\ip{b_i}{b_j} = 0$ für alle $i \ne j$. Also ist $b_1,\ldots,b_n$ eine ONB. \end{proof} \begin{example}[Krähenfuß zu ONB] Wir wandeln unseren 3-Krähenfuß aus \cref{Krähenfüße} in eine 3-dimensionale ONB mit konstanter Höhe um: \begin{align*} K_3 & = \frac{1}{2}\cdot \begin{pmatrix} 0 & -\sqrt{3} & \sqrt{3} \\ 2 & -1 & -1 \\ \end{pmatrix} \\ B_3 & = \begin{pmatrix} \cdots & \frac{\sqrt{3-1}}{\sqrt{3}} \cdot K_3 & \cdots \\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \\ \end{pmatrix} = \frac{1}{2\sqrt{3}} \cdot \begin{pmatrix} 0 & -\sqrt{6} & \sqrt{6} \\ 2\sqrt{2} & -\sqrt{2} & -\sqrt{2} \\ 2 & 2 & 2 \\ \end{pmatrix} \end{align*} \end{example} \begin{example}[ONB zu Krähenfuß] Wir wandeln die folgende 4-dimensionale ONB mit konstanter Höhe in einen 4-Krähenfuß um: \begin{align*} B_4 & = \frac{1}{2} \cdot \begin{pmatrix} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix} \\ K_4 & = \frac{\sqrt{4}}{\sqrt{4-1}} \cdot \frac{1}{2} \cdot \begin{pmatrix} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ \deleted{1} & \deleted{1} & \deleted{1} & \deleted{1} \\ \end{pmatrix} = \frac{1}{\sqrt{3}} \cdot \begin{pmatrix} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ \end{pmatrix} \end{align*} \end{example} \begin{definition} Eine \emph{ganzzahlige $n$-dimensionale ONB} ist eine $n$-dimensionale ONB, deren Matrix-Darstellung die folgende Form besitzt: \begin{align*} B_n & = \lambda \cdot (a_{ij}) & \text{mit } & \lambda \in \mathbb{R} \\ & & \text{und } & a_{ij} \in \mathbb{Z} \text{ für alle } i,j \in \{1,\ldots,n\} \end{align*} \end{definition} Wenn wir also ganzzahlige Krähenfüße suchen, suchen wir in Wirklichkeit ganzzahlige ONB mit konstanter Höhe. In den folgenden beiden Abschnitten werden wir verschiedene Wege kennenlernen, genau solche ONB zu konstruieren. \section{Hadamard-Matrizen} Nachdem wir unsere Krähenfüße auf bestimmte ONB zurückführen konnten, ist es nun an der Zeit, diesen Zusammenhang auszuschlachten. Wir profitieren hierbei von der Tatsache, dass ONB im Gegensatz zu Krähenfüßen sehr gründlich erforscht wurden. Dabei interessieren uns besonders die Erkenntnisse über \emph{Hadamard-Matrizen}:~\endnote{% Hadamard-Matrix, deutschsprachige Wikipedia, \url{https://de.wikipedia.org/wiki/Hadamard-Matrix}}\endnote{% Hadamard matrix, englischsprachige Wikipedia, \url{https://en.wikipedia.org/wiki/Hadamard_matrix}} \begin{definition} Eine \emph{Hadamard-Matrix} ist eine Matrix, deren Spalten-Vektoren paarweise senkrecht aufeinander stehen deren Einträge ausschließlich $\pm 1$ sind. \end{definition} Na wunderbar! Diese Definition klingt ziemlich genau nach dem, was wir suchen. Da haben wir unsere Schatztruhe gefunden. Wir schlagen einfach nach, wie Hadamard-Matrizen für bestimmte Dimensionen $n$ konstruiert werden, wandeln diese nach unserem Rezept direkt in Krähenfüße um, und sind fertig. Halt. Nicht so schnell. Bevor wir diesen Weg gehen können, müssen wir zwei Probleme aus dem Weg räumen: \begin{enumerate} \item Eine Hadamard-Matrix ist fast eine ONB, aber nicht ganz. Zwar stehen alle Vektoren paarweise senkrecht aufeinander, aber sie sind nicht auf Länge~1 normiert. \item Wir benötigen eine ONB mit konstanter Höhe. \end{enumerate} Zum Glück lassen sich beide Probleme recht einfach lösen. Das erste Problem lösen wir mit einem entsprechenden Vorfaktor, geben dem Ergebnis einen passenden Namen und zeigen, dass dabei tatsächlich eine ONB herausgekommen ist. \begin{definition} Eine $n$-dimensionale \emph{Hadamard-ONB} ist eine $n$-dimensionale Hadamard-Matrix, die mit dem Vorfaktor~$\frac{1}{\sqrt{n}}$ multipliziert wurde. \end{definition} \begin{lemma} Jede Hadamard-ONB ist tatsächlich eine ONB. \end{lemma} \begin{proof} Seien $h_1, \ldots, h_n$ die Spaltenvektoren einer beliebigen $n$-dimensionalen Hadamard-Matrix. Dann gilt: \begin{align*} |h_i| & = \sqrt{(\pm 1)^2+\cdots+(\pm 1)^2} = \sqrt{1+\cdots+1} = \sqrt{n} \end{align*} Das heißt, alle Spaltenvektoren haben die gleiche Länge $\sqrt{n}$. Die Skalierung mit dem Vorfaktor~$\frac{1}{\sqrt{n}}$ führt somit zu Einheitsvektoren. \end{proof} Das zweite Problem lösen wir mit Hilfe unseres Vorzeichen-Lemmas. \begin{lemma} Jede Hadamard-ONB lässt sich durch geeignete Vorzeichenwechsel der Matrix-Einträge in eine Hadamard-ONB mit konstanter Höhe umformen. \end{lemma} \begin{proof} Die unterste Zeile einer Hadamard-ONB besteht nach Konstruktion ausschließlich aus den Einträgen~$\frac{1}{\sqrt{n}}$ und~${-}\frac{1}{\sqrt{n}}$. Um eine konstante Höhe zu erreichen, müssen alle negativen Einträge~${-}\frac{1}{\sqrt{n}}$ in positive Einträge~$\frac{1}{\sqrt{n}}$ umgewandelt werden. Hierzu kehren wir für alle Spalten, deren $n$-te Koordinate~${-}\frac{1}{\sqrt{n}}$ ist, das Vorzeichen um. \end{proof} Nachdem wir diese beiden Probleme aus der Welt geschafft haben, können wir uns endlich der Konstruktion von Hadamard-Matrizen zuwenden. Da dieses Thema locker einen eigenen Artikel füllen kann, werden wir uns auf die wichtigsten Erkenntnisse beschränken und deren Beweise außen vor lassen. Hadamard-Matrizen sind nach dem Mathematiker Jacques Hadamard benannt und existieren grundsätzlich nur für die Dimensionen $n=1$, $n=2$ und durch 4 teilbare Dimensionen $n=4k$ mit $k \in \mathbb{Z}_{>0}$. In allen anderen Fällen ist die Konstruktion beweisbar unmöglich. Allerdings wurde noch nicht für alle Dimensionen $n=4k$ eine solche Konstruktion gefunden, daher ist es bisher nur eine Vermutung, die sogenannte Hadamard-Vermutung, dass für jede Dimension $n=4k$ tatsächlich eine Hadamard-Matrix existiert. Die wichtigsten Konstruktionswerkzeuge, mit denen wir eine Vielzahl von Dimensionen abdecken können, sind:\footnote{% Diese Konstruktionen weichen etwas von denen in der Literatur ab. Sie sind derart geändert, dass stets Hadamard-Matrizen mit letzter Zeile $(1 \cdots 1)$ entstehen. So erhalten wir direkt Hadamard-ONB mit konstanter Höhe und ersparen uns die nachträgliche Vorzeichen-Umkehrung einiger Spalten.} \begin{theorem} Für $n=1$ existiert eine Hadamard-Matrix: \begin{align*} H_1 & = \begin{pmatrix} 1 \\ \end{pmatrix} \end{align*} \end{theorem} \begin{theorem} Für $n=2$ existiert eine Hadamard-Matrix: \begin{align*} H_2 & = \begin{pmatrix} 1 & -1 \\ 1 & 1 \\ \end{pmatrix} \end{align*} \end{theorem} \begin{theorem}[Erste Paley-Konstruktion] Ist $p$ eine Primzahl\footnote{% Diese Konstruktion funktioniert auch mit Primzahlpotenzen, indem wir das Legendre-Symbol und die Jacobsthal-Matrix von Primkörpern auf beliebige endliche Körper verallgemeinern.} mit $p \equiv 3 \pmod 4$, so können wir für $n = p+1$ folgende Hadamard-Matrix konstruieren: \begin{align*} H_{p+1} & = \begin{pmatrix} 1 & & & \\ \vdots & & Q_p - I_p & \\ 1 & & & \\ 1 & 1 & \cdots & 1 \\ \end{pmatrix} \end{align*} Dabei bezeichnet $I_p$ die $p \times p$ Einheitsmatrix und $Q_p$ die $p \times p$ Jacobsthal-Matrix.\footnote{% Diese ist definiert als $Q_p = (q_{ij})$ mit $q_{ij} = \smalllegendre{j-i}{p}$, wobei $\smalllegendre{a}{p}$ das Legendre-Symbol bezeichnet.} \end{theorem} \begin{theorem}[Sylvester-Konstruktion] Aus jeder $n$-dimensionalen Hadamard-Matrix $H_n$ können wir eine $2n$-dimensionale Hadamard-Matrix $H_{2n}$ wie folgt konstruieren:\footnote{% Übungsaufgabe: Zeige, dass die so konstruierte Matrix $H_{2n}$ tatsächlich eine Hadamard-Matrix ist.} \begin{align*} H_{2n} & = \begin{pmatrix} H_n & -H_n \\ H_n & H_n \\ \end{pmatrix} \end{align*} \end{theorem} Nun ist es soweit! Wir haben endlich alle Werkzeuge beisammen, um unsere Krähenfüße zu konstruieren. \begin{example}[Ganzzahliger 8-Krähenfuß] Wir starten mit der $2$-dimensionalen Hadamard-Matrix und wenden die Sylvester-Konstruktion zweimal an: \begin{align*} H_4 & = \begin{pmatrix} H_2 & -H_2 \\ H_2 & H_2 \\ \end{pmatrix} = \begin{pmatrix} 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix} \\ H_8 & = \begin{pmatrix} H_4 & -H_4 \\ H_4 & H_4 \\ \end{pmatrix} = \begin{pmatrix} 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \end{align*} Nun normieren wir die Hadamard-Matrix zu einer Hadamard-ONB: \begin{align*} B_8 & = \frac{1}{\sqrt{8}} \cdot H_8 \end{align*} Diese Hadamard-ONB hat bereits konstante Höhe, wir brauchen also keine Vorzeichen umzukehren. Schließlich wandeln wir die ONB in einen 8-Krähenfuß um: \begin{align*} K_8 & = \frac{1}{\sqrt{7}} \cdot \begin{pmatrix} 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ \end{pmatrix} \end{align*} \end{example} \begin{example}[Ganzzahliger 12-Krähenfuß] Wir bemerken, dass $12 = 11+1$ und dass $11$~eine Primzahl mit~$11 \equiv 3 \pmod{4}$ ist. Wir starten mit der $11 \times 11$ Jacobsthal-Matrix:\footnote{ Die quadratischen Reste modulo 11 sind 1, 3, 4, 5 und 9. Die Legendre-Symbole $\smalllegendre{0}{11},\smalllegendre{1}{11},\ldots,\smalllegendre{10}{11}$ sind entsprechend $0,1,{-}1,1,1,1,{-}1,{-}1,{-}1,1,{-}1$. Dies ist zugleich die erste Zeile der Jacobsthal-Matrix. Die übrigen Zeilen erhalten wir durch zyklische Vertauschung.} \begin{align*} Q_{11} & = \begin{pmatrix} 0 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 \\ -1 & 0 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 \\ 1 & -1 & 0 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 \\ -1 & 1 & -1 & 0 & 1 & -1 & 1 & 1 & 1 & -1 & -1 \\ -1 & -1 & 1 & -1 & 0 & 1 & -1 & 1 & 1 & 1 & -1 \\ -1 & -1 & -1 & 1 & -1 & 0 & 1 & -1 & 1 & 1 & 1 \\ 1 & -1 & -1 & -1 & 1 & -1 & 0 & 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & -1 & -1 & 1 & -1 & 0 & 1 & -1 & 1 \\ 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 0 & 1 & -1 \\ -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 0 & 1 \\ 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & 0 \\ \end{pmatrix} \end{align*} Wir subtrahieren die Einheitsmatrix $I_{11}$ (also ersetzen in der Diagonale die Werte~$0$ jeweils durch~${-}1$) und wenden die erste Paley-Konstruktion an: \begin{align*} H_{12} & = \begin{pmatrix} 1 & & & \\ \vdots & & Q_{11} - I_{11} & \\ 1 & & & \\ 1 & 1 & \cdots & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 \\ 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 \\ 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 \\ 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \end{align*} Wir normieren zu einer Hadamard-ONB, die bereits konstante Höhe hat, und erzeugen aus dieser unseren Krähenfuß: \begin{align*} K_{12} & = \frac{1}{\sqrt{11}} \cdot \begin{pmatrix} 1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 & -1 \\ 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 \\ 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 & -1 \\ 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & -1 & -1 \\ \end{pmatrix} \end{align*} \end{example} \section{Alternativer Ansatz} Eine neuartige Methode\footnote{% Der Autor hat diesen Ansatz zur Erzeugung ganzzahliger ONB selbst entdeckt und konnte ihn in der Literatur bislang nicht wiederfinden. Er freut sich über Hinweise aus der Leserschaft, falls dieser Ansatz doch nicht so neu sein sollte wie vermutet.} ist die Konstruktion geeigneter ONB durch folgenden Ansatz: \begin{align*} A_n & = \lambda \cdot \begin{pmatrix} e & g & g & g & \cdots & g & f \\ e & g & g & g & & f & g \\ \vdots & \vdots & \vdots & & \reflectbox{$\ddots$} & & \vdots \\ e & g & g & f & & g & g \\ e & g & f & g & \cdots & g & g \\ e & f & g & g & \cdots & g & g \\ e & e & e & e & \cdots & e & e \\ \end{pmatrix} & \text{mit } \lambda \in \mathbb{R} \text{ und } e,f,g \in \mathbb{Z} \end{align*} Das heißt: Die Einträge der ersten Spalte und letzten Zeile sind $e$. Die Einträge der gespiegelten Diagonale (mit Ausnahme der linken unteren Ecke) sind $f$. Die übrigen Einträge sind $g$.\footnote{% Für $g=0$ werden solche Matrizen \emph{Arrowhead-Matrizen} genannt, da die Form der übrigen Matrix-Einträge an eine Pfeilspitze (englisch: Arrowhead) erinnert. In der gängigen Literatur zeigt die Pfeilspitze nach links oben. Für unsere Zwecke ist es jedoch nützlich, von dieser Konvention abzuweichen und die Pfeilspitze nach links unten zeigen zu lassen. Doch auch für $g \ne 0$ sind diese Matrizen offenbar nützlich. Der in einigen Kreisen recht bekannte Mathematiker Adam~P.~Goucher (Entdeckungen in \emph{Conway's Game of Life}, Engagement in der britischen Mathematik-Olympiade) bemerkte hierzu für die gespiegelte (Pfeilspitze nach links oben) Variante dieser Matrizen: "`I've found these useful as well! Premultiplying by one of these matrices converts a vector of zero mean to a vector with empty initial coordinates -- which is useful for dealing with centred data in Procrustes analysis."'~\endnote{% What is the term for this type of matrix?, MathOverflow, \url{https://mathoverflow.net/q/262091}}} Strategisch gesehen haben diese Matrizen für uns folgende Vorteile: \begin{enumerate} \item Sie haben nur sehr wenige Freiheitsgrade. \item Trotzdem kann man ihnen durch zusätzliche Einschränkungen die Struktur einer ONB "`aufzwingen"'. \item Die letzte Zeile ist bereits per Definition konstant. \end{enumerate} Der strategische Nachteil ist jedoch: \begin{itemize} \item Nicht für alle Dimensionen $n$ gibt es ganzzahlige Lösungen. \end{itemize} Doch der Reihe nach. Zunächst ignorieren wir die Ganzzahligkeit und betrachten $\lambda e$, $\lambda f$ und $\lambda g$ jeweils als reelle Unbekannte. Die Spaltenvektoren von $A_n$ bezeichnen wir wie üblich mit $b_1,\ldots,b_n$. Nun ist $A_n$ genau dann eine ONB, wenn $\ip{b_i}{b_i} = 1$ und $\ip{b_i}{b_j} = 0$ für alle $i \ne j$. Das sind insgesamt $n^2$ Gleichungen. Gruppieren wir sie jedoch, fällt uns folgendes auf: \begin{align} 1 & = \ip{b_1}{b_1} = n \cdot (\lambda e)^2 \\ 1 & = \ip{b_i}{b_i} = (n-2) \cdot (\lambda g)^2 + (\lambda f)^2 + (\lambda e)^2 & & \text{für alle } i \in \{2,\ldots,n\} \\ 0 & = \ip{b_1}{b_j} = (n-2) \cdot (\lambda e)(\lambda g) + (\lambda e)(\lambda f) + (\lambda e)^2 & & \text{für alle } j \in \{2,\ldots,n\} \\ 0 & = \ip{b_i}{b_j} = (n-3) \cdot (\lambda g)^2 + 2 \cdot (\lambda g)(\lambda f) + (\lambda e)^2 & & \text{für alle } i,j \in \{2,\ldots,n\} \end{align} Es sind in Wirklichkeit also nur vier Gleichungen! Da wir eine ONB mit konstanter Höhe benötigen, kommt noch eine fünfte Gleichung hinzu: \begin{align} \lambda e & = \frac{1}{\sqrt{n}} \end{align} Wir haben also ein quadratisches Gleichungssystem mit 5 Gleichungen und 3 Unbekannten. Falls wir Pech haben, liefert das Gleichungssystem für einige~$n$, oder sogar alle~$n$, keine Lösung. Aber wir haben Glück:\footnote{% Es handelt sich natürlich nicht um Glück, sondern um einen klassischen \emph{Survivorship~Bias}: Der Autor experimentierte mit verschiedenen Ansätzen und präsentiert hier aus Platzgründen lediglich den Ansatz, der zu einem guten Ergebnis führte.} Es gibt für jedes~$n$ eine oder mehrere Lösungen, und zwar mindestens die folgende: \begin{align*} \lambda e & = \frac{1}{\sqrt{n}} & \lambda f & = 1-\frac{1}{n-\sqrt{n}} & \lambda g & = -\frac{1}{n-\sqrt{n}} \end{align*} Nun wollen wir den gemeinsamen reellen Faktor $\lambda$ so wählen, dass $e$, $f$ und $g$ ganzzahlig werden. Dies ist leider nicht für alle $n$ möglich. Daher gehen wir den umgekehrten Weg: Wir nutzen $\lambda$, um die Nenner zu eliminieren und schauen, für welche $n$ die resultierenden $e$, $f$ und $g$ ganzzahlig werden: \begin{align*} \lambda & = \frac{1}{n-\sqrt{n}} & e & = \sqrt{n}-1 & f & = n-\sqrt{n}-1 & g & = -1 \end{align*} Offenbar liefert dieser Ansatz für alle quadratischen Dimensionen $n=k^2$ mit $k \in \mathbb{Z}_{>0}$ eine ganzzahlige Lösung. Hilft uns das weiter? Was haben wir dadurch gewonnen? Nun, für gerade $k$ haben wir erst einmal nichts gewonnen, wir könnten stattdessen genauso gut Hadamard-Matrizen verwenden. Aber für ungerade $k = 2\ell+1$ erhalten wir Konstruktion von ganzzahligen ONB ungerader Dimension $n=(2\ell+1)^2$ mit $\ell \in \mathbb{Z}_{>0}$, etwa $n=9$ oder $n=25$, für die es prinzipiell keine Hadamard-Matrizen gibt! Bei der Umwandlung zu einem Krähenfuß ergibt sich als neuer Vorfaktor: \begin{align*} \lambda' & = \lambda \cdot \frac{\sqrt{n}}{\sqrt{n-1}} = \frac{1}{n-\sqrt{n}} \cdot \frac{\sqrt{n}}{\sqrt{n-1}} = \frac{1}{(\sqrt{n}-1)\sqrt{n-1}} \end{align*} Außerdem funktioniert auch hier die Silvester-Konstruktion, sodass wir die Dimensionen $n=2\cdot(2\ell+1)^2$ erreichen, etwa $n=18$ oder $n=50$, für die es ebenfalls keine Hadamard-Matrizen gibt, da sie nicht durch 4 teilbar ist. Einen Fallstrick gibt es jedoch: Da wir direkt mit den ONB arbeiten, müssen wir nachträglich mit dem Faktor~$\frac{1}{\sqrt{2}}$ normalisieren: \begin{align*} A_{2n} & = \frac{1}{\sqrt{2}} \cdot \begin{pmatrix} A_n & -A_n \\ A_n & A_n \\ \end{pmatrix} \end{align*} \begin{example}[Ganzzahliger 9-Krähenfuß] Zuerst errechnen wir die Matrix-Einträge: \begin{align*} \lambda & = \frac{1}{9-\sqrt{9}} = \frac{1}{6} & e & = \sqrt{9}-1 = 2 & f & = 9-\sqrt{9}-1 = 5 & g & = -1 \end{align*} Unsere ONB mit konstanter Höhe lautet entsprechend: \begin{align*} A_9 & = \frac{1}{6} \cdot \begin{pmatrix} 2 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 5 \\ 2 & -1 & -1 & -1 & -1 & -1 & -1 & 5 & -1 \\ 2 & -1 & -1 & -1 & -1 & -1 & 5 & -1 & -1 \\ 2 & -1 & -1 & -1 & -1 & 5 & -1 & -1 & -1 \\ 2 & -1 & -1 & -1 & 5 & -1 & -1 & -1 & -1 \\ 2 & -1 & -1 & 5 & -1 & -1 & -1 & -1 & -1 \\ 2 & -1 & 5 & -1 & -1 & -1 & -1 & -1 & -1 \\ 2 & 5 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ \end{pmatrix} \end{align*} Dies liefert uns den folgenden ganzzahligen 9-Krähenfuß: \begin{align*} K_9 & = \frac{1}{2\sqrt{8}} \cdot \begin{pmatrix} 2 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 5 \\ 2 & -1 & -1 & -1 & -1 & -1 & -1 & 5 & -1 \\ 2 & -1 & -1 & -1 & -1 & -1 & 5 & -1 & -1 \\ 2 & -1 & -1 & -1 & -1 & 5 & -1 & -1 & -1 \\ 2 & -1 & -1 & -1 & 5 & -1 & -1 & -1 & -1 \\ 2 & -1 & -1 & 5 & -1 & -1 & -1 & -1 & -1 \\ 2 & -1 & 5 & -1 & -1 & -1 & -1 & -1 & -1 \\ 2 & 5 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ \end{pmatrix} \end{align*} \end{example} \section{Zusammenfassung und Ausblick} Wir haben für sehr viele Dimensionen~$n$ ganzzahlige Krähenfüße konstruiert. Dabei haben wir gesehen, dass dies äquivalent dazu ist, ganzzahlige Orthonormalbasen mit konstanter Höhe zu finden. Via Hadamard-Matrizen können wir die Dimensionen 1 und 2, sowie sehr viele durch 4 teilbare Dimensionen abdecken. Falls sich die Hadamard-Vermutung bewahrheiten sollte, können wir sogar alle durch 4 teilbare Dimensionen mit diesem Ansatz erreichen. Über einen alternativen Ansatz konnten wir zudem Dimensionen erreichen, die nicht durch 4 teilbar sind. Allerdings funktioniert dieser Ansatz nur, wenn die Dimension eine Quadratzahl oder das Doppelte einer solchen ist. Für alle übrigen Dimensionen ist die Frage nach ganzzahligen Krähenfüßen noch offen: 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, und so weiter. An dieser Stelle sei dazu aufgerufen, mit Modifikationen des alternativen Ansatzes zu experimentieren, sodass wir einige dieser Lücken schließen können. Wer eine größere Herausforderung sucht, möge sich an einer Hadamard-Matrix der Dimension 668 versuchen. Wem das immer noch zu banal ist, sollte sich direkt der Hadamard-Vermutung zuwenden. Alle Erkenntnisse zu ganzzahligen Krähenfüßen werden auf der Webseite dieses Artikels gesammelt: \begin{center} \url{https://njh.eu/kraehenfuesse} \end{center} \theendnotes \addcontentsline{toc}{section}{Referenzen} \section*{Lizenz} \addcontentsline{toc}{section}{Lizenz} Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung~-- Weitergabe unter gleichen Bedingungen 4.0 International Lizenz. (CC BY-SA 4.0) \\ \url{https://creativecommons.org/licenses/by-sa/4.0/} \end{document}