TITLE: do the null space vectors need to be an orthogonal complement to the rowspace vector, isn't it enough to be linearly independent?
QUESTION [1 upvotes]: say for example I have two 3 dimensional vectors that are linearly independent then I would be be able to form a 2 dimensional subspace which is a plane in the 3 dimension. the null space in my understanding is the missing vectors that are needed to represent the whole 3 dimension and conventionally is it formed by finding the orthogonal complement for both vectors in my subspace which is for sure linearly independent.
my question is, do the nullspace vectors need to be orthogonal, I am under the assumption that any vector that is linearly independent is good enough to represnt the whole dimension ? if that is not the case, why is it conventional for them to be orthogonal is it for simplicity?

REPLY [1 votes]: Your observations can be formalized as follows:
Let $A$ be a $m \times n$ matrix over a field $K$ (e.g. $K = \mathbb{R}$ for geometric intuition). For every $1 \leq i \leq m$ let $A_i = (A_{i1}, \dotsc, A_{in})^T \in K^n$ be the transposed of the $i$-th row of $A$ and let
$$
 R = \mathrm{span}_K\{A_1, \dotsc, A_m\} \subseteq K^n.
$$
For $x,y \in K^n$ let $x \cdot y = \sum_{i=1}^n x_i y_i$ and call $x$ and $y$ orthogonal if $x \cdot y = 0$. For any subspace $U \subseteq K^n$ let
$$
 U^\perp = \{x \in K^n \mid \text{$x \cdot y = 0$ for every $y \in U$}\}
$$
be the orthogonal complement of $U$.
Then $(A \cdot x)_i= \sum_{j=1}^n A_{ij} x_j$ for all $x \in K^n$ and $1 \leq i \leq m$. Therefore $x \in \ker A$ if and only if $\sum_{j=1}^n A_{ij} x_j = 0$ for every $1 \leq i \leq m$. Notice that $\sum_{j=1}^n A_{ij} x_j = A_i \cdot x$. Thus $x \in \ker A$ if and only if $A_i \cdot x = 0$ for every $1 \leq i \leq m$, i.e. if $x$ is orthogonal to each row of $A$. It then follows that $x$ is already orthogonal to every $y \in R$ because
$$
 \left( \sum_{i=1}^m \lambda_i A_i \right) \cdot x
 = \sum_{i=1}^m \lambda \underbrace{A_i \cdot x}_{=0}
 = 0.
$$
So we have $\ker A = R^\perp$. In this way is makes sense to say that the nullspace $\ker A$ is precisely the orthogonal complement $R^\perp$ of the subspace $R$ spanned by the rows of $A$.
(These who know the dual space will recognize this as a special case of the equality $\mathrm{im}(f^*) = \ker(f)^\perp$ where $f \colon V \to W$ is some linear map and $f^* \colon W^* \to V^*$ is the induced linear map.)


TITLE: Finding parametric eqution for the tangent line
QUESTION [1 upvotes]: Let $C$ be the curve through $P\left(-2,1,5\right)$
  intersecting the surfaces $\Sigma_1:z=x^2+y^2$ and
  $\Sigma_2:z=13-(x^2+4y^2)$. Find the tangent line of $C$ at $P$.

My teacher used the total derivative of each surface to find the orthogonal vector. The technique is simple, I just don't fully understand why she did so. Can anyone please provide a geometric explanation? Thanks!

