calculus - Find a Continuous Function

I am having a problem with this exercise. Could someone help?

Suppose $a \in (0,1)$ is a real number which is not of the form $\frac{1}{n}$ for any natural number n
n. Find a function f which is continuous on $[0, 1]$ and such that $f (0) = f (1)$ but which does not satisfy $f (x) = f (x + a)$ for any x with $x$, $x + a \in [0, 1]$.

I noticed that this condition is satisfied if and only if $f(x) \geq f(0)$

Thank you in advance

Answer

Look at $f(x) = \sin(2\pi x)$. For which values of $a$ can you find an $x \in [0,1]$ with $x+a \in [0,1]$ and $f(x) = f(x+a)$? In particular, if you additionally require $a > \frac{1}{2}$, can such an $a$ exist at all?

Once you've answered that you've solved your problem for some values of $a$. Which are those?

A general solution can be found in the answers to Universal Chord Theorem (Link found by the user who asked the question). To quote $$
f(x) = \sin^2\left(\frac{\pi x}{a}\right) - x \ \sin^2\left(\frac{\pi}{a}\right)

$$

is a solution. This works because $f(x) = f(x+a)$ implies $a \sin^2\left(\frac{\pi}{a}\right) = 0$ and thus $a=\frac{1}{n}$ for some $n \in \mathbb{N}$. The answers to the linked questions also prove that $a \neq \frac{1}{n}$ for every $n \in \mathbb{N}$ is a necessary condition for a solution to exist.

linear algebra - Every element in $SU(2)$ has the form $begin{bmatrix} alpha& beta\ -bar{beta} & -bar{alpha}end{bmatrix}$ with $alpha, betain mathbb{C}$

I want to prove that every element in $\operatorname{SU}(2)$ has the form
$$
\begin{bmatrix} \alpha& \beta\\ -\bar{\beta} & -\bar{\alpha}\end{bmatrix},
$$
with $\alpha, \beta\in \mathbb{C}$, for this I took an arbitrary element
$$

\begin{bmatrix} \alpha& \beta\\ \gamma & \delta\end{bmatrix},
$$
and I arrive at the following equalities
$$
\alpha\delta-\beta\gamma=1, \quad \alpha\bar{\alpha}+\beta\bar{\beta}=1, \quad \bar{\alpha}\gamma+\bar{\beta}\delta=0, \quad \gamma\bar{\gamma}+\delta\bar{\delta}=1
$$

but I don't know from here how to prove that $\gamma=-\bar{\beta}$ and $\delta=-\bar{\alpha}$, any idea? Thank you.

What are some fast ways to generate random numbers?

Many programming languages come with a function to give random numbers. I wonder how they implement that. Also, assuming the language doesn't have a random function, is there a way to generate them quickly? Another related question is if the language (and included libraries) had this random function included, could someone write a faster one just using the "primitives" of the language? I don't remember ever hearing about this in college but for probability simulation I have been using random numbers a lot and now am wondering how they do it and get it so there is no bias and not the same repeating pattern of numbers. Do they just reference some internal clocks of the computer? If so, wouldn't that then bias the numbers some?

I should clarify and say what if I only needed random numbers from 0 to 255 (8 bit) to simulate most card hands, die rolls... Is there a way I can write my own or has anyone on this site tinkered around with writing their own successfully?

It would be fun on a very fast computer to have some algorithm that gives me random numbers as quickly as possible (even storing them in memory or streaming them). For example, if I wanted 1 trillion random numbers to run a simulation without spending a lot of CPU cycles generating them so there is more available CPU speed to actually run the simulation.

elementary number theory - Finding inverse of polynomial in a field

I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take:

In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + 1$.

My understanding is that one needs to use the (Extended?) Euclidean Algorithm and Bezout's Identity. Here's what I currently have:

Proceeding with Euclid's algorithm:

$$ x^3 + 2x + 1 =(x^2 + 1)(x) + (x + 1) \\\\

x^2 + 1 = (x + 1)(2 + x) + 2$$

