Math Challenge - June 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #26
benorin
Homework Helper
Insights Author
1,328
122
10. Evaluate ##\int_0^{\infty}\frac{\log(x)}{x^2-1}dx.## (IR)

Owing to the infinite discontinuities of the integrand at ##x=0## and ##x=1##, I will split the integral up, $$I_1:=\int_0^{1}\frac{\log(x)}{x^2-1}dx\text{ and }I_2:=\int_1^{\infty}\frac{\log(x)}{x^2-1}dx$$

In ##I_1## substitute ##x=e^{-t}\implies dx=-e^{-t}dt\wedge 0\leq t \leq \infty## and the the integral becomes

$$\begin{gathered} I_1:=\int_0^{\infty}\frac{te^{-t}}{1-e^{-2t}}\, dt =\int_0^{\infty}t\sum_{k=0}^{\infty}e^{-(2k+1)t}\, dt \\ =\sum_{k=0}^{\infty}\int_0^{\infty}te^{-(2k+1)t}\, dt \\ \end{gathered} $$

let ##u=(2k+1)t## then we have
$$\begin{gathered} I_1=\sum_{k=0}^{\infty}\tfrac{1}{(2k+1)^2} \underbrace{\int_0^{\infty}te^{-u}\, dt}_{=\Gamma (2)=1} \\ =\sum_{k=0}^{\infty}\tfrac{1}{(2k+1)^2}=\lambda (2) \\ \end{gathered} $$

where ##\lambda (z)## is the Dirichlet Lambda Function.

The evaluation of the other integral, ##I_2##, goes the same as ##I_1## except that the first change of variable is ##x=e^t##, and the value is ##I_2 =\lambda (2)##. Hence the value of the given integral is ##2\lambda (2)##.
 
  • Like
Likes Delta2 and Adesh
  • #27
wrobel
Science Advisor
Insights Author
889
618
I see that 12a has already been solved but I think that ##i^i## is a countable set and I have not seen that was stressed anywhere in the thread perhaps I see not carefully
 
  • #28
735
188
I see that 12a has already been solved but I think that ##i^i## is a countable set and I have not seen that was stressed anywhere in the thread perhaps I see not carefully
Sir I would very much like to know that. What it means to say “##i^i## is a countable set” ? As for my knowledge till now, countable set is a set whose elements can be counted (it may be infinite but it is countably infinite). Please explain the point which needed to be stressed.
 
  • #29
wrobel
Science Advisor
Insights Author
889
618
$$i^i=\{e^{-\pi/2+2\pi n}\mid n\in\mathbb{Z}\}$$
 
  • Like
Likes dextercioby and Adesh
  • #30
etotheipi
My attempt at Question 15:

Proof by Induction:-

Base Case: Let ##n=1##, so we have a singleton set ##\{a_1\}## and the only subset of this is ##\{a_1\}## itself and it is of course, divisible by 1.

Let's say when we have ##k## different integers, ##\{a_1, a_2, a_3, \cdots , a_k\}## we take a subset ##\{a_{j1}, a_{j2}, a_{j3}, \cdots , a_{jm}\}## such that
$$
\frac{a_{j1} + a_{j2} + \cdots + a_{jm} }{k} = q
$$

Inductive Step: Let's add just one more integer to our previous set of integers, we add ##q##. Now, we have ##k+1## integers. So, we have ##\{a_1, a_2, \cdots , a_k, q\}##. Take the same subset that we took in the ##k##th case along with ##q## in it, so we have ##\{a_{j1}, a_{j2}, \cdots , a_{jm} , q\}##. Now,
$$
\frac{a_{j1} + a_{j2} + \cdots a_{jm} + q}{k+1} = \frac{kq + q}{k+1} \\
\frac{a_{j1} + a_{j2} + \cdots a_{jm} + q}{k+1} = q
$$

Hence, we can always choose a subset from the set of given ##n## integers such that ##n## divides the sum of members of subset.

A few words: I suspect the step when I said "let's add ##q## to our set and we will get ##k+1## integers" because I have to make sure that ##q## doesn't occur in the set ##\{a_1, a_2, \cdots a_k\}## (because we're asked in the question to prove for "##n## different integers"). This is the only thing I doubt, however, question-posters may find some other mistakes, they are welcome to inform me about the flaws in the proof.