REPLY [2 votes]: The total derivative of a function
$f:\mathbb{R}^3\rightarrow\mathbb{R}$
at a point $P=\mathbf{x}_0$ is a linear function
$df:\mathbb{R}^3\rightarrow\mathbb{R}$,
$$
df
=\frac{\partial f}{\partial x}dx
+\frac{\partial f}{\partial y}dy
+\frac{\partial f}{\partial z}dz,
$$
i.e. so that $df(\Delta x,\Delta y,\Delta z)
=\frac{\partial f}{\partial x}\Delta x
+\frac{\partial f}{\partial y}\Delta y
+\frac{\partial f}{\partial z}\Delta z$.
It gives you the linear approximation
$$
f(\mathbf{x}) \approx f(\mathbf{x}_0)
+\frac{\partial f(\mathbf{x}_0)}{\partial x}\Delta x
+\frac{\partial f(\mathbf{x}_0)}{\partial y}\Delta y
+\frac{\partial f(\mathbf{x}_0)}{\partial z}\Delta z
$$
where
$(x,y,z)=\mathbf{x}=\mathbf{x}_0+\Delta\mathbf{x}$
and
$\Delta\mathbf{x}=(x-x_0,y-y_0,z-z_0)$,
and its level sets are planes in $\mathbb{R}^3$
perpendicular to the gradient $\nabla{f}(\mathbf{x}_0)$.
In our case, if we take the cross product of the gradients
at a point of common intersection $\mathbf{x}_0$,
we will also find the tangent to the curve (not line!) $C$,
since this gives us something normal to both gradients and
therefore tangent to $\Sigma_1$ and $\Sigma_2$.
Now $\Sigma_1$ is a paraboloid with global minimum at the origin
and axis of symmetry/revolution along the $z$ axis, and $\Sigma_2$
is similar but inverted, with parabolic vertical cross sections
and elliptic horizontal cross sections and global maximum at $(0,0,13)$. To calculate these gradients, we need to write the equations for these curves as functions:
$$f_1=x^2+ y^2-z\quad\implies\quad\nabla{f_1}=(2x,2y,-1)$$
$$f_2=x^2+4y^2+z\quad\implies\quad\nabla{f_2}=(2x,8y,+1)$$
(the curves will then be the level sets for the values $f_1=0$
and $f_2=13$). This would give us a tangent vector parallel to
$$\nabla{f_1}\times\nabla{f_2}=(10y,-4x,12xy)$$
and hence, at $P(-2,1,5)$, a parametric tangent line
(with parameter $s$ being distance from $P$) of
$$\mathbf{x}(s)=(-2,1,5)\pm\frac{s}{\sqrt{185}}(5,-4,12).$$
Note also that curve $C$ is the locus of points $(x,y,z)$ satisfying
$x^2+y^2=z=13-(x^2+4y^2)$ $\implies$
$2x^2+5y^2=13$ $\implies$
$$
\left(\frac{x}{\sqrt{13/2}}\right)^2+
\left(\frac{y}{\sqrt{13/5}}\right)^2=
13
$$
which could therefore be parametrized by
$$
\mathbf{x}(t)=
\left(
\sqrt{\frac{13}2}\cos{t},
\sqrt{\frac{13}5}\sin{t},
\frac{13}{10}
\left(5\cos^2t+3\sin^2t\right)
\right),
$$
giving yet another way to compute the tangent!


TITLE: Meaning of "Gradient with respect to coordinates of particle" in SPH
QUESTION [0 upvotes]: I'm currently trying to implement a simple SPH simulation based on a variety of papers. However as I'm not a trained physicist nor mathematician I have a small issue with the following notation and formulation repeated in a number of different papers and internet sites:

and $\nabla_a$ denotes the gradient taken with respect to the coordinates
  of particle $a$.

As far as I can tell this is the first paper using this description.
So what is meant by this notation? Is it simply a vector with a partial derivative for each dimension? Or is it something like a directional derivative?

REPLY [3 votes]: The explict notation is the folowing.
you have i,j particle indexes, and you have the following definitions:
$\vec r_{ij} = \vec r_j - \vec r_i $ , where $\vec r_i$ is the position of the $i$-th particle.
$W(\vec r_{ij},h_i)$ is the smoothing-kernel evaluated between the 2 SPH particles, using the smoothing parameter of the j-th particle.
The notation he uses is the following:
$\nabla_i W_{ij}(h_i) = \frac{\partial W(\vec r_i - \vec r_j,h_i)}{\partial \vec r_i}$
In (most) hidrodynamic aplications of SPH, the usual convention is that for all i, $h_i=h$ is fixed, and $W(\vec r_{ij},h) = w(\frac{|\vec r_i-\vec r_j|}{h})$, and so, you can think that you have an $W(\vec r)$ and you have $\nabla W = \nabla w(r) = w'(r)\hat r$, ando so, in this case, we write:
$\nabla_i W_{ij}(h_i) = w'(r_{ij},h)\frac{\vec r_i - \vec r_j}{|\vec r_i - \vec r_j|}$
and so, you have an explicit formula for this gradient with respect to the i-th particle
It's possible to formulate an SPH formula with $h_i$ depending on the particle, and on the near particles (through the, implicit, dependence on $\rho_i$), and when you do that, you need to introduce 'correcting schemes', which involve calculating things like $\Omega_i = 1-\frac{\partial h_i}{\partial \rho_i}\sum_k m_k\frac{\partial W}{\partial h_i}(r_{ij},h_i)$
I personally don't like this kind of 'correction scheme' which involves changing the smoothing parameter(or using constant, but different parameters for each particle), but, it's a legit try, and in many occasions it works. Still, it makes difficult to enforce symmetries and conservations laws on the system based only on the equations of movement.


text:
\section{Subgroup is Superset of Conjugate iff Normal}
Tags: Conjugacy, Normal Subgroups