We stop here because 2 is invertible in $\mathbb{Z}_3[x]$. We rewrite it using a congruence:

$$(x+1)(2+x) \equiv 2 \mod{(x^2+1)}$$

I don't understand the high level concepts sufficiently well and I'm lost from here. Thoughts?

Wikipedia has a page on this we a decent explanation, but it's still not clear in my mind.

Note that this question has almost the same title, but it's a level of abstraction higher. It doesn't help me, as I don't understand the basic concepts.

Thanks.

Answer

Write $f := x^3+2x+1$ and $g := x^2+1$. We want to find the inverse of $g$ in the field $\mathbb F_3[x]/(f)$ (I prefer to write $\mathbb F_3$ instead of $\mathbb Z_3$ to avoid confusion with the $3$-adic integers), i.e. we are looking for a polynomial $h$ such that $gh \equiv 1 \pmod f$, or equivalently $gh+kf=1$ for some $k\in \mathbb F_3[x]$. The Euclidean algorithm can be used to find $h$ and $k$:
\begin{align}
f &= x\cdot g+(x+1)\\
g &= (x+2)\cdot(x+1) + 2\\
(x+1) &= (2x)\cdot2 + 1
\end{align}

Working backwards, we find
\begin{align}
1 &= (x+1)-(2x)\cdot 2\\
&= (x+1)-(2x)(g-(x+2)(x+1))\\
&= (2x^2+x+1)(x+1)-(2x)g\\
&= (2x^2+x+1)(f-xg)-(2x)g\\
&= (2x^2+x+1)f- (x^3+2x^2)g\\
&= (2x^2+x+1)f - (2x^3+x^2)g\\
&= (2x^2+x+1)f + (x^3+2x^2)g.
\end{align}

So, the inverse of $g$ modulo $f$ is $h = x^3+2x^2 \pmod f = 2x^2+x+2 \pmod f$.

linear algebra - Relation between the rank of the matrix and its characteristic polynomial?

Is there some kind of relation between the rank of the matrix and its characteristic polynomial?After searching through various posts

Say if $A \in M_{5}(\Bbb{R})$ and its characteristic polynomial is $\alpha x^5 + \beta x^4 + \gamma x^3 =0 $,then the rank of matrix $A$ = ?

I am unable to estalish the relation ,like I know that from characteristic polynomial i can obtain the eigenvalues and hence the trace and determinant of the matrix and now the question is if i know the trace and determinat of the matrix can i obtain some information about the rank of the matrix(the number of linearly independent rows in the rref).

I was looking at this question but still i am not aware of any trick or relation.

Answer

If the matrix is diagonalizable, rank = degree of the characteristic polynomial minus the order of multiplicity of root 0 (in the example, the rank of the matrix is 5 - 3 = 2).

In fact, in this case, writing $M=PDP^{-1}$ with $D$ diagonal matrix with $n-r$ zeros, and transforming it into $MP=PD$, it means that if the columns of $P$ are denoted $P_k$, we have $MP_k=\lambda_k P_k$ with, say, the last $n-r$ vectors associated with eigenvalue $0$, (and only them) i.e. we have exactly $n-r$ independant vectors belonging to the kernel.

linear algebra - Diagonalizability of $A in M_{n}(Bbb{R})$ (Upper traingular matrix) with all diagonal entries 1 and $A neq I$?

If $A \in M_{n}(\Bbb{R})$ is an Upper triangular matrix with diagonal entries $1$ such that $A \neq I$, then what can we say about the diagonalizability of $A$ ?

I know that if the matrix has distinct eigenvalues or the set of eigenvectors are linearly independent then the matrix is diagonalizable.

And that the eigenvalues of the triangular matrices are given by the diagonal elements like here and here, but they work nocely if we had distinct elements on the main diagonal.

But in my case I have same value 1 on the main diagonal, how can I approach about the diagonalizability of the matrix?

Answer