I am not sure if this approach works, I think for the reason that you pointed out at the end that it needs to be proven for all possible sets. For instance, what if the new set of size ##k+1## has the new element ##q+3## instead of ##q##?

To restate the problem in a simpler form I was thinking that we suppose the parent set has ##n## elements. Each element can be expressed in the form ##an+b##, where ##b \in \{0,1,2,\dots, n-1\}##. We then need to show that given any combination of ##n## numbers (repetition allowed) from ##\{0,1,2,\dots, n-1\}##, we can always find ##k## of them such that their sum equals a multiple of ##n##.

For example, if ##n=3## so that ##b \in \{0,1,2\}##, for any combination of 3 numbers from that set (e.g. {0,0,0}, {1,2,2}, {1,2,3}, etc.) we must prove that we can always find a group in that combination that adds to a multiple of 3.
 
  • #31
15,778
14,090
#8) a)

Let ##I(\alpha ) := \int_0^\pi \log (1-2\alpha \cos(x)+\alpha^2)\,dx\quad (\alpha \geq 1)##, then

$$\begin{gathered} \tfrac{dI}{d\alpha } = \int_0^\pi \tfrac{\partial }{\partial \alpha} \log (1-2\alpha \cos(x)+\alpha ^2)\,dx = 2 \int_0^\pi \tfrac{\alpha -\cos (x) }{1-2\alpha \cos (x)+\alpha ^2} \,dx \\ = \tfrac{1}{\alpha} \int_0^\pi\left(1- \tfrac{1-\alpha ^2}{1-2\alpha \cos(x)+\alpha^2} \right) \,dx \\ \end{gathered}$$

I used a table of integrals here and got