\begin{theorem}
Let $\struct {G, \circ}$ be a [[Definition:Group|group]].
Let $N$ be a [[Definition:Subgroup|subgroup]] of $G$.
Then $N$ is [[Definition:Normal Subgroup/Definition 1|normal in $G$ (by definition 1)]] {{iff}}:
: $\forall g \in G: g \circ N \circ g^{-1} \subseteq N$
: $\forall g \in G: g^{-1} \circ N \circ g \subseteq N$
\end{theorem}

\begin{proof}
By definition, a [[Definition:Subgroup|subgroup]] is [[Definition:Normal Subgroup/Definition 1|normal in $G$]] {{iff}}:
:$\forall g \in G: g \circ N = N \circ g$
First note that:
:$(1): \quad \paren {\forall g \in G: g \circ N \circ g^{-1} \subseteq N} \iff \paren {\forall g \in G: g^{-1} \circ N \circ g \subseteq N}$
which is shown by, for example, setting $h := g^{-1}$ and substituting.
=== Necessary Condition ===
Suppose that $N$ is [[Definition:Normal Subgroup|normal in $G$]].
Then:
{{begin-eqn}}
{{eqn | lo= \forall g \in G:
      | l = g \circ N
      | r = N \circ g
      | c = {{Defof|Normal Subgroup}}
}}
{{eqn | ll= \leadsto
      | l = g \circ N
      | o = \subseteq
      | r = N \circ g
      | c = {{Defof|Set Equality}}
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ N} \circ g^{-1}
      | o = \subseteq
      | r = \paren {N \circ g} \circ g^{-1}
      | c = {{Defof|Subset Product}}
}}
{{eqn | ll= \leadsto
      | l = g \circ N \circ g^{-1}
      | o = \subseteq
      | r = N \circ \paren {g \circ g^{-1} }
      | c = [[Subset Product within Semigroup is Associative/Corollary|Subset Product within Semigroup is Associative: Corollary]]
}}
{{eqn | ll= \leadsto
      | l = g \circ N \circ g^{-1}
      | o = \subseteq
      | r = N \circ e
      | c = {{Defof|Inverse Element}}
}}
{{eqn | ll= \leadsto
      | l = g \circ N \circ g^{-1}
      | o = \subseteq
      | r = N
      | c = [[Coset by Identity]]
}}
{{end-eqn}}
Similarly:
{{begin-eqn}}
{{eqn | lo= \forall g \in G:
      | l = N \circ g
      | r = g \circ N
      | c = {{Defof|Normal Subgroup}}
}}
{{eqn | ll= \leadsto
      | l = N \circ g
      | o = \subseteq
      | r = g \circ N
      | c = {{Defof|Set Equality}}
}}
{{eqn | ll= \leadsto
      | l = g^{-1} \circ \paren {N \circ g}
      | o = \subseteq
      | r = g^{-1} \circ \paren {g \circ N}
      | c = {{Defof|Subset Product}}
}}
{{eqn | ll= \leadsto
      | l = g^{-1} \circ N \circ g
      | o = \subseteq
      | r = \paren {g^{-1} \circ g} \circ N
      | c = [[Subset Product within Semigroup is Associative/Corollary|Subset Product within Semigroup is Associative: Corollary]]
}}
{{eqn | ll= \leadsto
      | l = g^{-1} \circ N \circ g
      | o = \subseteq
      | r = e \circ N
      | c = {{Defof|Inverse Element}}
}}
{{eqn | ll= \leadsto
      | l = g^{-1} \circ N \circ g
      | o = \subseteq
      | r = N
      | c = [[Coset by Identity]]
}}
{{end-eqn}}
{{qed|lemma}}
=== Sufficient Condition ===
Let $N$ be a [[Definition:Subgroup|subgroup of $G$]] such that:
: $\forall g \in G: g \circ N \circ g^{-1} \subseteq N$
and so from $(1)$ above:
: $\forall g \in G: g^{-1} \circ N \circ g \subseteq N$
Then:
{{begin-eqn}}
{{eqn | lo= \forall g \in G:
      | l = g \circ N \circ g^{-1}
      | o = \subseteq
      | r = N
      | c =
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ N \circ g^{-1} } \circ g
      | o = \subseteq
      | r = N \circ g
      | c = {{Defof|Subset Product}}
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ N} \circ \paren {g^{-1} \circ g}
      | o = \subseteq
      | r = N \circ g
      | c = [[Subset Product within Semigroup is Associative/Corollary|Subset Product within Semigroup is Associative: Corollary]]
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ N} \circ e
      | o = \subseteq
      | r = N \circ g
      | c = {{Defof|Inverse Element}}
}}
{{eqn | ll= \leadsto
      | l = g \circ N
      | o = \subseteq
      | r = N \circ g
      | c = [[Coset by Identity]]
}}
{{end-eqn}}
Similarly:
{{begin-eqn}}
{{eqn | lo= \forall g \in G:
      | l = g^{-1} \circ N \circ g
      | o = \subseteq
      | r = N
      | c =
}}
{{eqn | ll= \leadsto
      | l = g \circ \paren {g^{-1} \circ N \circ g}
      | o = \subseteq
      | r = g \circ N
      | c = {{Defof|Subset Product}}
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ g^{-1} } \circ \paren {N \circ g}
      | o = \subseteq
      | r = g \circ N
      | c = [[Subset Product within Semigroup is Associative/Corollary|Subset Product within Semigroup is Associative: Corollary]]
}}
{{eqn | ll= \leadsto
      | l = e \circ \paren {N \circ g}
      | o = \subseteq
      | r = g \circ N
      | c = {{Defof|Inverse Element}}
}}
{{eqn | ll= \leadsto
      | l = N \circ g
      | o = \subseteq
      | r = g \circ N
      | c = [[Coset by Identity]]
}}
{{end-eqn}}
Thus we have:
:$N \circ g \subseteq g \circ N$
:$g \circ N \subseteq N \circ g$
By definition of [[Definition:Set Equality/Definition 2|set equality]]:
:$g \circ N = N \circ g$
Hence the result.
{{qed}}
\end{proof}