It isn't diagonalizable. Your matrix is of the form $I+N$ where $I$ is the identity matrix and $N$ is strictly upper triangular. You can check that being strictly upper triangular means that $N^n=0$, since if the $e_i$ are the basis vectors, and $E_m$ is the subspace spanned by $e_1,\ldots,e_m$, with $E_0=0$ then you can check that $NE_m \subseteq E_{m-1}$, so $N^nE_n = E_0=0$. However since $A\ne I$, $N\ne 0$. Now suppose $M$ diagonalizes $A$, so $MAM^{-1} = D$ for $D$ a diagonal matrix. Then $M(I+N)M^{-1}=MIM^{-1}+MNM^{-1} = D$, but $MIM^{-1}=I$, so we in fact have $MNM^{-1}=D-I$, so in fact $N$ must be diagonalizable. However we still have $(MNM^{-1})^n=0$, so if $D-I$ has elements $\lambda_1,\ldots,\lambda_n$ on the diagonal, then $\lambda_i^n=0$, which implies $\lambda_i=0$, hence $D-I=0$. Thus we would have that $D=I$, and $N=0$, contradicting the assumption that $A\ne I$, so $N\ne 0$.

summation - Mathematical induction proof that $sumlimits_{k=2}^{n-1} {k choose 2} = {n choose 3} $

I have a problem with a mathematical equation. I don’t find the given solution.

This is the equation: $\sum\limits_{k=2}^{n-1} {k \choose 2} = {n \choose 3} $

I should show with induction that the expression is correct for every $n >= 3$.

I started with the beginning of the induction. For $n = 3$.

$\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3} $
That’s correct.

Now I don’t know how to dissolve that equation. The solution should be:

$\sum\limits_{k=2}^{n-1} {k \choose 2} + {n \choose 2} = {n \choose 3} + {n \choose 2} = {n + 1 \choose 3} $

Why ${n \choose 2}$? It would be awesome, if someone could tell me the steps or give some tips how I could reach that solution.

Edit:

Well, at that point I am:

1. Beginning of the induction: $\sum\limits_{k=2}^{2} {2 \choose 2} = 1 = {3 \choose 3}$




2. Induction step n + 1: $\sum\limits_{k=2}^{n} {k \choose 2} + {n \choose 3}$
   Thats my assumption: ${n \choose 3}$.




3. Change the first addend with the assumption, so I get ${n \choose 2} + {n \choose 3}$




4. Add it into the binomial coefficient formula: ${n! \choose 2!(n-2)!} + {n! \choose 3!(n-3)!}$

I have it like @david-mitra. Whats wrong with that way?

Thanks.

Answer

We wish to prove:
$$
\sum_{k=2}^{n-1} {k\choose 2}= {n\choose3},\quad n\ge3.\tag{1}
$$

If you want to prove that equation (1) holds for all $n\ge 3$ using induction:

1) Show that the equation is true for $n=3$:

$$
\sum_{k=2}^{3-1} {k\choose 2}= {2\choose2}= {3\choose3}.\tag{1}
$$

2) Assume that the equation is true for $n=m$:
$$
\color{maroon}{\sum_{k=2}^{m-1} {k\choose 2}}= \color{maroon}{m\choose3 }.

$$

3) Now show that the equation must be true for $n=m+1$:

$$\eqalign{
\sum_{k=2}^{(m+1)-1} {k\choose 2}
&=\sum_{k=2}^{m } {k\choose 2}\cr
&=\sum_{k=2}^{m-1 } {k\choose2} +\color{darkgreen}{\sum_{k=m}^m {k\choose2}}\cr
&=\biggl[\ \color{maroon}{ \sum_{k=2}^{m-1 } {k\choose 2}}\ \biggr]+\color{darkgreen}{m\choose2}\cr
&= \color{maroon}{ m\choose 3} +{m\choose2}\cr


&= {m!\over (m-3)! 3!}+ {m!\over (m-2)! 2!}\cr
&={ m(m-1)(m-2)\over 3!} +{ m(m-1) \over 2!} \cr
&= m(m-1)({m-2\over 6}+{3\over 6 })\cr

&= { m(m-1)(m+1)\over 6} \cr
&={m+1\choose 3}.

}
$$