$$\tfrac{dI}{d\alpha } =\tfrac{\pi}{\alpha }-\tfrac{2}{\alpha}\left[ \arctan \left(\tfrac{1+\alpha}{1-\alpha}\tan \left( \tfrac{x}{2}\right)\right)\right| _{x=0}^{\pi} =\tfrac{2\pi}{\alpha}$$

hence

$$I(\alpha )=2\pi \int\tfrac{d\alpha}{\alpha}= 2\pi\log | \alpha | + C$$

I'll leave the rest of the solution (determining the constant) to somebody else. Good luck!

Note: I've read this problem somewhere before.
The Feynman trick is the correct idea, but I'd like to see the complete integration, since this is a bit tricky to do. And what about ##|\alpha|=1##?
 
  • #32
15,778
14,090
Although, it is clearly written “n different integers”, but then also I want to ask if all of them are different or not all of them are equal? I mean is there a possibility that two integers could be same?
We consider ##n## different integers. Otherwise we would have ##n-1## many. It is the starting situation, not a resulting property.
 
  • #33
15,778
14,090
A few words: I suspect the step when I said "let's add ##q## to our set and we will get ##k+1## integers" because I have to make sure that ##q## doesn't occur in the set ##\{a_1, a_2, \cdots a_k\}## (because we're asked in the question to prove for "##n## different integers").
This is not the point. You cannot "add" an integer you like, since then you could always add ##n## and the statement becomes trivial. We have given any ##n## different integers.

Induction is the wrong idea, sum and division, however, was a good idea. Try different sums.
 
Last edited:
  • #34
15,778
14,090
$$i^i=\{e^{-\pi/2+2\pi n}\mid n\in\mathbb{Z}\}$$
You can do this with every complex number: ##z=re^{i\varphi}=re^{i(\varphi + 2n\pi)}.## We usually assume ##0\leq \varphi < 2\pi## as representation.
 
  • #35
wrobel
Science Advisor
Insights Author
889
618
You can do this with every complex number: z=reiφ=rei(φ+2nπ).z=re^{i\varphi}=re^{i(\varphi + 2n\pi)}.
##e^{i(\varphi+2n\pi)}## is one number while ##i^i## is the infinite set of numbers
 
Last edited:
  • #36
benorin
Homework Helper
Insights Author
1,328
122
Ignore this post, it contains an arithmetic error, for the correct solution, read post #40.

4. Let ##S:=\{\,(x,y,z)\in \mathbb{R}^3\,|\,x^2+y^2=(2-z)^2,\,0\leq z\leq 2\,\}## be the surface of a cone ##C## with a circular cross section and a peak at ##(0,0,2)##. The orientation of ##S## be such, that the normal vectors point outwards. Calculate the flux through ##S## of the vector field (FR)
$$
F\, : \,\mathbb{R}^3 \longrightarrow \mathbb{R}^3\, , \,F(x,y,z)=\begin{pmatrix}xy^2\\x^2y\\(x^2+y^2)(1-z)\end{pmatrix}.$$
I assume the cone has a base because it's oriented. Let ##S_1## denote the upper cone-shaped surface given by ##z=g(x,y):=2-\sqrt{x^2+y^2},\quad ( 0\leq x^2+y^2\leq 2^2)##. Also denote the ##x,y,## and ##z## components of ##\vec{F}## by ##P,Q,## and ##R##, respectively. Then

$$\begin{gathered} \iint_{S_1}\vec{F}\cdot d\vec{S} = \iint_{\text{Projection of } S_1\text{ in the }xy\text{-plane}}\left(-Pg_x-Qg_y+R\right)\, dA \\ = \iint_{x^2+y^2\leq 2^2}\left[\tfrac{2x^2y^2}{\sqrt{x^2+y^2}}+(x^2+y^2)\left(-1+\sqrt{x^2+y^2}\right)\right] \, dA\\= \int_{0}^{2\pi}\int_0^2\left(\tfrac{r^4\sin ^2\theta\cos ^2\theta}{r}+r^2(r-1)\right) r\, dr d\theta\\ =\int_{0}^{2\pi}\sin ^2\theta\cos ^2\theta\, d\theta\int_0^2r^4\, dr+\int_{0}^{2\pi}d\theta \int_0^2 (r^4-r^3)\, dr=\boxed{\tfrac{32\pi}{5}}\\ \end{gathered} $$

Let ##S_2## denote the circular disk ##z=h(x,y)=0,\quad (0\leq x^2+y^2\leq 2^2 )## with downward pointing normal. Then

$$\begin{gathered} \iint_{S_2}\vec{F}\cdot d\vec{S}=-\iint_{x^2+y^2\leq 2^2}(x^2+y^2)\, dA\\ = -\int_0^{2\pi}\, d\theta \int_0^2 r^3\, dr=\boxed{-8\pi}\\ \end{gathered}$$

Hence, adding the fluxes, we get ##\boxed{ \iint_{S}\vec{F}\cdot d\vec{S}=-\tfrac{8\pi}{5}}##.
 
Last edited:
  • #37
15,778
14,090
I assume the cone has a base because it's oriented. Let ##S_1## denote the upper cone-shaped surface given by ##z=g(x,y):=2-\sqrt{x^2+y^2},\quad ( 0\leq x^2+y^2\leq 2^2)##. Also denote the ##x,y,## and ##z## components of ##\vec{F}## by ##P,Q,## and ##R##, respectively. Then

$$\begin{gathered} \iint_{S_1}\vec{F}\cdot d\vec{S} = \iint_{\text{Projection of } S_1\text{ in the }xy\text{-plane}}\left(-Pg_x-Qg_y+R\right)\, dA \\ = \iint_{x^2+y^2\leq 2^2}\left[\tfrac{2x^2y^2}{\sqrt{x^2+y^2}}+(x^2+y^2)\left(-1+\sqrt{x^2+y^2}\right)\right] \, dA\\= \int_{0}^{2\pi}\int_0^2\left(\tfrac{r^4\sin ^2\theta\cos ^2\theta}{r}+r^2(r-1)\right) r\, dr d\theta\\ =\int_{0}^{2\pi}\sin ^2\theta\cos ^2\theta\, d\theta\int_0^2r^4\, dr+\int_{0}^{2\pi}d\theta \int_0^2 (r^4-r^3)\, dr=\boxed{\tfrac{32\pi}{5}}\\ \end{gathered} $$

Let ##S_2## denote the circular disk ##z=h(x,y)=0,\quad (0\leq x^2+y^2\leq 2^2 )## with downward pointing normal. Then

$$\begin{gathered} \iint_{S_2}\vec{F}\cdot d\vec{S}=-\iint_{x^2+y^2\leq 2^2}(x^2+y^2)\, dA\\ = -\int_0^{2\pi}\, d\theta \int_0^2 r^3\, dr=\boxed{-8\pi}\\ \end{gathered}$$

Hence, adding the fluxes, we get ##\boxed{ \iint_{S}\vec{F}\cdot d\vec{S}=-\tfrac{8\pi}{5}}##.
This is the wrong answer. The mistake is in the first part of your calculation, which I do not really understand what you did. Cover the cone with a disc ##D## and calculate ##\int_{D\cup S}F\vec{n}dS##.
 
  • #38
benorin
Homework Helper
Insights Author
1,328
122
I used a formula out of my old Stuart Calculus book, 4th ed., pg 1100: If ##\vec{F}=\left< P,Q,R\right>## and ##S:=\left\{(x,y,z) | z=g(x,y)\forall (x,y)\in D\right\}## then (with upward directed normal)
$$\iint_{S}\vec{F}\cdot d\vec{S}=\iint_{D}\left( -P \tfrac{\partial g}{\partial x}-Q \tfrac{\partial g}{\partial y}+R\right) \, dA$$

where the instance of ##z## in any of ##P,Q,R## is replaced by ##z=g(x,y)##. This is how I learned to calcullate flux through surfaces. Is this incorrect? I checked my integration and arithmetic with WolframAlpha.
 
  • #39
benorin
Homework Helper
Insights Author
1,328
122
Oh I see that I "lost" a factor of 2 on a single term along the way. 1 sec.
 
  • #40
benorin
Homework Helper
Insights Author
1,328
122
Corrected arithmetic error from previous post, ##\boxed{\boxed{\text{corrections are double boxed}}}##.

4. Let ##S:=\{\,(x,y,z)\in \mathbb{R}^3\,|\,x^2+y^2=(2-z)^2,\,0\leq z\leq 2\,\}## be the surface of a cone ##C## with a circular cross section and a peak at ##(0,0,2)##. The orientation of ##S## be such, that the normal vectors point outwards. Calculate the flux through ##S## of the vector field (FR)
$$
F\, : \,\mathbb{R}^3 \longrightarrow \mathbb{R}^3\, , \,F(x,y,z)=\begin{pmatrix}xy^2\\x^2y\\(x^2+y^2)(1-z)\end{pmatrix}.$$

I assume the cone has a base because it's oriented. Let ##S_1## denote the upper cone-shaped surface given by ##z=g(x,y):=2-\sqrt{x^2+y^2},\quad ( 0\leq x^2+y^2\leq 2^2)##. Also denote the ##x,y,## and ##z## components of ##\vec{F}## by ##P,Q,## and ##R##, respectively. Then

$$\begin{gathered} \iint_{S_1}\vec{F}\cdot d\vec{S} = \iint_{\text{Projection of } S_1\text{ in the }xy\text{-plane}}\left(-Pg_x-Qg_y+R\right)\, dA \\ = \iint_{x^2+y^2\leq 2^2}\left[\tfrac{2x^2y^2}{\sqrt{x^2+y^2}}+(x^2+y^2)\left(-1+\sqrt{x^2+y^2}\right)\right] \, dA\\ = \int_{0}^{2\pi}\int_0^2\left(\tfrac{\boxed{\boxed{-2}}r^4\sin ^2\theta\cos ^2\theta}{r}+r^2(r-1)\right) r\, dr d\theta\\ =\boxed{\boxed{-2}}\int_{0}^{2\pi}\sin ^2\theta\cos ^2\theta\, d\theta\int_0^2r^4\, dr+\int_{0}^{2\pi}d\theta \int_0^2 (r^4-r^3)\, dr=\boxed{\boxed{\tfrac{8\pi}{5}}}\\ \end{gathered} $$

Let ##S_2## denote the circular disk ##z=h(x,y)=0,\quad (0\leq x^2+y^2\leq 2^2 )## with downward pointing normal. Then

$$\begin{gathered} \iint_{S_2}\vec{F}\cdot d\vec{S}=-\iint_{x^2+y^2\leq 2^2}(x^2+y^2)\, dA\\ = -\int_0^{2\pi}\, d\theta \int_0^2 r^3\, dr=\boxed{-8\pi}\\ \end{gathered}$$

Hence, adding the fluxes, we get ##\boxed{\boxed{ \iint_{S}\vec{F}\cdot d\vec{S}=-\tfrac{32\pi}{5}}}##.
 
Last edited:
  • #41
15,778
14,090
Corrected arithmetic error from previous post, .



I assume the cone has a base because it's oriented. Let denote the upper cone-shaped surface given by . Also denote the and components of by and , respectively. Then


Let denote the circular disk with downward pointing normal. Then


Hence, adding the fluxes, we get .
Divergence is zero, flux is not. And consider the correct sign! The orientation is given in the problem statement.
 
  • #42
benorin
Homework Helper
Insights Author
1,328
122
Ahh, yes. Seems it was a negative two that I fudged. I've edited the corrected post #40, please refresh the page @fresh_42 .
 
  • #43
benorin
Homework Helper
Insights Author
1,328
122
The 3b1b (3 blue 1 brown) guy said you never really stop making stupid little mistakes, or something close to that. I see some evidence of this claim. Lol.
 
  • #44
15,778
14,090
The 3b1b (3 blue 1 brown) guy said you never really stop making stupid little mistakes, or something close to that. I see some evidence of this claim. Lol.
There is no fifth in the solution. It is quite simple if you use Gauß' theorem.
 
  • #45
Halc
Gold Member
293
239
I need clarification on problem 11: How to get a rope to fall if either nail is removed.
From what I can tell, the trick is to not have the rope fall, which I suppose could be done by making a loop of it. Maybe the problem is suggesting a loop (the phrase 'hang the rope around' sort of suggests one).

Suppose a 3m rope draped symmetrically between a pair of nails separated by a meter. The rope hands straight down on either side and kind of a curve between. Remove either nail and the rope is over twice as long on one side of the remaining nail as the other, so it just pulls the short side up and falls.

If the rope is a loop, then just reduce a 6 meter loop to a 3 meter rope by doubling it up.

This is way too easy of an answer, and so I presume there's something unstated in the problem that I'm not getting.
 
  • #46
benorin
Homework Helper
Insights Author
1,328
122
I will circle back to the flux thing after this post.

The Feynman trick is the correct idea, but I'd like to see the complete integration, since this is a bit tricky to do. And what about ##|\alpha|=1##?

Edit: The unabridged version.

#8) a) Let ##I(\alpha ) := \int_0^\pi \log (1-2\alpha \cos(x)+\alpha^2)\,dx\quad ( | \alpha | > 1)##, then

$$\begin{gathered} \tfrac{dI}{d\alpha } = \int_0^\pi \tfrac{\partial }{\partial \alpha} \log (1-2\alpha \cos(x)+\alpha ^2)\,dx = 2 \int_0^\pi \tfrac{\alpha -\cos (x) }{1-2\alpha \cos (x)+\alpha ^2} \,dx \\ = \tfrac{1}{\alpha} \int_0^\pi\left(1- \tfrac{1-\alpha ^2}{1-2\alpha \cos(x)+\alpha^2} \right) \,dx \\ \end{gathered}$$

now do Karl Weierstass' trick and apply the change the change of variables ##t=\tan \left(\tfrac{x}{2}\right) , 0\leq t\leq \infty\implies \cos (x)= \tfrac{1-t^2}{1+t^2}\text{ and } dx=\tfrac{2\, dt}{1+t^2}## to get

$$\begin{gathered} \tfrac{dI}{d\alpha } = 2\int_0^\infty \tfrac{\alpha -\tfrac{1-t^2}{1+t^2}}{1-2\alpha \left(\tfrac{1-t^2}{1+t^2}\right)+\alpha ^2}\cdot \tfrac{2\, dt}{1+t^2} = 4\int_0^\infty \tfrac{(\alpha+1)t^2+(\alpha -1)}{\left[ (\alpha +1)^2t^2+(\alpha -1) ^2\right] (1+t^2)}\, dt\\ \end{gathered}$$

Aside: partial faction decomposition of the integrand. Let ##A,B, C,## and ##D## be rational functions of ##\alpha##. Then set

$$\begin{gathered}\tfrac{(\alpha+1)t^2+(\alpha -1)}{\left[ (\alpha +1)^2 t^2+(\alpha -1) ^2\right] (1+t^2)}=\tfrac{At+B}{1+t^2}+\tfrac{Ct+D}{ (\alpha +1)^2 t^2+ (\alpha -1) ^2}\\ \implies (\alpha +1) t^2 + (\alpha -1)= (At+B) \left[ (\alpha +1)^2 t^2 + (\alpha -1) ^2 \right] + (Ct+D)(1+t^2)\\ \end{gathered}$$

solving this system of equations is quickest by plugging in enough values of ##t##, namely,

$$\begin{gathered} \boxed{t=0} : \alpha -1 = B(\alpha -1)^2+D\implies D=(\alpha -1)\left[ 1-B(\alpha -1)\right] \quad (eqn\, 1) \\ \boxed{t=i} : -2 = (Ai+B)\left[ (\alpha -1)^2+(\alpha +1)^2\right]\implies A=0 \quad (eqn \, 2)\text{ and } B=\tfrac{1}{2\alpha}\quad (eqn \, 3)\\ \end{gathered} $$

Now ##(eqn \, 2)## implies ##C=0## and substituting ##(eqn \, 3)## into ##(eqn \, 1)## gives ##D=\tfrac{1}{2}\left(\alpha - \tfrac{1}{\alpha}\right)##. End aside.

Hence we have

$$\begin{gathered} \tfrac{dI}{d\alpha } = 2\int_0^\infty\left( \tfrac{\tfrac{1}{\alpha}}{1+t^2}+\tfrac{\alpha -\tfrac{1}{\alpha}}{ (\alpha +1)^2 t^2+(\alpha -1) ^2}\right) \, dt \\ = \tfrac{2}{\alpha} \left[ \tan ^{-1} (t) \right| _{t=0}^{\infty}+2\tfrac{\alpha -\tfrac{1}{\alpha}}{(\alpha +1) ^2}\int_0^\infty \tfrac{dt}{ t^2+\left( \tfrac{\alpha -1}{\alpha +1}\right) ^2} \\= \tfrac{\pi}{\alpha} +2\tfrac{\alpha -\tfrac{1}{\alpha}}{(\alpha +1) ^2}\cdot \left( \tfrac{\alpha +1}{\alpha -1}\right)\left[ \tan ^{-1} \left( t\cdot \tfrac{\alpha +1}{\alpha -1}\right) \right| _{t=0}^{\infty} \\ = \boxed{\tfrac{2\pi}{\alpha}=\tfrac{dI}{d\alpha}}\\ \end{gathered}$$

hence

$$I(\alpha )=2\pi \int\tfrac{d\alpha}{\alpha}= 2\pi\log | \alpha | + C\quad (\text{for } | \alpha | > 1) $$

As for the case of ##\alpha =1##, I know that ##I(1)=0## but infuriatingly enough I cannot prove it with any clever trick thus far. I think there's gonna be something on par with the integral of a odd function over a symmetric interval vanishes--but I did trig, log, and basic integral identities for a half hour: no joy! I think I'm just tired. I hope it will come to me later...

Note: I've read this problem somewhere before.

Edit 2: Did I say after this post? Right. Well not right after...
 
  • #47
15,778
14,090
I hope it will come to me later...
You're closing in. Your answer is almost right and the two cases ##|\alpha|=1## are missing.
 
  • #49
Infrared
Science Advisor
Gold Member
938
525
@benorin Your answer is correct, but you can simplify: What is ##2\lambda(2)##?

@Halc The condition "will fall down" means that the rope is not supported by a nail. You could take the rope to be a loop, if that's helpful.
 
  • #50
StoneTemplePython
Science Advisor
Gold Member
1,203
597
Thanks for the the catch @StoneTemplePython Condition 1 should be "The ##\textbf{off-diagonal}## entries of ##A## are all positive." I should have checked more carefully.

so the 'right answer' is to apply Gerschgorin Discs / strict diagonal dominance and the result falls out. Here's a different approach:
the problem implies all diagonal entries are negative
##A = -D +B##
where ##B## is strictly positive except the diagonal is zero'd out, and ##D## is a diagonal matrix with positive diagonal entries. Multiplication by an invertible matrix doesn't change rank and it is convenient to homogenize the diagonal, so it suffices to check the invertibility of

## D^{-1}A = -I + D^{-1}B = -I + C##
where ##C## is strictly positive except its diagonal is zero

the problem tells us
##A\mathbf 1 \leq -\alpha \mathbf 1##
for some ##\alpha \gt 0##
where all inequalities are interpreted component-wise

re-scaling by positive numbers:
## \big(-I + C\big)\mathbf 1 = D^{-1}A\mathbf 1 \leq -\alpha D^{-1}\mathbf 1 \leq -\sigma \mathbf 1##
where ##\sigma := \alpha \cdot \min_i (D^{-1}_{i,i})## which implies ##\sigma## is positive. If for some reason ##\sigma \gt 1## then we can use an even looser upper bound and select ##\sigma := \frac{1}{2}##. Thus we have ##\sigma \in (0,1)##

re-arranging terms
## C\mathbf 1 \leq (1-\sigma)\mathbf 1##
and using the non-negativity in ##C##
## C^2\mathbf 1 \leq (1-\sigma)C\mathbf 1 \leq (1-\sigma)^2\mathbf 1##
##\longrightarrow C^k\mathbf 1 \leq (1-\sigma) C^{k-1}\mathbf 1\leq ... \leq (1-\sigma)^k\mathbf 1##
- - - - -
to help with interpretation:
##\mathbf x := C^{k-1}\mathbf 1##
## \mathbf x = C^{k-1}\mathbf 1 \leq (1-\sigma)^{k-1} \mathbf 1##
so we know ##0 \leq x_j \leq (1-\sigma)^{k-1}## and by non-negativity of ##C##, we can specialize to its jth column giving us
##x_j \mathbf c_j \leq (1-\sigma)^{k-1}\mathbf c_j ##
summing over the bound:
##C^{k}\mathbf 1 = C \mathbf x = \sum_{j=1}^n x_j \mathbf c_j\leq \sum_{j=1}^n (1-\sigma)^{k-1} \mathbf c_j =(1-\sigma)^{k-1} \cdot \sum_{j=1}^n \mathbf c_j = (1-\sigma)^{k-1} C\mathbf 1 \leq (1-\sigma)^k \mathbf 1##
- - - - -

if ##C## had an eigenvalue with modulus ##\geq 1##, we'd have

##1##
## \leq \big \Vert C^k\big \Vert_F##
## = \Big(\sum_{i=1}^n\sum_{j=1}^n \vert c^{(k)}_{i,j}\vert^2 \Big)^\frac{1}{2}##
## \leq \Big(\sum_{i=1}^n\sum_{j=1}^n \vert c^{(k)}_{i,j}\vert \Big) \text{ (triangle inequality)}##
##=\sum_{i=1}^n\sum_{j=1}^n c^{(k)}_{i,j}##
## = \mathbf 1^T C^k \mathbf 1##
##\leq (1-\sigma)^k \mathbf 1^T \mathbf 1##
##=(1-\sigma)^k \cdot n##

but the upper bound may be arbitrarily small for large enough k thus the spectral radius of ##C## is ##\lt 1##, and in particular ##C## can't have an eigenvalue of 1 telling us
##\det\big(-I+C\big ) \neq 0\longrightarrow \det\big(A\big) \neq 0##
 
Last edited:

Related Threads on Math Challenge - June 2020

Replies
137
Views
12K
M
Replies
104
Views
10K
Replies
77
Views
10K
Replies
150
Views
11K
  • Last Post
3
Replies
61
Views
7K
Replies
64
Views
10K
Replies
52
Views
7K
Replies
33
Views
6K
Replies
60
Views
5K
Replies
98
Views
8K
Top