config: wiki


TITLE: Why isn't Higgs coupling considered a fifth fundamental force?
QUESTION [71 upvotes]: When I first learned about the four fundamental forces of nature, I assumed that they were just the only four kind of interactions there were. But after learning a little field theory, there are many other kinds of couplings, even in the standard model. So why isn't the Yukawa Higgs coupling considered a fifth fundamental force? To be a fundamental force, does there need to be a gauge boson mediating it?

REPLY [3 votes]: I agree with tparker's comment: it's for absolutely no good reason at all.
As discussed in this Résonaances blog post, there is a Higgs-mediated force between particles, which is a bit like scalar gravity, but with a weak-force-like range. Its Feynman diagrams look just like those for other forces. I can't see any good reason to deny fundamental-force status to this interaction in light of the fact that:

The nuclear force, which is carried by non-gauge bosons (pions), is called a force. Not a fundamental force, since pions aren't fundamental, but it's similar to the Higgs force otherwise. There's even a pion version of the Higgs mechanism.

The electromagnetic force is called fundamental even though its force carrier is a weird mixture of the fundamental SU(2) and U(1) gauge fields.

The weak force is called a fundamental force even though it barely has the qualities you'd normally associate with a force, and its force carriers are weird mixtures of the fundamental SU(2) and U(1) gauge fields and the fundamental Higgs field.

The Higgs force shares the weak force's weakness of not being quite fundamental because the Higgs that we see isn't quite the fundamental Higgs field. But it's not a composite particle either. I'm inclined to say that gravity, SU(3), SU(2), U(1), and the fundamental Higgs force are the five fundamental forces of our current standard model, and electromagnetism, the weak force, and the low-energy Higgs force should be classified as "dwarf fundamental forces".


TITLE: If $\sum a_n b_n <\infty$ for all $(b_n)\in \ell^2$ then $(a_n) \in \ell^2$
QUESTION [35 upvotes]: I'm trying to prove the following:

If $(a_n)$ is a sequence of positive numbers such that $\sum_{n=1}^\infty a_n b_n<\infty$ for all sequences of positive numbers $(b_n)$ such that $\sum_{n=1}^\infty b_n^2<\infty$, then $\sum_{n=1}^\infty a_n^2 <\infty$.

The context here is functional analysis homework, in the subject of Hilbert spaces.
Here's what I've thought:
Let $f=(a_n)>0$. Then the problem reads: if $\int f\overline{g}<\infty$ for all $g>0,g\in \ell^2$, then $f\in \ell^2$. This brings the problem into the realm of $\ell^p$ spaces.
I know the inner product is defined only in $\ell^2$, but it's sort of like saying: if $\langle f,g\rangle <\infty$ for all $g>0,g\in \ell^2$ then $f\in \ell^2$.
I read this as: "to check a positive sequence is in $\ell^2$, just check its inner product with any positive sequence in $\ell^2$ is finite, then you're done", which I find nice, but I can't prove it :P
From there, I don't know what else to do. I thought of Hölder's inequality which in this context states:
$$\sum_{n=1}^\infty a_nb_n \leq \left( \sum_{n=1}^\infty a_n^2 \right)^{1/2} \left( \sum_{n=1}^\infty b_n^2 \right)^{1/2}$$
but it's not useful here.

REPLY [0 votes]: It can be proven using the Hölder inequality — see lemma 1.8 (page 8) of these notes. (There may be mistakes; I typeset these from lecture notes.) There's no need to invoke heavy machinery like the uniform boundedness principle or even the Riesz representation theorem; it's a special case of a general result for $\ell^p$ spaces.


TITLE: product is defined by $(fg)(x)=\sum_{k=0}^{m+n} a_kb_{k-i} x^{k} $
QUESTION [0 upvotes]: Let $f(x)=\sum_{i=0}^{m} a_i x^i$ and $g(x)=\sum_{i=1}^{n} b_i x^i$ be two polynomial then their product is defined by $(fg)(x)=\sum_{k=0}^{m+n} a_kb_{k-i} x^{k} $.
Now if we tend $m,n \to \infty $ and let both the series $f$ and $g$ converges on $\mathbb{R}$, then how to write their product.
i.e., $ \left( \sum_{i=0}^{\infty} a_ix^i \right) \left(\sum_{i=1}^{\infty} b_i x^{i} \right)=? $
Can we express the product of the two series just similar form as in case of polynomial?
Help me, please.

REPLY [2 votes]: If $f(x)=\sum_{n=0}^{\infty} a_n x^n$ and $g(x)=\sum_{n=0}^{\infty} b_n x^n$ are power series which are convergent for $|x|<R$, then we have
$f(x)g(x)=\sum_{n=0}^{\infty} c_n x^n$ for $|x|<R$,
where $c_n= \sum_{k=0}^{n} a_kb_{n-k}$.
The power series $\sum_{n=0}^{\infty}c_nx^n$ is called the Cauchy product of $\sum_{n=0}^{\infty}a_nx^n$ and $\sum_{n=0}^{\infty}b_nx^n$


TITLE: Proof of number of flops required to reduce a n×(n+1) matrix
QUESTION [0 upvotes]: While studying the row reduction algorithm to solve a linear system, I came across a statement saying that "a flop is one arithmetic operation on two real floating point numbers. For an $n×(n+1)$ matrix, the reduction to echelon form can take $\frac {2n^3}{3}+\frac {n^2}{2}-\frac {7n}{6}.$ In contrast, further reduction to reduced echelon form needs at most $n^2$."
Does anyone know how to prove the above 2 formulas? Please bear in mind that I have only just begun to study linear algebra, and thus am unfamiliar with many technical vocabularies in linear algebra.<\p>

REPLY [1 votes]: In the standard row echelon form algorithm (without pivoting), at stage number $k$ you already have $0$'s below the diagonal in the first $k-1$ columns of your matrix $A$.  You divide each of the $n+1-k$ elements in row $k$ to the right of the diagonal by $A_{k,k}$: that's $n+1-k$ operations.  Then for each of the
$(n-k)(n+1-k)$ elements $A_{ij}$ with $i > k$ and $j > k$, you replace $A_{ij}$ by
$A_{ij} - A_{ik} A_{kj}$: that's one multiplication and one subtraction for each, thus $2 (n-k)(n+1-k)$ operations.  Then you replace $A_{kk}$ by $1$ and $A_{ik}$ by $0$ for $i > k$: no arithmetic involved there.  The total is
$$ \sum_{k=1}^n \left( n+1-k + 2 (n-k)(n+1-k)\right)$$
which turns out to be $$\dfrac{2}{3} n^3 + \frac{n^2}{2} - \dfrac{n}{6}$$
This is $n$ more than the answer you were given.  I don't see where they are saving those $n$ operations.


TITLE: The alternating group $A_4$ is generated by {(12)(34),(123)},
QUESTION [2 upvotes]: The alternating group $A_4$ is generated by {(12)(34),(123)}. Let $a = (12)(34)$, $b = (123)$. We see that $a^2 = 1, b^3 = 1$:
$$No.1:a^0 b^0 = 1$$
$$No.2: a^1 b^0=(12)(34)$$
$$No.3: a^0 b^1=(123)$$
$$No.4:b^2 = (123)(123) = (132)$$
$$No.5:ab = (12)(34)(123) = (243)$$
$$No.6:ab^2 = (12)(34)(123)(123) = (143)$$
$$No.7:ba = (123)(12)(34) = (134)$$
$$No.8:b^2a = (123)(123)(12)(34) = (123)(134) = (234)$$
$$No.9:bab = (123)(12)(34)(123) = (134)(123) = (124)$$
$$No.10:bab^2 = (123)(12)(34)(123)(123) = (124)(123) = (14)(32)$$
$$No.11:b^2 a b = (123)(123)(12)(34)(123) = (234)(123)=(13)(24)$$
$$No.12:b^2 a b^2 = (123)(123)(12)(34)(123)(123) = (123)(14)(32) = (142)$$
But 4 elements has 24 permutations, so half of them shall be in $|A_4|$.
Since those 12 are distinct, done.

REPLY [3 votes]: A(nother) conceptual proof goes like that.
$a = (12)(34)$ and $b = (123)$ are even permutations, so $H = \langle a, b \rangle \le A_{4}$.
$H$ contains an element of order $2$ and an element of order $3$, so it has order divisible by $2$ and $3$, hence its order is a multiple of $6$.
Now $A_{4}$ does not have a subgroup $H$ of order $6$. Such a subgroup would have index $2$ in $A_{4}$, and thus it would be normal in $A_{4}$. Now $H$ contains a normal subgroup of order $3$, and thus $A_{4}$ would have a unique subgroup of order $3$, which is clearly not the case.


TITLE: Principal G bundles v.s. Flat G connection
QUESTION [6 upvotes]: What is the difference between Principal G bundles v.s. Flat G connection?

I heard that for a discrete group $G$ (in physics, or a finite group $G$ in math), the principal G bundles is the same as the flat G connection.
I know the definitions, but I wish to know explicit cases where I can see their differences. Like this MO post.

REPLY [17 votes]: For a topological group $G$ and a path-connected base space $X$, a principal $G$-bundle is classified by a map $X \to BG$ where $BG$ is the classifying space, whereas a principal $G$-bundle with flat connection (which presumably is what you meant to ask about) is classified by a map $\pi_1(X) \to G$ (its monodromy), or equivalently by a map $X \to BG_{\delta}$, where $G_{\delta}$ is $G$ equipped with the discrete topology.
The two spaces above are the same when $G$ is discrete but different in general. For example,
$$\pi_1(BG_{\delta}) \cong G$$
while
$$\pi_1(BG) \cong \pi_0(G).$$
So already on a circle the classifications of principal $G$-bundles vs. principal $G$-bundles with flat connection are very different, and the difference persists for higher-dimensional spheres: $BG_{\delta}$ has no higher homotopy, but the higher homotopy groups of $BG$ are the higher homotopy groups of $G$ shifted down one index.
If your question was on a more basic level than this, the point is that a connection is extra structure you can put on a principal bundle that equips it with a notion of parallel transport, and flatness is an extra property guaranteeing that parallel transport only depends on the homotopy class of the path. Without a connection you don't even get a notion of parallel transport.


TITLE: Correlation maximization (Canonical correlation analysis)
QUESTION [0 upvotes]: A question concerning part b):

I replaced $X$ with $X=Xw_x$ and $Y$ with $Y=Yw_y$ and took the derivative wrt $w_x$ and $w_y$. Unfortunately, I wasn't able to get to the end as my dimensions do not match after applying the derivative quotient rule. Then, I looked at the solution and realized that the solution was completely different from mine.

My questions are:
1) Why doesn't the denominator matter? It contains the variables we're optimizing...
2) Why are we setting values for variances (with value 1 in this example)? If they don't matter shouldn't we just maximize the nominator?
3) Why can't I just normally optimize by taking the derivative of the whole Corr expression without any comments about the denominator and nominator and optimize all together?
NB: I know how Lagrange multipliers work, I just don't understand how/why we get the constraints in this example.

REPLY [1 votes]: This problem corresponds to the well-known Canonical Correlation Analysis (CCA).
Assuming two zero-mean random vectors ${\bf x}$ and ${\bf y}$, we define $x$ and $y$ as linear combinations of the elements of ${\bf x}$ and ${\bf y}$ (i.e. $x = {\bf x}^T{\bf w}_x$ and $y = {\bf y}^T{\bf w}_y$).
What we want in CCA is to find ${\bf w}_x$ and ${\bf w}_y$ that maximize the correlation between $x$ and $y$.
We define the correlation coefficient as:
$$
\rho = \frac{E[xy]}{\sqrt{E[x^2]E[y^2]}}
=\frac{E[{\bf w}_x^T {\bf x} {\bf y}^T {\bf w}_y]}
{\sqrt{E[{\bf w}_x^T {\bf x} {\bf x}^T {\bf w}_x]E[{\bf w}_y^T {\bf y} {\bf y}^T {\bf w}_y]}}
=\frac{{\bf w}_x^T E[{\bf x} {\bf y}^T] {\bf w}_y}
{\sqrt{{\bf w}_x^T E[{\bf x} {\bf x}^T] {\bf w}_x {\bf w}_y^T E[{\bf y} {\bf y}^T] {\bf w}_y}}
=\frac{{\bf w}_x^T {\bf C}_{xy} {\bf w}_y}
{\sqrt{{\bf w}_x^T {\bf C}_{xx} {\bf w}_x {\bf w}_y^T {\bf C}_{yy} {\bf w}_y}}
$$
Note that $\rho$ is the same regardless of the scaling of ${\bf w}_x$ and ${\bf w}_y$. If, for e.g. we multiply ${\bf w}_x$ by $\alpha$ and ${\bf w}_y$ by $\beta$ we get the original $\rho$:
$$
\rho=\frac{\alpha{\bf w}_x^T {\bf C}_{xy} \beta{\bf w}_y}
{\sqrt{\alpha{\bf w}_x^T {\bf C}_{xx} \alpha{\bf w}_x \beta{\bf w}_y^T {\bf C}_{yy} \beta{\bf w}_y}}
=\frac{\alpha \beta {\bf w}_x^T {\bf C}_{xy} {\bf w}_y}
{\sqrt{\alpha^2\beta^2}\sqrt{{\bf w}_x^T {\bf C}_{xx} {\bf w}_x {\bf w}_y^T {\bf C}_{yy} {\bf w}_y}}
$$
This means that we can always play (re-scale) ${\bf w}_x$ and ${\bf w}_y$ to modify the denominator without affecting $\rho$. Particularly, we use this fact to simplify the problem by setting to get solutions that satisfy:
$$
{\bf w}_x^T {\bf C}_{xx} {\bf w}_x = 1\\
{\bf w}_y^T {\bf C}_{yy} {\bf w}_y = 1
$$
Hence, the problem becomes optimizing the numerator of $\rho$ subject to the previous constraints.


TITLE: Geometric multiplicity, invertible matrices
QUESTION [4 upvotes]: Would appreciate help with the following problem:

Given an invertible $n \times n$ real matrix $A$ with eigenvalue $t$ of geometric multiplicity at least $2$, determine whether the following statement is true: "There is a real polynomial $Q(x)$ of degree smaller or equal to $n-2$ such that the inverse of $A$ equals $Q(A)$".

It's easy to prove a similar statement, that the inverse of A can be represented by an $n-1$ degree polynomial (if I am correct, this is true for any invertible matrix), but that's as far as I got. I was thinking maybe the Jordan form of $A$ can help me out, but I haven't gotten very far with that. Would appreciate hints!

REPLY [2 votes]: To expand on my comment: A typical way of showing that if $A$ is invertible then there is a polynomial $q(x)$ such that $A^{-1}=q(A)$ is to use Cayley-Hamilton: writing
$$\chi(x) = x^n + a_{n-1}x^{n-1}+\cdots+a_0$$
for the characteristic polynomial of $A$, we know that $a_0$ is the product of the eigenvalues, and so $A$ is invertible if and only if $a_0\neq 0$. The Cayley-Hamilton Theorem tells us that $\chi(A)=0$, so
$$0 = A^n + a_{n-1}A^{n-1}+\cdots + a_1A + a_0I,$$
from which we get that
$$-a_0I = A^n+a_{n-1}A^{n-1}+\cdots + a_1A,$$
hence
$$I =-\frac{1}{a_0}A\left( A^{n-1} + a_{n-1}A^{n-2}+\cdots + a_1I\right).$$
Thus, putting $q(x) = -\frac{1}{a_0}\left(x^{n-1}+a_{n-1}x^{n-2}+\cdots + a_1\right)$ gives the desired polynomial.
Of course, you can play the exact same game with the minimal polynomial instead of the characteristic polynomial. The matrix $A$ is invertible if and only if $0$ is not an eigenvalue, if and only if $x$ does not divide the minimal polynomial. The geometric multiplicity of $\mathbf{t}$ tells you something about the degree of the minimal polynomial: since the highest degree of $x-\mathbf{t}$ that divides the minimal polynomial is the size of the largest Jordan block associated to $\mathbf{t}$, and since the geometric multiplicity equals the number of Jordan blocks, if the algebraic multiplicity of $\mathbf{t}$ is, say, $m$, having geometric multiplicity $2$ tells you that there are at least two Jordan blocks associated to $\mathbf{t}$, and so the largest block will have size at most $m-1$; which tells you that if the largest power of $x-\mathbf{t}$ that divides $\chi(x)$ is $m$, then the largest power of $x-\mathbf{t}$ that divides the minimal polynomial is at most $m-1$.
Can you leverage that into showing that a $Q(x)$ as you want must exist?


TITLE: Is my DFA correct?
QUESTION [1 upvotes]: I have to construct a DFA with $\Sigma = \{A, C, D, X\}$ such that the DFA accepts the string $w = CA^{177}$ or $w = A^{177}C$ and sticks in the final state.
$A^{177}$ means $177$ times $A$. So $CA_{1} \cdots A_{177}$ and $A_{1} \cdots A_{177}C$ should be accepted and else should be rejected.
For that I've constructed the DFA which is shown in the picture.
The state $175A$ is a placeholder for the part of the DFA which counts $175 As$ and is not a single state.
I think we don't have to draw the whole DFA state by state, since it gets very big. Instead I'd draw a DFA like shown and describe what happens in $175A$ "state".
So the description for $175A$ would be like: $175A$ is a sub DFA with $175$ states, which implements $mod$ $175$.
Is my logic and the DFA correct? Is it minimal?
Thanks
Asg
See the DFA drawn by JFLAP1

REPLY [0 votes]: If the language to be recognized is $\{CA^{177}, \ A^{177}C\}$, your DFA is not correct since it accepts also the word $A^{177}XA^{177}C$ (and many others). The problem is that when your DFA read a "wrong" symbol such as '$D$' or '$X$', it goes back to the initial state, but it should be a "local sink".
A correct and minimal DFA recognizing the language $\{CA^{177}, \ A^{177}C\}$ over the alphabet $\Sigma = \{A,C,D,X\}$ is the following:

Disclaimer: The image is obtained using the xy package for $\LaTeX$, which is not supported by MathJax. Its (not minimal and not elegant) $\LaTeX$ source is:
&&*++[o][F-]{q_{C}} \ar[r]^A \ar[drr]_{C,D,X} &*++[o][F-]{q_{\mathit{CA}}} \ar[r]^A \ar[dr]^<<<<<{C,D,X} &\dots \ar[r]^A &*++[o][F-]{q_{\mathit{CA}^{176}}} \ar[dr]^A \ar[dl]^{C,D,X} \\
\ar[r]&*++[o][F-]{q_0} \ar[ur]^C \ar[dr]_A \ar[rrr]^<<<<<<<<<<{D,X} &&&*++[o][F-]{q_1} \ar@(ur,ul)[]|{A,C,\\D,X}&& *++[o][F=]{q_\mathrm{f}} \ar[ll]^<<<<<<<<<<<{A,C,D,X}\\
&&*++[o][F-]{q_{A}} \ar[r]_A \ar[urr]^{C,D,X} &\dots \ar[r]_A &*++[o][F-]{q_{\mathit{A}^{176}}} \ar[r]_A \ar[u]^{C,D,X} &*++[o][F-]{q_{\mathit{A}^{177}}} \ar[ur]_C \ar[ul]_<<<<{A,D,X}


TITLE: Math for computer programming
QUESTION [0 upvotes]: I'm a computer engineering student, and I'm trying to get a firm grasp of math before starting to program. I know that math is strictly related to programming, but I don't know what is the field of math most related to programming, for example, automata theory, compatibility theory, discrete math, type theory, category theory, lambda calculus etc can you guys tell me which math field is the most related to programming and computer science?
Thank you!

REPLY [0 votes]: It really depends heavily on what you are programming, I would even go as far as saying that programming in general does not really require any math skills beyond the overall understanding of the language and the notion of algorithm. However, to solve certain problems, maths skills will certainly help you

For designing algorithms and study their complexity in general, it is useful to be familiar with recursivity and induction, as well as recursive sequences. You will probably need to know how to classify the growth of sequence (the big O and small o notation)
For running scientific computations, like simulate a physical system or a biological ecosystem, you probably need a fair bit of analysis, know about ODE, PDE. Then the most important part is probably the results proving convergence of methods for solving them
There are also a lot of situation in which you want to apply linear algebra. I don't have examples on top of my head, but it is actually very common to compute the inverse of a matrix, or a base change. More advanced probably come up as well, even though a bit less often
If you do some data analysis, you definitely want a solid background in statistics
If you do machine learning, and especially neuron networks, I think you want to know at least the basics of multivariate geometry
If you want to experiment with functional programming, then category theory will be useful, especially if you try programming in Haskell. But it is by no means required.
If you want to understand the more theoretical aspects of computer science, and the general principles that make programming languages work in general, you probably need a bit of automata theory and formal languages, or even go till lambda-calculus and turing machines

As you can see, you don't really need to know any maths for programming, but as a programmer you will most certainly meet some maths, and even more so if you are a computer scientist in general. This list is certainly non exhaustive. My advice would be, if you want to have general knowledge in maths, to take a book of first year undergrad general and study from it, and doing the exercises. Everything you will find in there are what all mathematics rely on