text:
# [texhax] using epsf.tex

Phil Parker phil at math.twsu.edu
Wed Jun 4 22:33:15 CEST 2003

How does one use epsf.tex with 2e?

I used epsf.tex with 2.09 to include EPS figures in LaTeX documents. Now
with 2e I get an error message:

! Undefined control sequence.
\@tempa ->\@nil

l.398 ...s $e_1$, $e_2$, $z$ and signature $+-+$.}
\label{f1}
The control sequence at the end of the top line
of your error message was never \def'ed. If you have
misspelled it (e.g., \hobx'), type I' and the correct
spelling (e.g., I\hbox'). Otherwise just continue,
and I'll forget about whatever was undefined.

everytime I try to include an EPS picture. (In case it's not clear, the
l.398 stuff is the end of the \caption call that follows the \epsffile call.
Here's the relevant excerpt from jp3.tex:

\begin{figure}
\begin{center}
\leavevmode
\epsffile{./h3ppm_snt_tl3.eps}
\caption{\small Geodesic surfaces in $H_3$ using exponential coordinates
with axes $e_1$, $e_2$, $z$ and signature $+-+$.}\label{f1}
\end{center}
\end{figure}

That's copied straight from files that worked with 2.09 long ago; I haven't
needed this with 2e until now.)

I assume the way to load epsf is:

\usepackage{epsf}

at least it claims it's loaded in the log file:

This is epsf.tex' v2.7k <10 July 1997>

And this is the version info on the linux box (RH, I think) where it's
running:

This is TeX, Version 3.14159 (Web2C 7.3.1) (format=latex 2002.4.12)  4 JUN
2003 21:06 **jp3
(jp3.tex
LaTeX2e <2000/06/01>

--
Phil Parker
--------------------------------------------
URL http://www.math.twsu.edu/Faculty/Parker/
Random quote:
Keep the old as long as it is good,
and take the new as soon as it is better.


text:
# I need to know an initial amount. I have the rate and the end amount.

#### nsupanda

##### New member
I profusely apologize if this is posted in the wrong thread, it seems like it would be pre-algebra because it seems like it would be a simple equation (even though I can't figure it out).

This is not a homework problem, but a real-world problem I'm having at work.

I need to know an "initial amount" that is multiplied by a percentage (11.52%) to get an "end amount" of $60,532.61. My boss told me to take$60,532.61 × (1-0.1152) to get the "initial amount" but it just isn't working for me. When I do that, I get $53,559.25. And when I take$53,559.25 + ($53,559.25 × 0.1152) I end up getting$59,729.28, which is NOT $60,532.61. What am I doing wrong? #### HallsofIvy ##### Elite Member You say the amount is "multiplied" by the percentage but if that were the case the result would be much less than the amount. It looks to me like you intend that the amount be increased by that percentage: R= A+AP= A(1+ P) so that A= R/(1+ P). Instead of multiplying by 1- 0.1152 you should be dividing by 1+ 0.1152.$60,532.61/1.1152= $54,279.60. #### Dr.Peterson ##### Elite Member I profusely apologize if this is posted in the wrong thread, it seems like it would be pre-algebra because it seems like it would be a simple equation (even though I can't figure it out). This is not a homework problem, but a real-world problem I'm having at work. I need to know an "initial amount" that is multiplied by a percentage (11.52%) to get an "end amount" of$60,532.61.

My boss told me to take $60,532.61 × (1-0.1152) to get the "initial amount" but it just isn't working for me. When I do that, I get$53,559.25. And when I take $53,559.25 + ($53,559.25 × 0.1152) I end up getting $59,729.28, which is NOT$60,532.61.

What am I doing wrong?
It's great that you checked your answer as you did. Often a failed check can be turned into a successful equation!

Replacing the answer you are checking with the variable x, the check, $53,559.25 + ($53,559.25 * 0.1152) =? $60,532.61, becomes the equation x + (x * 0.1152) = 60,532.61. To solve this equation, combine like terms on the left to get 1.1152x = 60,532.61, and solve by dividing: x = 60,532.61/1.1152 = 54,279.60. What your boss is doing is reducing$60,532.61 by 11.52%, which is not the same as undoing an increase by 11.52%, because he is taking 11.52% of the resulting amount rather of the initial amount. That is a common mistake. You are wise to have checked the answer.

format: plain


text:
# Linear Algebra/Self-Composition

Linear Algebra
 ← Nilpotence Self-Composition Strings →

This subsection is optional, although it is necessary for later material in this section and in the next one.

A linear transformations $t:V\to V$, because it has the same domain and codomain, can be iterated.[1] That is, compositions of $t$ with itself such as $t^2=t\circ t$ and $t^3=t\circ t\circ t$ are defined.

Note that this power notation for the linear transformation functions dovetails with the notation that we've used earlier for their squared matrix representations because if ${\rm Rep}_{B,B}(t)=T$ then ${\rm Rep}_{B,B}(t^j)=T^j$.

Example 1.1

For the derivative map $d/dx:\mathcal{P}_3\to \mathcal{P}_3$ given by

$a+bx+cx^2+dx^3\stackrel{d/dx}{\longmapsto} b+2cx+3dx^2$

the second power is the second derivative

$a+bx+cx^2+dx^3\stackrel{d^2/dx^2}{\longmapsto} 2c+6dx$

the third power is the third derivative

$a+bx+cx^2+dx^3\stackrel{d^3/dx^3}{\longmapsto} 6d$

and any higher power is the zero map.

Example 1.2

This transformation of the space of $2 \! \times \! 2$ matrices

$\begin{pmatrix} a &b \\ c &d \end{pmatrix} \stackrel{t}{\longmapsto} \begin{pmatrix} b &a \\ d &0 \end{pmatrix}$

has this second power

$\begin{pmatrix} a &b \\ c &d \end{pmatrix} \stackrel{t^2}{\longmapsto} \begin{pmatrix} a &b \\ 0 &0 \end{pmatrix}$

and this third power.

$\begin{pmatrix} a &b \\ c &d \end{pmatrix} \stackrel{t^3}{\longmapsto} \begin{pmatrix} b &a \\ 0 &0 \end{pmatrix}$

After that, $t^4=t^2$ and $t^5=t^3$, etc.

These examples suggest that on iteration more and more zeros appear until there is a settling down. The next result makes this precise.

Lemma 1.3

For any transformation $t:V\to V$, the rangespaces of the powers form a descending chain

$V\supseteq \mathcal{R}(t)\supseteq\mathcal{R}(t^2)\supseteq\cdots$

and the nullspaces form an ascending chain.

$\{\vec{0}\,\}\subseteq\mathcal{N}(t)\subseteq\mathcal{N}(t^2)\subseteq\cdots$

Further, there is a $k$ such that for powers less than $k$ the subsets are proper (if $j then $\mathcal{R}(t^j)\supset\mathcal{R}(t^{j+1})$ and $\mathcal{N}(t^j)\subset\mathcal{N}(t^{j+1})$), while for powers greater than $k$ the sets are equal (if $j\geq k$ then $\mathcal{R}(t^j)=\mathcal{R}(t^{j+1})$ and $\mathcal{N}(t^j)=\mathcal{N}(t^{j+1})$).

Proof

We will do the rangespace half and leave the rest for Problem 6. Recall, however, that for any map the dimension of its rangespace plus the dimension of its nullspace equals the dimension of its domain. So if the rangespaces shrink then the nullspaces must grow.

That the rangespaces form chains is clear because if $\vec{w}\in\mathcal{R}(t^{j+1})$, so that $\vec{w}=t^{j+1}(\vec{v})$, then $\vec{w}=t^{j}(\,t(\vec{v})\,)$ and so $\vec{w}\in\mathcal{R}(t^{j})$. To verify the "further" property, first observe that if any pair of rangespaces in the chain are equal $\mathcal{R}(t^{k})=\mathcal{R}(t^{k+1})$ then all subsequent ones are also equal $\mathcal{R}(t^{k+1})=\mathcal{R}(t^{k+2})$, etc. This is because if $t:\mathcal{R}(t^{k+1})\to \mathcal{R}(t^{k+2})$ is the same map, with the same domain, as $t:\mathcal{R}(t^{k})\to \mathcal{R}(t^{k+1})$ and it therefore has the same range: $\mathcal{R}(t^{k+1})=\mathcal{R}(t^{k+2})$ (and induction shows that it holds for all higher powers). So if the chain of rangespaces ever stops being strictly decreasing then it is stable from that point onward.

But the chain must stop decreasing. Each rangespace is a subspace of the one before it. For it to be a proper subspace it must be of strictly lower dimension (see Problem 4). These spaces are finite-dimensional and so the chain can fall for only finitely-many steps, that is, the power $k$ is at most the dimension of $V$.

Example 1.4

The derivative map $a+bx+cx^2+dx^3\stackrel{d/dx}{\longmapsto} b+2cx+3dx^2$ of Example 1.1 has this chain of rangespaces

$\mathcal{P}_3\supset\mathcal{P}_2\supset\mathcal{P}_1 \supset\mathcal{P}_0\supset\{\vec{0}\,\}=\{\vec{0}\,\}=\cdots$

and this chain of nullspaces.

$\{\vec{0}\,\}\subset\mathcal{P}_0\subset\mathcal{P}_1\subset\mathcal{P}_2 \subset\mathcal{P}_3=\mathcal{P}_3=\cdots$
Example 1.5

The transformation $\pi:\mathbb{C}^3\to \mathbb{C}^3$ projecting onto the first two coordinates

$\begin{pmatrix} c_1 \\ c_2 \\ c_3 \end{pmatrix} \stackrel{\pi}{\longmapsto} \begin{pmatrix} c_1 \\ c_2 \\ 0 \end{pmatrix}$

has $\mathbb{C}^3\supset\mathcal{R}(\pi)=\mathcal{R}(\pi^2)=\cdots$ and $\{\vec{0}\,\}\subset\mathcal{N}(\pi)=\mathcal{N}(\pi^2)=\cdots\,$.

Example 1.6

Let $t:\mathcal{P}_2\to \mathcal{P}_2$ be the map $c_0+c_1x+c_2x^2 \mapsto 2c_0+c_2x.$ As the lemma describes, on iteration the rangespace shrinks

$\mathcal{R}(t^0)=\mathcal{P}_2 \quad \mathcal{R}(t)=\{a+bx\,\big|\, a,b\in\mathbb{C}\} \quad \mathcal{R}(t^2)=\{a\,\big|\, a\in\mathbb{C}\}$

and then stabilizes $\mathcal{R}(t^2)=\mathcal{R}(t^3)=\cdots$, while the nullspace grows

$\mathcal{N}(t^0)=\{0\} \quad \mathcal{N}(t)=\{cx\,\big|\, c\in\mathbb{C}\} \quad \mathcal{N}(t^2)=\{cx+d\,\big|\, c,d\in\mathbb{C}\}$

and then stabilizes $\mathcal{N}(t^2)=\mathcal{N}(t^3)=\cdots$.

This graph illustrates Lemma 1.3. The horizontal axis gives the power $j$ of a transformation. The vertical axis gives the dimension of the rangespace of $t^j$ as the distance above zero— and thus also shows the dimension of the nullspace as the distance below the gray horizontal line, because the two add to the dimension $n$ of the domain.

As sketched, on iteration the rank falls and with it the nullity grows until the two reach a steady state. This state must be reached by the $n$-th iterate. The steady state's distance above zero is the dimension of the generalized rangespace and its distance below $n$ is the dimension of the generalized nullspace.

Definition 1.7

Let $t$ be a transformation on an $n$-dimensional space. The generalized rangespace (or the closure of the rangespace) is $\mathcal{R}_\infty(t)=\mathcal{R}(t^n)$ The generalized nullspace (or the closure of the nullspace) is $\mathcal{N}_\infty(t)=\mathcal{N}(t^n)$.

## Exercises

Problem 1

Give the chains of rangespaces and nullspaces for the zero and identity transformations.

Problem 2

For each map, give the chain of rangespaces and the chain of nullspaces, and the generalized rangespace and the generalized nullspace.

1. $t_0:\mathcal{P}_2\to \mathcal{P}_2$, $a+bx+cx^2\mapsto b+cx^2$
2. $t_1:\mathbb{R}^2\to \mathbb{R}^2$,
$\begin{pmatrix} a \\ b \end{pmatrix}\mapsto\begin{pmatrix} 0 \\ a \end{pmatrix}$
3. $t_2:\mathcal{P}_2\to \mathcal{P}_2$, $a+bx+cx^2\mapsto b+cx+ax^2$
4. $t_3:\mathbb{R}^3\to \mathbb{R}^3$,
$\begin{pmatrix} a \\ b \\ c \end{pmatrix}\mapsto\begin{pmatrix} a \\ a \\ b \end{pmatrix}$
Problem 3

Prove that function composition is associative $(t\circ t)\circ t=t\circ (t\circ t)$ and so we can write $t^3$ without specifying a grouping.

Problem 4

Check that a subspace must be of dimension less than or equal to the dimension of its superspace. Check that if the subspace is proper (the subspace does not equal the superspace) then the dimension is strictly less. (This is used in the proof of Lemma 1.3.)

Problem 5

Prove that the generalized rangespace $\mathcal{R}_\infty(t)$ is the entire space, and the generalized nullspace $\mathcal{N}_\infty(t)$ is trivial, if the transformation $t$ is nonsingular. Is this "only if" also?

Problem 6

Verify the nullspace half of Lemma 1.3.

Problem 7

Give an example of a transformation on a three dimensional space whose range has dimension two. What is its nullspace? Iterate your example until the rangespace and nullspace stabilize.

Problem 8

Show that the rangespace and nullspace of a linear transformation need not be disjoint. Are they ever disjoint?

Solutions

Linear Algebra
 ← Nilpotence Self-Composition Strings →


text:
# How to do formatting? [duplicate]

I need help with formatting like how to use logs, lims, superscripts and subscripts etc.

## migrated from math.stackexchange.comFeb 1 '14 at 20:31

This question came from our site for people studying math at any level and professionals in related fields.

Well, above the upper right corner of the text box for your question/answer there is little '?' sign. After clicking the sign it will show you list of basic formatting or you can get to a different site for 'advanced help'. Also you can use LaTeX for math formatting because the server runs MathJax script.

But to cover just the basics:

To format math expressions you can must enclose the math in '\$' from each side. So, in order to write something like this:$x^2 + 2$, I had to write \$x^2 + 2\$. As you can probably tell from the example the superscript/upper index/exponent you can write using this '^' sign. The subscript uses '_'. For example$2x_1^2 + x_2$is in fact: \$2x_1^2 + x_2\$. If the expression in the super/subscript is more complicated you must use curly brackets. E.g. \$ x^-1\$executes as$ x^-1$, so in order to get$ x^{-1}$you must write \$ x^{-1}\$. The same goes for the subscript. Basic mathematical functions are probably known to MathJax and you can get the right format by writing '\' before the name of the function without any space. So e.g. \$lim\$compiles as$lim$while \$\lim\$is$\lim$. Btw. subscript with limits: \$\lim_{n \to \infty}\$stands for$\lim_{n \to \infty}$. More examples: \$\sin, \cos, \log_a, \sum_{n=1}^\infty \ldots\$is$\sin, \cos, \log_a, \sum_{n=1}^\infty, \int_0^1 \ldots$. If the function isn't know to$\LaTeX$you can write \$\operatorname{sgn}x\$and it will give the 'sgn' proper font and spacing$\operatorname{sgn} x$. When the mathematical object is bigger or longer you can use double dollars instead of single. Then the object will be put in the middle and will be slightly bigger. E.g. \$\$\int_0^1 x_1^2 \;\mathrm{dx}\$\\$ will look like this

$$\int_0^1 x_1^2\; \mathrm{dx}$$

Don't worry about the '\;' it is just space in mathematical mode(also '\,' and '\:') and '\mathrm{dx}' just changes the family font.

Hope that will help you to get into it. Bear in mind, that this is very little, so you will have to learn a lot by yourself. But feel free to ask. Good luck!

This should probably go in Mathematics Meta, but when you make posts on the right side there are 3 links for formatting and MathJaX help.

I don't think there's a formatting guide on Stack Overflow because very rarely do people use math equations, most of the time it's code.


text:
Wikipedia talk:WikiProject Mathematics

 This is a discussion page for WikiProject Mathematics This page is devoted to discussions of issues relating to mathematics articles on Wikipedia. Related discussion pages include: /Conventions /Graphics /PlanetMath Exchange /Proofs /Typography /Wikipedia 1.0 Mathematics Portal MoS Mathematics Reference desk (mathematics) (Please ask general questions of interest here). Please add new topics at the bottom of the page and sign your posts.

A Wikipedia ad has been created for this project page
 edit Archives 2009: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2010: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2011: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2012: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2013: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2014: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2015: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2016: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2017: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2018: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec 2019: Jan · Feb · Mar · Apr · May · Jun · Jul · Aug · Sep · Oct · Nov · Dec

Square root of integers

The problem arose from WP:Articles for deletion/Square root of 10. What to do with the topic now, in light of the deletionist assault? Is a separate article warranted? If no separate, then my proposal, square root #Principal square roots of the positive integers, or something else? Incnis Mrsi (talk) 14:06, 3 September 2019 (UTC)

My knee-jerk reaction was, "This topic is basically (integers in) quadratic number fields, which are extremely important." But then I realized that we have Quadratic field for all that. What is the intended division of labor between the two articles? Is there a substantial body of knowledge specific to quadratic integers? The presence of reliable sources in that article suggests so, but I haven't examined them closely. Mgnbar (talk) 14:23, 3 September 2019 (UTC)
Properties like being Euclidean domain, being principal ideal domains, basis as free abelian group, and many others are more specific to quadratic integer rings than to quadratic fields, even if these properties are described in Quadratic field. D.Lazard (talk) 14:42, 3 September 2019 (UTC)
Integers are important far beyond ℚ[D], if only due to such rings as Gauss ℤ[ i ], Eisenstein ℤ[31], and Dirichlet ℤ[ τ ] which is important for 5-fold rotational symmetry. Incnis Mrsi (talk) 14:51, 3 September 2019 (UTC)
@D.Lazard: what? Isn’t the usefulness of prime factorization to compute many of square roots of integers important? Incnis Mrsi (talk) 14:51, 3 September 2019 (UTC)
The computation of (approximations of) square roots of integers is not very different from that of real number, and belongs thus to Square root. Two things may belong to quadratic integers that are not there in any version: 1/ Computing the largest square-free factor of an integer (that is the smallest d generating a given ${\displaystyle \mathbb {Q} ({\sqrt {d}})}$). For that, no better algorithm is known than prime factorization. So a few lines in Quadratic integer suffices. 2/ Testing whether a quadratic integer is the square of a quadratic number, and, if yes, computing the square root. This is considered in Nested radical and would deserve to be linked here. D.Lazard (talk) 15:36, 3 September 2019 (UTC)
As “not very different from” – false, they are algebraic numbers and “integers”, after all. These facts are completely obscured after D.Lazard’s edits. Incnis Mrsi (talk) 16:06, 3 September 2019 (UTC)
Which edit(s) obscured anything? D.Lazard (talk) 16:54, 3 September 2019 (UTC)
Before the deletionist strike the topic redirected to that subsection. Now one can’t easily infer that square roots of integers are algebraic integers. Nor can the reader access 2, 3, 5, at least not in reasonable proximity of the request. The 10 thing is also removed, but it was not directly a D.’s fault. Incnis Mrsi (talk) 17:11, 3 September 2019 (UTC)
No redirect is needed for saying that the square roots of an integer are quadratic integers. I have added this to Square root. D.Lazard (talk) 18:19, 3 September 2019 (UTC)

What occasion could there be to write "square root of integers" rather than "square roots of integers" or "square root of an integer"? Michael Hardy (talk) 23:51, 4 September 2019 (UTC)

I followed the model of square root of negative numbers. For comparison, Special:PrefixIndex/square roots has nothing of the sort. Incnis Mrsi (talk) 04:44, 5 September 2019 (UTC)
So there exist more useless redirects from grammatically-faulty titles? Interesting, but not a good choice to use as a model. —David Eppstein (talk) 06:01, 5 September 2019 (UTC)
David Eppstein highly probably speaks English better than me by a large margin, hence WP:SOFIXIT. Incnis Mrsi (talk) 06:06, 5 September 2019 (UTC)

Math-related affiliate

Just a reminder about m:Wikimedia Community User Group Math, which any person who supports the group's goals is welcome to join. As of a few weeks ago, the group is one of the officially recognized m:affiliates of the Wikimedia Foundation. Whatamidoing (WMF) (talk) 00:29, 6 September 2019 (UTC)

Articles with links to DAB pages

I have collected another batch of articles containing math(s)-related links to DAB pages which would benefit from expert attention. Search for 'disam' in read mode, and for '{{d' in edit mode; and if you solve one of these puzzles, post {{done}} here.

Thanks in advance, Narky Blert (talk) 02:58, 9 September 2019 (UTC)

I had to edit after a substandard fix in “almost complex manifold”. Please, look at a whole article, not only to narrow context. Don’t make job to earn green points. Incnis Mrsi (talk) 12:52, 9 September 2019 (UTC)
I'm going to stay polite, but please don't ask thanks for this rather aggressive pointing out of a perfectly correct (if maybe not optimal) edit that did not satisfy your opaque standards, and let me add that I have no idea what a green point is nor any desire to learn.
I'd also suggest you refrain from insulting people for petty motives. If you want to discuss math leave a message on the talk page of the article. jraimbau (talk) 11:15, 11 September 2019 (UTC)
The standards aren’t in fact “opaque”, it is MOS:LINKCLARITY. If Jean Raimbault wants to discuss my petty motives, then he can leave a message here, although it can become moot soon. Incnis Mrsi (talk) 11:51, 11 September 2019 (UTC)
Notice that Incnis Mrsi has been blocked for one month by Rschen7754 for incivility. JRSpriggs (talk) 03:06, 12 September 2019 (UTC)
Let us not escalate... Boris Tsirelson (talk) 04:45, 12 September 2019 (UTC)
Thanks for all your help and to Narky Blert for finding the problems. It looks as if the one unfixed link needs a physicist or engineer rather than a mathematician. Certes (talk) 12:22, 11 September 2019 (UTC)
Fixed the last one; it was referring to charge transfer in a CT complex --{{u|Mark viking}} {Talk} 07:37, 12 September 2019 (UTC)
I work on the assumption that mathematicians will be the people best-placed to determine the specific concepts which physicists, engineers, and the like have borrowed and misused.
(I'm an organic chemist. I'm allowed to say that sort of thing.) Narky Blert (talk) 19:37, 13 September 2019 (UTC)
Am engineer. Can agree, borrow and misuse math all the time. --Izno (talk) 20:20, 13 September 2019 (UTC)

Invariants and covariants

There is a problem with the disambiguation required for Michael Roberts (mathematician) in the previous thread: the link to a dab page is clearly intended to refer to covariants of invariant theory. The problem is that I have not found any mention of such a covariant in English Wikepedia. Do someone has an idea for solving the problem?

Here is what I remember on this subject: Let ${\displaystyle f}$ be a generic form in n variables (that is, its coefficients are indeterminates). The group GL(n) acts on the form by linear changes of variables. The discriminant of a form in two variables is an invariant. An invariant of GL(n) (or of a subgroup) is a polynomial in the coefficients of the form. A covariant is a form in the same variables, with coefficients polynomials in the coefficient of the given form, which is similarly invariant. For example, an invariant is a covariant of degree 0.

What precedes is clearly not sufficient, even for a stub. Again, any idea? D.Lazard (talk) 18:22, 9 September 2019 (UTC)

This is in fact about covariant transformations, or I miss something? Forms are tensors of special form. Incnis Mrsi (talk) 18:39, 9 September 2019 (UTC)
One possibility is to replace the phrase "covariants and invariants" with the phrase "invariant theory". (If there were a reference attached to this statement in the article then I would worry about accurately representing it, but since there is none ....) Also pinging the article author to this discussion; possibly they can share some insight. --JBL (talk) 19:05, 9 September 2019 (UTC)
We do have the article “module of covariants”. — Taku (talk) 04:45, 10 September 2019 (UTC)
I have found two definitions of a covariant; one in Invariant of a binary form, and one in wikt:covariant, which is more general (not restricted to binary forms) and perfectly accurate. Therefore, I have created the redirect Covariant (invariant theory), I have disambiguated Michael Roberts (mathematician) by using this redirect, and added an entry in Covariance (disambiguation), that links to the redirect and contains a copy of dictionary definition. However, some questions deserve a further discussion;
• The new redirect is the only occurrence of the noun "covariant" in the dab page. This suggest creating a stub based on Wiktionary definition, called Covariant, and with a hatnote like "for the adjective uses, see Covariance (disambiguation)". What do you think?
• The fact that it vas so difficult to find this definition shows that a reorganization is needed for interlinking Invariant theory and all related articles. When this will be correctly done, it will probably appear that Invariant theory would need a complete rewrite, with possibly some merges and or splits.
D.Lazard (talk) 09:43, 10 September 2019 (UTC)
We already have definitions in a glossary; Glossary_of_invariant_theory has 42 uses of the term and and entry for covariant. --{{u|Mark viking}} {Talk} 17:27, 10 September 2019 (UTC)
The problem is that the definition given there is not understandable for most readers, and does not correspond to the usual definition (that of wikt:covariant and Invariant of a binary form). D.Lazard (talk) 18:10, 10 September 2019 (UTC)
I wouldn’t call a subminimal stub an article. See talk:Module_of_covariants #AG. Incnis Mrsi (talk) 18:20, 10 September 2019 (UTC)
(I have added an explanation on the notation as well as to a link to the article giving the definition. -- Taku (talk) 00:19, 11 September 2019 (UTC))
If I've opened up a smallish can of worms, I'm delighted. WP is full of holes where readers can't find easily, or can't find exactly, what they need, and every one filled is an improvement. Narky Blert (talk) 21:17, 10 September 2019 (UTC)
• First, as I recall, a covariant is something like a linear (multi-linear, polynomial) map that is invariant under the given group action. The basic idea is that you get more flexibility by working with maps not elements; i.e., you get more invariants to work with. (Module of covariants, I think, gives probably the most general definition of covariants.) So, given this, I don’t think redirecting covariant (invariant theory) to an invariant of a binary form is a good idea. I will make a library trip to find some refers (and do some edits).
• Generally speaking, Wikipedia is still weak in invariant theory topics (I don’t need to tell you why).
• Finally, yes, there is adjective “covariant” as in “covariant functor” and that has to be distinguished from. (So the disambig page is needed). — Taku (talk) 23:09, 10 September 2019 (UTC)
Thank you to JBL for pinging me. I am happy with what Taku says. Moonraker (talk) 21:43, 12 September 2019 (UTC)

Using a book that plagiarized Wikipedia as a Wikipedia source?

I've been editing trigonometry to address some of the problems it had in its GA review. In particular, much of it was unsourced or OR. I've been going through and deleting unsourced assertions and adding sources to everything else.

There was a section marked with 'more sources needed'. This sections was the 'applications' section, which has largely been unchanged since at least 2007: https://en.wikipedia.org/w/index.php?title=Trigonometry&oldid=122379664

I was going through and sourcing each 'application' one at a time, when I found a book that had all of them:

This is a Springer book where the authors have just copied and pasted the Wikipedia section, rearranging a few items.

I'm not too concerned that the authors have plagiarized this. My real question, though, is, would it be appropriate to use this book as a source for the whole list (as I've done for now), or would it be better to find sources that aren't plagiarized from Wikipedia itself?

Brirush (talk) 19:33, 12 September 2019 (UTC)

I think it's definitely better not to use sources that plagiarized from Wikipedia (or from elsewhere). XOR'easter (talk) 20:17, 12 September 2019 (UTC)
More definitively, Wikipedia policy prohibits using such sources. See WP:CIRCULAR. (Their preface credits Wikipedia, so this might count as properly-credited use of CC materials rather than straight-up plagiarism, but it makes no difference for its usability as a source.) —David Eppstein (talk) 20:18, 12 September 2019 (UTC)
It may also be worth adding {{Backwards copy}} to the articles, to prevent them being flagged as copy violation by Wikipedia. Certes (talk) 20:24, 12 September 2019 (UTC)
Thanks to both of you, this is very clear. Brirush (talk) 01:37, 13 September 2019 (UTC)

What should an article for a branch of mathematics look like?

As I mentioned above, I've been reworking Trigonometry, focusing on organization and on removing OR and adding sources.

The page still looks skimpy, however, and I feel that more could be added (maybe separate sections on the properties of the graphs, on inverse functions, and perhaps fourier series/analysis?). I've been looking at other pages for inspiration, but I found to my surprise that no 'branch of mathematics' is currently a GA or a FA. Algebra, calculus, etc. are all below GA quality, and have some of the same problems that trigonometry has.

So I wanted to get some consensus before acting. What should 'big topic' articles like this cover? Is there any thing that you feel is necessary or standard for such articles? Is there any particularly good article in a related field that could be used as a template or inspiration? Brirush (talk) 02:42, 13 September 2019 (UTC)

You raise good questions. I think it is quite a challenge to be comprehensive, readable by non-experts and a reasonable length all at once for articles on general topics. One general article I like is Field (mathematics). It takes pains to be readable and concrete near the start of the article, but doesn't shy away from the more advanced topics later on. For trig, some ideas: I guess one of the first things to do is to figure out what goes in trigonometry and what goes in trigonometric functions. One might compare and contrast trigonometry, which is really about plane trigonometry, with spherical trigonometry, hyperbolic trigonometry and generalized trigonometry. Is there anything interesting about how trig has been or is currently taught? For applications, something more than just a long list of fields that use it might be good. Are there some particularly notable uses, maybe something from navigation or surveying? --{{u|Mark viking}} {Talk} 03:52, 13 September 2019 (UTC)
A detailed history section is a major plus! Edit: I see that trigonometry actually has a fairly well-developed one, with just a few citations that need to be added. — MarkH21 (talk) 07:03, 13 September 2019 (UTC)
Thanks for the work already done on Trigonometry. I completely agree with Mark viking's comments. A large part of my Wikipedia activity is devoted to improve in this way fundamental articles of Wikipedia (See my user talk for some of my main edits). IMO, we must distinguish articles about an area of mathematics, such as Trigonometry from articles about the fundamental concept(s) that are the basis of such an area, such as Trigonometric functions. Articles on areas must explain the motivations, the history, the limits of the area (when there is a consensus for that), and the relations with other areas. The objective is that a reader can gets an idea of the subject and find easily the related technical articles that he may need. An example of a very good such article is Number theory, although it needs many improvements (cosmetic, IMO) for being labeled GA. On the other hand, article on fundamental concepts must allow the reader to find the technical details that he needs, such as a formula that he has learnt and forgiven, or a related concept that he has heard about. This is in this spirit that I have recently edited Trigonometric functions (see [1]). In particular, other trigonometric functions than sine, cosine, and tangent are rarely used, except, maybe, in teaching; therefore, my edits limit the formulas given in the article to the most useful formulas relating sine, cosine, and tangent and refer to List of trigonometric identities for the less important formulas. However, the maintenance of such fundamental articles is a true problem, because of the numerous good faith editors who want to add their preferred minor aspect of the subject. For example, since my edits, a section on the expansion of trigonometric functions as infinite products has been added. IMO, such a section is confusing, and must be replaced by a simple link, as it gives too much emphasis on a non-fundamental result. D.Lazard (talk) 09:45, 13 September 2019 (UTC)
At the risk of putting words into D.Lazard's mouth, let me say it another way. Mathematical concepts have precise definitions. For example, a topology is a set of subsets satisfying certain axioms. However, mathematical disciplines are ill-defined and overlapping. For example, the discipline of topology heavily overlaps with geometry, analysis, algebra, etc. And Wikipedia should explain both concepts and disciplines. Mgnbar (talk) 12:16, 13 September 2019 (UTC)
I completely agree, and what I was saying is that rules for a good article (answer to the question in the heading) are different for disciplines and for concepts. D.Lazard (talk) 12:23, 13 September 2019 (UTC)
Agreed. And the citation process for the two is a bit different. For the concept of topology, one can cite the definition from Munkres' book Topology. For the discipline of topology, which topics can be included and excluded? If a topic appears in Munkres' Topology, then one can reasonably include it. If a topic does not appear, then one cannot reasonably exclude it. (The same problem exists for other sources and for combinations of sources.) So the discipline of topology has to be "defined" using examples. Mgnbar (talk) 16:34, 13 September 2019 (UTC)
This is maybe a bit of a quibble, but I don't think "concept" is the right word for topology in the sense of a collection of open sets, at least to distinguish it from topology as a discipline. Topology as a discipline is arguably still a concept. I think a better word would be "object" — the collection of open sets notion is a type of mathematical object, whereas the discipline is not (and indeed has no precise mathematical definition at all). --Trovatore (talk) 19:56, 13 September 2019 (UTC)

I've now completed my revision of Trigonometry. In the process, I've added several figures and tables, and almost doubled the size of the entry. I've tried to be careful and check for errors, but I would appreciate it if someone would look it over for mistakes, especially stray sentences from copy-and-paste or errors in the tables. If you feel any additions or removals are inappropriate, I can revert them. Thanks for the advice given above, it was extremely helpful.

Edit: The article itself isn't complete. As mentioned by someone else, it could use an overview of spherical/hyperbolic geometry. I'm not too familiar with spherical trigonometry, so I didn't attempt it.

Brirush (talk) 19:43, 13 September 2019 (UTC)

Trovatore: Topology is a class of mathematical objects, and topology (the discipline) is a sociological/anthropological object? Actually, I don't have strong opinions about the terminology. :) Mgnbar (talk) 20:44, 13 September 2019 (UTC)
I find that a useful proxy is whether you use a countable or uncountable noun. A topology (count noun) is a mathematical object, whereas topology (mass noun) is a discipline.
This is by the way the distinction we should use for a Boolean algebra (count noun, the structure) versus Boolean algebra (mass noun, the equational style). I fought the good fight on that point many years ago, with a somewhat unsatisfactory outcome, because of a participant with unusual foundational views. --Trovatore (talk) 21:29, 13 September 2019 (UTC)

The page numbers in a lot of the references in trigonometry are given as the first half of a range. Surely this doesn't mean that the entire rest of the book after that page number is the relevant part. Would ff. work better? XOR'easter (talk) 18:40, 14 September 2019 (UTC)

Thank you, I was using https://reftag.appspot.com/ to convert google book links to Wikipedia citations. It had a few other idiosyncracies that I had to address (like using a non-existent 'coauthors' tag). I'll see if I can convert the page ranges to ff's! Brirush (talk) 22:53, 14 September 2019 (UTC)
Okay, I fixed it. I did not use ff after all, because I didn't realize it meant 'multiple pages', and when I found references, my technique was to find the exact page that had the quote I wanted, so it shouldn't need the subsequent pages. I changed it to single pages. Brirush (talk) 23:03, 14 September 2019 (UTC)
Thanks! I did some spot-checking and fixed a couple other glitches that were probably due to Google Books metadata weirdness. I'll try to check the page over more thoroughly soon. XOR'easter (talk) 23:58, 14 September 2019 (UTC)

Minkowski fractal

(for context)
Image from "Fractal antenna"
Image from "Vicsek fractal"

There are currently redirects from Minkowski curve, Minkowski island, Minkowski sausage, and Minkowski fractal which lead to the article "Fractal antenna". An image given as an example of a fractal antenna design is labelled as a "Minkowski Island". Currently the term is in bold because the redirects indicate that it is a topic. However, an article about a subspecies of doves should probably redirect to an article about doves and not to an article about bird-shaped objects. It would be beneficial if an appropriate article was created to explain the Minkowski fractal, or if the redirects led to an article which explained the Minkowski fractal. The image is titled File:6452553 Vicsek Fractal Antenna.png, which implies that "Minkowski island" is an alternate name for the Vicsek fractal. "Vicsek fractal" does mention that the boundary is a variant of the Koch snowflake, and the "Koch snowflake" article contains a quadratic variant of the Koch curve labelled as the 'Minkowski Sausage', so one or both of the articles "Vicsek fractal" and "Koch snowflake" should probably contain the explanation. Hyacinth (talk) 04:08, 14 September 2019 (UTC)

Regarding the mathematics banner of the Category:Ordinal numbers

See Category talk:Ordinal numbers. Chongkian (talk · contribs) removed the {{Maths banner}}. Apparently, he believes that {{WikiProject Numbers}} is sufficient. Is that appropriate?

I think that ordinals are relevant to Mathematics generally, not merely to the Numbers project. JRSpriggs (talk) 05:34, 15 September 2019 (UTC)

Sure! I've restored WPM there. Boris Tsirelson (talk) 09:21, 15 September 2019 (UTC)
From what I have found, generally there are WikiProject Mathematics ('math banner' or 'math rating'), WikiProject Statistics and WikiProject Numbers which are highly inter-related to each other. Whenever it is related to math in general, we shall use math banner or math rating, but if it is a more specific term of math (which is number or statistics), isnt that we should related it to its more 'specific' WikiProject category? 'Numbers' and 'statistics' are (and always be part of) 'mathematics'. That's the idea behind it for my reason. Same case like 'country', 'geography' or 'city'; 'geography' (or WikiProject Geography) shall be the default categorization first for all of administrative divisions (e.g. town, village, state, province), unless such particular article is about a country or city, then we shall put it under WikiProject Countries or WikiProject Cities respectively (because such WikiProjects do exist), and take out the 'parent' WikiProject which is WikiProject Geography. Villages shall be put under the general WikiProject Geography because up to this moment, there is no WikiProject Villages. Chongkian (talk) 10:03, 15 September 2019 (UTC)
It’s worth noting that WikiProject Numbers is only semi-active now. Also, statistics isn’t universally considered a branch of mathematics. — MarkH21 (talk) 10:18, 15 September 2019 (UTC)
Looking at WikiProject Numbers I fail to find there any interest to transfinite numbers. Thus, I'd say, it is THEIR decision, to treat "number" as "finite number". I just respect their (quite reasonable) decision. Boris Tsirelson (talk) 10:30, 15 September 2019 (UTC)
WikiProject Numbers has been concentrating on articles about integers by removing cruft (77 is the shirt number of Joe Minor-Leaguer), improving navigation templates and promoting their existence. Three years ago, 1 was the title of the article about the year AD 1. Certes (talk) 11:37, 15 September 2019 (UTC)
As a moderately active member of both projects, I don't remember any discussion of infinite numbers in the WikiProject Numbers page or notability guidelines. I don't believe 0.999... is tagged with WikiProject Numbers. — Arthur Rubin (talk) 17:30, 15 September 2019 (UTC)
The usual practice with project banners is to use all applicable ones, not to try to decide which is most applicable and use only that. —David Eppstein (talk) 17:56, 15 September 2019 (UTC)
I don't think WikiProject Numbers wants Ordinal number. As a fairly active member of both WPM and WPN, I don't think the charter of WPN includes infinite numbers. — Arthur Rubin (talk) 17:55, 16 September 2019 (UTC)
To Arthur: Then remove {{WikiProject Numbers}} from Category talk:Ordinal numbers and Category talk:Cardinal numbers. I do not feel qualified to do that since I am not a member of the numbers project. JRSpriggs (talk) 09:45, 17 September 2019 (UTC)

Hilbert's fourth problem article

Hi! The second sentence in this article in its current form seems to be somewhat mangled for me.

In one statement derived from the original, it was to find up to an isomorphism all geometries whose axioms system of the classical geometry (Euclidean, Hyperbolic and elliptic) if we drop the axioms of congruence involving the concept of the angle and add the systems with the triangle inequality' regarded as an axiom.

Maybe this rewriting could be adequate:

In one statement derived from the original, it was to find up to an isomorphism all geometries that have an axiomatic system of classical geometry (Euclidean, Hyperbolic and elliptic), with those axioms of congruence that involve the concept of the angle dropped, and triangle inequality', regarded as an axiom, added.

As I am not a professional, I would like to have an expert opinion before editing the article. Thank you in advance! --94.21.201.110 (talk) 11:17, 17 September 2019 (UTC)

Courtesy link: Hilbert's fourth problem. That is, indeed, incomprehensible. It used to be different, before a spate of edits by Vlasenko D in June. Probably those edits deserve some scrutiny (for English language usage at a minimum). --JBL (talk) 12:00, 17 September 2019 (UTC)
I agree. At least, the old version of the lead deserves to be immediately restored, although it could also be clarified. D.Lazard (talk) 13:49, 17 September 2019 (UTC)

Just why the initial letter in "hyperbolic" should be capital while that in "elliptic" is in lower case is unclear. Or to put it more bluntly, it shouldn't be. Michael Hardy (talk) 21:46, 18 September 2019 (UTC)

Draft:Direct discontinuous Galerkin method

Is this an original research or something in mainstream? I’m inclined to the former (and thus the deletion on the ground), but wondering what other editors think. —- Taku (talk) 23:18, 18 September 2019 (UTC)

The sources look legit and don't appear to be languishing in citation obscurity, and the SIAM one is ten years old. It looks like we could have an article, or at least a section of an article, on the topic, but the existing draft text would need serious editing before it could be called ready. Compare its prose with Discontinuous Galerkin method. XOR'easter (talk) 01:17, 21 September 2019 (UTC)

Pull the knotted part of the curve tight?

This discussion calls for experts, right? Boris Tsirelson (talk) 18:49, 19 September 2019 (UTC)

No, I don't think so: in the 2 years since the first comments were made, the caption has been changed and now does not suffer from the problem discussed there. --JBL (talk) 19:28, 19 September 2019 (UTC)
I see, thank you. Boris Tsirelson (talk) 19:49, 19 September 2019 (UTC)
(I agree with your comment there, incidentally -- Daqu was right about the error, the most recent comment looks wrong. But it is all moot as far as the article is concerned.) --JBL (talk) 20:47, 19 September 2019 (UTC)
Do you not need to require that the first (directional) derivative of the curve be continuous? I think that would be impossible if you just shrink it to a point. JRSpriggs (talk) 07:55, 20 September 2019 (UTC)
Feel free to find a verifiable source supporting your claims, if I am not to be considered as an expert. Quantum Knot (talk) 08:32, 20 September 2019 (UTC)
(to Quantum Knot) Such sources surely exist; can someone help to find them?
For now I've found this: This turns out to not be the correct notion of equivalence for knots - it would force all tame knots to be equivalent!. Boris Tsirelson (talk) 10:13, 20 September 2019 (UTC)
And this: For ${\displaystyle m-n\leq 2}$ this is not so: e.g., any knot ${\displaystyle S^{1}\to \mathbb {R} ^{3}}$ is PL isotopic to the unknot, but is not necessarily PL ambient isotopic to the unknot. Boris Tsirelson (talk) 10:24, 20 September 2019 (UTC)
And this: Secondly, surprisingly (and catastrophically), the way we have defined equivalence actually causes all knots to be equivalent to one another! “Gradually pulling the string tight” so that the knot shrinks to a point is a perfectly good continuous deformation between any knot and the unknot! Boris Tsirelson (talk) 11:30, 20 September 2019 (UTC)
And this: The word "isotopy " refers to the deformation of the string. The word "ambient" refers to the fact that the string is being deformed through the three-dimensional space that it sits in. Note that in an ambient isotopy, we are not allowed to shrink a part of the knot down to a point, as in Figure 1.20, in order to be rid of the knot. (page 120) Boris Tsirelson (talk) 11:45, 20 September 2019 (UTC)
And this: Remark 1.5. All knots are trivial under continuous isotopy. (batchelor’s unknotting) Boris Tsirelson (talk) 11:52, 20 September 2019 (UTC)
Wow! The clue is the phrase "batchelor’s unknotting" (or "batchelor’s isotopy")! Google this, and you'll find easily a lot of required sources. So, I stop here; the problem is solved. (Should we create an article on this idea?) Boris Tsirelson (talk) 11:57, 20 September 2019 (UTC)
(to JRSpriggs) Sure, if we work in the space ${\displaystyle \mathrm {Emb} ^{1}(S^{1},\mathbb {R} ^{3})}$ of continuously differentiable embeddings, then the situation should be different. But differentiability is never mentioned in "Homotopy". Boris Tsirelson (talk) 10:02, 20 September 2019 (UTC)
Maybe "bachelor" rather than "batchelor"? Justin Roberts's discussion (your third link) is very nice. A less rigorous, more sociological explanation for why continuous deformations are the wrong idea is that no one would ever have introduced ambient isotopies into knot theory if continuous deformations sufficed. --JBL (talk) 20:13, 20 September 2019 (UTC)
I haven't tracked down an explicit reference, but this seems likely to be named after G. K. Batchelor, who studied knotted vortices in fluid dynamics. —David Eppstein (talk) 21:00, 20 September 2019 (UTC)


text:
# Fast Inverse Square Root

This is a classic hack in the graphics community. It is not optimal on modern hardware, but is still useful for some smaller systems. This hack has been in use since the 70s.

Here's an example from the Quake3 source code:

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;                       // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

return y;
}

In order to understand this hack, three things need to be reviewed:

1. The effect of basic operations on numbers and binary patterns
2. The structure of the floating point binary format
3. Newton's method for finding roots

## Basic operations

Exponent multiplication works like this: $$2^x \times 2^y = 2^{xy}$$

Shifts in binary work as the do in decimal. In decimal: $$23 \times 10 = 230$$ $$23 << 1 = 230$$

In binary: $$0101_2 \times 2 = 1010_2$$ $$0101_2 << 1 = 1010_2$$

## Floating point format

We will only consider single precision IEEE-754 floating point for this problem. Floats are 32 bits long and have this form:

 1    8               23
|-|--------|-----------------------|
s    E               M

Where $$s$$ is the sign, with 0 for positive and 1 for negative. $$E$$ is the exponent, with a bias of 127. Sometimes the exponent is written as $$e$$ without the bias, so $$e = E-127$$. $$M$$ is the mantissa, with an implied leading 1. The mantissa can have a leading 0 in some special cases, which we will ignore. So the basic formula for computing a float value is: $$f = -1^s \times 1.M \times 2^{E-127}$$

## A simple version

A less optimized and simpler version of the trick is:

float inverseSqrt( float number )
{
float est;
const float one = 1.0f;
int i = *(int*)&one;
i = i + (i >> 1);
i = i - *(int*)&number;
est = *(float*)&i;
return est;
}

This is based on Blinn's write up (see references). This one works by dividing the exponent by 2. A bitwise right shift should normally do this, but since the exponent field is biassed, it takes more.

The number 1 has a exponent of 0 and a mantissa of 0. So, the biassed exponent for 1 is 127. By adding the 1's exponent to its right shifted value, it approximates an E value of 190 (with some error in the mantissa): $$E = 127 + (127>>1)$$

The input value has an exponent bias of 127 and while shifting it divides the exponent by two (resulting in the square root), it leaves a bias of 63. So, subtracting the shifted input exponent removes the extra 63 from the shifted one exponent, leaving a bias of 127 and the negative shifted input exponent.

There is now some error data in the mantissa from the shift, but the exponent should be the original exponent negated and divided by two: the inverse square root with a bit of error.

## Newton's method

Newton's method is an algorithm for finding roots (solutions to equations). Newton's method is: $$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

That is, given an estimated solution to a function $$f$$ ($$x_0$$), a better solution can be found by following the slope of the tangent (derivative) back towards the x-axis.

# Using Newton's method

So, given the function we wish to solve is $$\frac{1}{\sqrt{x}}$$, we will need to estimate a value, then use Newton's method to improve the value. However, instead of using $$\frac{1}{\sqrt{x}}$$, we will instead use Newton's method on a function that represents the error of our guess and $$\frac{1}{\sqrt{x}}$$. That is, when this error function reaches 0, we have the exact solution to the inverse square root. So, we will use Newton's method to find values that minimize the result.

Since the inverse square root is: $$\frac{1}{\sqrt{x}}$$ Given an initial value of $$x$$ and a very good guess $$y$$, then this could be true: $$y = \frac{1}{\sqrt{x}}$$ However, since $$y$$ is an estimate it will more likely be: $$y \approx \frac{1}{\sqrt{x}}$$

Given this, we wish to minimize the error between the initial value $$x$$ and the guess $$y$$. The relation between our guess is: $$\frac{1}{y^2} = x$$

The error between the guess and the actual value is then: $$\epsilon = \frac{1}{y^2} - x$$ or $$\epsilon = y^{-2} - x$$

If the error was 0, then $$y$$ would be the exact answer. Using Newton's method, the error can be minimized: $$y_1 = y - \frac{\epsilon(y)}{\epsilon'(y)}$$

The derivative of the error is: $$\epsilon'(y) = -2y^{-3}$$

Newton's method becomes:

$$y_1 = y - \frac{y^{-2} - x}{-2y^{-3}} \$$ $$y_1 = y - (y^{-2} - x)(-\frac{1}{2}y^{3}) \$$ $$y_1 = y - (-\frac{1}{2})(y - xy^{3}) \$$ $$y_1 = y - (-\frac{1}{2}y + \frac{1}{2}xy^{3}) \$$ $$y_1 = y + \frac{1}{2}y - \frac{1}{2}xy^{3} \$$ $$y_1 = \frac{3}{2}y - \frac{1}{2}xy^{3} \$$ $$y_1 = 1.5y - 0.5xy^{3} \$$ $$y_1 = y(1.5 - 0.5xy^{2}) \$$

This is the last lines of the code:

y  = y * ( threehalfs - ( x2 * y * y ) );

# The exponent

Since the value of the float is $$f = -1^s \times 1.M \times 2^{E-127}$$

and we are trying to approximate $$y = \frac{1}{\sqrt{x}}$$

we can assume that $$x$$ is positive and the estimate becomes: $$y = \frac{1}{\sqrt{x}} = \frac{1}{\sqrt{1.M}} \times 2^\frac{1}{\sqrt{e}}$$ or $$y = \frac{1}{\sqrt{1.M}} \times 2^{\frac{-e}{2}}$$

The exponent has a bias of 127, so the actual exponent value is $$E = -e/2 + 127$$

We wish to divide the original exponent by 2 and negate it, but still retain the bias. This can be done in integer math as:

newE = (0 - ((E-127) >> 1)) + 127

newE = 0 - ((E >> 1)-(127 >> 1)) + 127

newE = 0 - (E >> 1) + 63 + 127

newE = 190 - (E >> 1)

or

0xbe - (E >> 1)

This works because E already has a bias of 127, so shifting by 2 divides the bias to 63. Then, subtracting the 63 results in a final bias of 127. The $$e$$ part of the exponent is thus shifted (divided by 2) and still biased correctly.

# The mantissa

Since there is a bitwise shift, some bits of the exponent might end up in the mantissa. There are two cases to consider with the exponent $$E$$ of the input value: it can be odd or even. If the $$E$$ is even, no new bits will be shifted into the mantissa. This is the only case we will consider. The odd case is similar, but longer and more complex, so see the references.

If $$E$$ is even, the $$e$$ must be odd because: $$e = E - 127$$

$$e$$ can then be written as $$2d+1$$. The guess float values can be written as $$E_g$$ and $$M_g$$. Then, since the estimate will subtract the shifted initial value: $$y = (1+M_g - M/2)2^{E_g - 190 - d}$$

Since the original exponent will be shifted and has a bias of 127, it will retain a bias of 63. If the guess float values are written as $$E_g$$ and $$M_g$$, the estimate can be written as: $$y = (1+M_g - M/2)2^{E_g - 190 - d}$$ Moving a two from the exponent to the mantissa: $$y = (2+2M_g - M)^{E_g - 191 - d}$$

If $$M/2 > M_g$$, then the mantissa will borrow from the exponent, increasing the mantissa by one and dividing the exponent by two, resulting in: $$y = (1 + (1+M_g - M/2))2^{E_g - 190 - d -1}$$ $$y = (2+M_g - M/2)2^{E_g - 191 - d}$$

There are then two possible results for the mantissa estimate: $$2M_g - M \: \text{:} \: E is even, M_g \geq M/2\$$ $$M_g - M/2 \: \text{:} \: E is even, M_g < M/2$$

Similarly, there are two results for the odd case: $$4M_g - M \: \text{:} \: E is odd, M_g \geq M/2\$$ $$1 + 2M_g - M \: \text{:} \: E is odd, M_g < M/2$$

These functions represent estimates for the inverse square root. Given appropriate guesses for $$M_g$$ and $$E_g$$, they form a piecewise linear function that approximates the inverse square root curve. For the classic constant value, one of the cases can never occur, resulting in a three-part function.

Eberly plots it as:

While the classic exponent can be derived, no one knows how the classic mantissa was derived. Lomont approximates it by minimizing the maximum error along the piecewise function. Minimizing this error over the function means optimizing nine possible cases.

Lomont shows the $$M_g$$ error as:

Note that the error is smallest near 0.45. If the E part of 0x5f3759df is set to 127, the result will be $$1.M$$. The constant 0x3fb759df does this, which shows the mantissa have a value of 0.432430.

Better guesses for a constant have been computed and they are close to the classic estimate. The actual source or method that generated the classic constant is not known.

# Example code

Here's a small program for testing the method. It will also time various inverse square root methods. On modern PCs, the standard floating point calculation is probably faster. The number of Newton iterations greatly impacts performance of the estimate calculations, so experiment with those and decide if the accuracy is worth the cost in the integer hacks.


text:
# Cycle permutation problem

• March 13th 2013, 12:31 PM
DonnieDarko
Cycle permutation problem
Hello there. I have this two cycle permutation problems to prove,

1. $\left ( a b \right )^{-1} = \left ( a b \right )$

2. $(1,2,3, .... ,n)^{-1} = (n,n-1, ... ,2,1)$

Any idea?
• March 13th 2013, 06:22 PM
Nehushtan
Re: Cycle permutation problem
#1. What is $(a\ b)(a\ b)$?

#2. Use #1 and induction. (Note: $(1\ 2\ \cdots\ n\ n+1)=(1\ n+1)(1\ 2\ \cdots\ n)$.)
• March 14th 2013, 12:31 PM
DonnieDarko
Re: Cycle permutation problem
Quote:

Originally Posted by Nehushtan
#1. What is $(a\ b)(a\ b)$?

#2. Use #1 and induction. (Note: $(1\ 2\ \cdots\ n\ n+1)=(1\ n+1)(1\ 2\ \cdots\ n)$.)

1. It is decomposition into disjoint cycle?
2. I tried to solve it like this.
$\tau = (a_{1} a_{2} ... a_{n} )$
$\tau(a_{i})=a_{i+1}$
$\tau^{-1}(a_{i+1})=a_{i}$
$\tau: a_{1} \mapsto a_{2} \mapsto ...\mapsto a_{n}$
$\tau^{-1}: a_{n} \mapsto a_{n-1} \mapsto ...\mapsto a_{1}$
- Its obvious that tau^(-1), is just tau written in reverse.


text:
# Which of the following problems is undecidable ?

This question was previously asked in
UGC NET Paper 3: Computer Science Nov 2017 Official Paper
View all UGC NET Papers >
1. To determine if two finite automata are equivalent
2. Membership problem for context free grammar
3. Finiteness problem for finite automata
4. Ambiguity problem for context free grammar

Option 4 : Ambiguity problem for context free grammar
Free
IBPS SO IT Officer Mains: Full Mock Test
5824
60 Questions 60 Marks 45 Mins

## Detailed Solution

The correct answer is option 4:

EXPLANATION

Option 1: Decidable

Minimize both finite automata if both are the same having automata then both are equivalent and hence to determine if two finite automata are equivalent is decidable

Option 2: Decidable

For the context-free language, we have a CYK algorithm for membership problem, so it is decidable

Option 3: Decidable

There is an algorithm for the finiteness problem

ALGORITHM:

Step1: delete states which are not reachable from the initial state and corresponding transitions.

Step 2: delete states and corresponding transitions which are not reachable to the final state.

Step 3: In remaining finite automata, if we find at least one loop and one final state then it is accepting infinite language.

so the finiteness problem is decidable

Option 4: Undecidable

Decidable there is no algorithm for finding ambiguity in grammar, so ambiguity is undecidable.


text:
# Functions

In each function there are two variables like $x$ and $y$. One of them can be selected as independent variable arbitrary (in this book $x$), then the other one is function variable or dependent variable. While independent variable changes, dependent variable changes according to the function rule, too.

Definition:
Let $A$ and $B$ are two sets and $f$ be a subset of Cartesian product of $A \times B$. $f$ is a function if and only if
$(x,y_1) \in f \,\,,\,\, (x,y_2) \in f \longrightarrow y_1=y_2$
In other words $f$ is a subset of pairs of $A \times B$ such that there aren't two different pairs with same first components.

Example:
Let $A= \lbrace 1,3,7 \rbrace$ and $B=\lbrace -2,0 \rbrace$. Cartesian product of $A\times B$ is equal to
$A \times B = \lbrace (1,-2),(1,0),(3,-2),(3,0),(7,-2),(7,0) \rbrace$
Also let $f=\lbrace (1,0),(3,-2),(7,-2) \rbrace$.
$f$ is a subset of $A \times B$ and also it is a function, because there aren't two different pairs with same first components.

Example:
In the below figure $f$ is a function from $A$ to $B$.
Notice that $f=\lbrace (1,11),(-2,\pi),(5,\pi) \rbrace$

Example:
In the below figure $g$ is NOT a function from $A$ to $B$.
Notice that $g=\lbrace (-1,\dfrac{1}{7}),(-1,\sqrt{2}),(0,\dfrac{1}{7}),(4,\sqrt{2}) \rbrace$

Example:
Is $R=\lbrace (\sqrt{2}-1,4),(\dfrac{1}{\sqrt{2}+1},5),(3,6),(\dfrac{1}{2-\sqrt{3}},1),(2+\sqrt{3},1)\rbrace$ a function? If no find subsets of $R$ which are functions and each one consists of three pairs.
Solution:
First of all notice that
$\dfrac{1}{\sqrt{2}+1}=\dfrac{1}{\sqrt{2}+1} \times \dfrac{\sqrt{2}-1}{\sqrt{2}-1}=\dfrac{\sqrt{2}-1}{2-1}=\sqrt{2}-1$

$\dfrac{1}{2-\sqrt{3}}=\dfrac{1}{2-\sqrt{3}} \times \dfrac{2+\sqrt{3}}{2+\sqrt{3}}=\dfrac{2+\sqrt{3}}{4-3}=2+\sqrt{3}$
So $R$ can be rewritten as below
$R=\lbrace(\sqrt{2}-1,4),(\sqrt{2}-1,5),(3,6),(2+\sqrt{3},1) \rbrace$
which is not a function.
Now put
$f_1=\lbrace (\sqrt{2}-1,4),(3,6),(2+\sqrt{3},1) \rbrace$

$f_2= \lbrace (\sqrt{2}-1,5),(3,6),(2+\sqrt{3},1) \rbrace$
$f_1$ and $f_2$ are obviously two subsets of $R$ which are functions.

Example:
If $R=\lbrace (3,m-5),(-1,m),(2,m^2),(3,8) \rbrace$ is a function, then what's the value of $m$?
Solution:

$(3,m-5)=(3,8) \rightarrow m-5=8 \rightarrow m=13$
It is clear that
$R=\lbrace (3,8),(-1,13),(2,169) \rbrace$

Example:
If $f=\lbrace(a^2-2a,3),(3,3),(-1,4),(a,3) \rbrace$ is a function, then what's the value of $a$?
Solution:
$(a^2-2a,3)=(3,3) \rightarrow a^2-2a=3 \rightarrow a^2-2a-3=0 \rightarrow a=-1 \,\,,\,\, a=3$
Notice if $a=-1$ then $f=\lbrace(3,3),(-1,4),(-1,3) \rbrace$, which is not a function.
Therefore $a=-1$ is not acceptable. So $a=3$ and $f=\lbrace (3,3),(-1,4) \rbrace$

Example:
Prove that $f(x)=x^3-2$ is a function.
Solution:
According to the definition of a function, one should prove that if $x_1=x_2$, then $y_1=y_2$. So
$x_1=x_2 \rightarrow x_1 ^3=x_2 ^3 \rightarrow x_1 ^3 -2 =x_2 ^3 -2 \rightarrow y_1=y_2$
Therefore $f$ is a function.

Example:
Prove that $x^2+y^2=4$ is NOT a function.
Solution:
$x^2+y^2=4 \rightarrow y^2=4-x^2$
Now
$x_1=x_2 \rightarrow x_1 ^2= x_2 ^2 \rightarrow -x_1 ^2=-x_2 ^2 \rightarrow 4-x_1 ^2=4-x_2 ^2 \rightarrow y_1 ^2= y_2 ^2 \rightarrow y_1 = \pm y_2$
Therefore it isn't a function.

Tip:
$(x - \alpha)^2 + (y - \beta)^2 = R^2$
is standard form for the equation of a circle. Notice that $(\alpha,\beta)$ is the center of the circle and $R$ is its radius.

#### Exercises

1.Which figure is a function?
2. If $f=\lbrace (a,3),(1,-3),(2a+4,3) \rbrace$ is a function, then what's the value of $a$?

3. If $f=\lbrace (a+b,2),(a^2-2,3),(a^2-2a,3),(3,2) \rbrace$ is a function, then what's the value of $a+b$?

4. If $f=\lbrace (7,11),(a^-6a,11),(a,4) \rbrace$ is a function, then what's the value of $a$?

5. If $f=\lbrace (3,2),(a-b,2),(2a+b,4),(2b,4),(1,\sqrt{2}),(-2,3) \rbrace$ is a function, then what's the value of $(f(a))^2+f(b)$?

6. Prove that $y=2|x|+3x-4$ is a function.

7. Prove that $|y|+|x|=1$ is NOT a function.

8. By adding an extra constraint to $(x-3)^2+(y-4)^2=11$, this would be a function. Try to find the constraint.

Domain and range of functions

Contact email:


text:
Determining Parameters for which Stochastic Process is a Martingale

I am trying to determine for what values of a, b the process $X_t=e^{aW_t+bt}, t \ge 0$ is a martingale with respect to $F_t^{W}$. Here $W_t$ is a brownian motion.

I know I need to show that $\mathbb E(X_t|F_s^{W})=X_s$, but I am not sure how to compute $\mathbb E(e^{aW_t+bt}|F_s^{W}).$ Any help would be appreciated.

• Have you tried decomposing $W_t = W_s + (W_t-W_s)$? It's the only trick I know, but it works. – Michał Miśkiewicz Apr 19 '17 at 22:58
• How do I deal with the expectation of the exponential though? – user75514 Apr 19 '17 at 23:00
• The brownian motion $W_t$ has a normal distribution. Have you done any exercise about deriving the moment generating function of normal before? – BGM Apr 20 '17 at 4:27
• Yes, I am familiar with MGFs. So I can substitute the MGF for $W_t$ for the expression inside the conditional expectation, but I am not sure how to tease the rest out. – user75514 Apr 20 '17 at 20:57


text:
Number is an abstract concept rather than a physical characteristic, it cannot be touched, but it can be represented by the objects. It can be used to count or measure a quantity. There are different numbers and number operations.

The basic number operations are addition, subtraction, multiplication and division.

These number operations are part of everyday life for everyone. In each event one will make use either one of the operations. In this section we will be learning more about numbers and operations.

Addition is an important basic operation in mathematics that represent combined collection of all objects together into a larger collection. That is total of all numbers. It is represented by the plus sign (+). The answer for addition of two numbers gives the 'Sum'.
Example: Addition of $3$ with $5$ gives the sum as $8$

$3 + 5 = 8$

## Subtraction

Subtraction is one of the basic operations of numbers. It is a process of deducting one number from other or take away a small part from the larger part. It is signified by the negative sign (-). It is an inverse operation of addition.
Example: The subtraction of $6$ from $10$ gives the value $4$.

$10 – 6 =4$

## Multiplication

The multiplication means that the repeated addition of numbers. It is signified by the sign ($\times$). For example, find the value of $3+3+3+3$.

This problem can be solved in two ways.

Addition: Add all the $3$s
$3+3+3+3=12$

Multiplication: There are four $3$s being added.

This is the same as $4 \times 3 = 12$.

## Division

Division can be approached from a different viewpoint. It is an inverse operation of multiplication. It may mean repeated subtraction. It is signified by the sign ($\div$).For example, we could interpret $15 \div 3$ to mean “how many $3$s are there in $15$?” We could subtract five $3$s in $15$.

This implies that $15 \div 3 = 5$.

## Numbers and Operations Problems

The following examples helps as to learn more about the operations.

### Solved Examples

Question 1: Find the sum of $864$ and $141$ ?
Solution:

864
+141
1005

The sum $864 + 141 = 1005$

Question 2: Find the difference between the numbers $864$ and $141$?
Solution:

864
- 141
723

The difference $864 -141 = 723$

Question 3: Find the product of $864$ and $10$
Solution:

864
x  10
000
864
8640

The product 864 \times 10 = 8640$Question 4: Divide the$864$by$16$? Solution: 16)864(54 80 64 64 00 The result of$864 \div 16 = 54\$


text:
# naginterfaces.library.correg.corrmat_partial¶

naginterfaces.library.correg.corrmat_partial(ny, nx, isz, r)[source]

corrmat_partial computes a partial correlation/variance-covariance matrix from a correlation or variance-covariance matrix computed by corrmat().

For full information please refer to the NAG Library document for g02by

https://www.nag.com/numeric/nl/nagdoc_27.1/flhtml/g02/g02byf.html

Parameters
nyint

The number of variables, , for which partial correlation coefficients are to be computed.

nxint

The number of variables, , which are to be considered as fixed.

iszint, array-like, shape

Indicates which variables belong to set and .

The th variable is a variable, for .

The th variable is a variable.

The th variable is not included in the computations.

rfloat, array-like, shape

The variance-covariance or correlation matrix for the variables as given by corrmat(). Only the upper triangle need be given.

Note: the matrix must be a full rank variance-covariance or correlation matrix and so be positive definite.

This condition is not directly checked by the function.

Returns
pfloat, ndarray, shape

The strict upper triangle of contains the strict upper triangular part of the partial correlation matrix. The lower triangle contains the lower triangle of the partial variance-covariance matrix if the matrix given in is a variance-covariance matrix. If the matrix given in is a partial correlation matrix then the variance-covariance matrix is for standardized variables.

Raises
NagValueError
(errno )

On entry, , and .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, values of are greater than zero and .

Constraint: exactly values of must be greater than zero.

(errno )

On entry, values of are less than zero and .

Constraint: exactly values of must be less than zero.

(errno )

On entry, the square root of the correlation matrix of the independent variables is singular.

Try removing some of the variables by setting the appropriate element of .

(errno )

On entry, the correlation matrix of the independent variables is singular.

Try removing some of the variables by setting the appropriate element of .

(errno )

On entry, an element of the partial correlation matrix is greater than .

Constraint: must be positive definite.

(errno )

On entry, a diagonal element of the partial covariance matrix is zero.

Constraint: must be positive definite.

(errno )

On entry, a diagonal element of the partial covariance matrix is zero and an element of the partial correlation matrix is greater than .

Constraint: must be positive definite.

Notes

Partial correlation can be used to explore the association between pairs of random variables in the presence of other variables. For three variables, , and , the partial correlation coefficient between and given is computed as:

where is the product-moment correlation coefficient between variables with subscripts and . The partial correlation coefficient is a measure of the linear association between and having eliminated the effect due to both and being linearly associated with . That is, it is a measure of association between and conditional upon fixed values of . Like the full correlation coefficients the partial correlation coefficient takes a value in the range () with the value indicating no association.

In general, let a set of variables be partitioned into two groups and with variables in and variables in and let the variance-covariance matrix of all variables be partitioned into,

The variance-covariance of conditional on fixed values of the variables is given by:

The partial correlation matrix is then computed by standardizing ,

To test the hypothesis that a partial correlation is zero under the assumption that the data has an approximately Normal distribution a test similar to the test for the full correlation coefficient can be used. If is the computed partial correlation coefficient then the appropriate statistic is

which has approximately a Student’s -distribution with degrees of freedom, where is the number of observations from which the full correlation coefficients were computed.

References

Krzanowski, W J, 1990, Principles of Multivariate Analysis, Oxford University Press

Morrison, D F, 1967, Multivariate Statistical Methods, McGraw–Hill

Osborn, J F, 1979, Statistical Exercises in Medical Research, Blackwell

Snedecor, G W and Cochran, W G, 1967, Statistical Methods, Iowa State University Press


text:
# maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the configuration of $n$ vectors $X_1, \ldots, X_n \in \mathbb{R}^n$ that maximizes the weighted sum $$V(X_1, \ldots, X_n) = \pi_1 \|X_1\|^2 + \ldots + \pi_n \| X_n\|^2$$ under the constraints $\|X_{i+1}-X_i\| \leq d_i$ for $i=1, 2, \ldots, n-1$ and $\sum_i \pi(i) X_i = 0$.

Motivation: as described in this article, this is another formulation of the following problem: among all possible reversible Markov chain in continuous time that have $\Pi=(\pi_1, \ldots, \pi_n)$ as invariant distribution on $\{ 1, \ldots, n\}$ and that can only jump on neighbouring sites, find the one that has maximum spectral gap, under a certain (linear) constraint on the jump intensities.

Remarks:

• one can consider the more general problem where the constraints are $\|X_i-X_j\| \leq d_{i,j}$: one can show that this is equivalent to a semidefinite programming optimization problem. It seems in general hard to solve; see above mentioned article.
• the case $\pi(1) = \ldots = \pi(n)$ is exactly solvable and an optimal configuration is a set of $n$ collinear vectors $X_i = \alpha_i U$, where the $\alpha_i$'s are easily computable; in this case, the problem is equivalent to maximizing $\sum_{i,j} \|X_i-X_j\|^2$.
-
Alekk, the article link is broken... –  Joseph O'Rourke Jan 20 '11 at 15:38
thanks: should be fixed now. –  Alekk Jan 20 '11 at 16:45


text:
## Overview

The singular value decomposition (SVD) is among the most important matrix factorizations of the computational era. In many domains, complex systems will generate data that is naturally arranged in large matrices, or more generally in arrays. For example, a time-series of data from an experiment or a simulation may be arranged in a matrix with each column containing all of the measurements at a given time. If the data at each instant in time is multi-dimensional, as in a high-resolution simulation of the weather in three spatial dimensions, it is possible to reshape or flatten this data into a high-dimensional column vector, forming the columns of a large matrix. Similarly, the pixel values in a grayscale image may be stored in a matrix, or these images may be reshaped into large column vectors in a matrix to represent the frames of a movie. Remarkably, the data generated by these systems are typically $\textbf{low rank}$, meaning that there are a few dominant patterns that explain the high-dimensional data. The SVD provides a systematic way to determine a low-dimensional approximation to high-dimensional data in terms of dominant patterns. This technique is $\textbf{data-driven}$ in that patterns are discovered purely from data, without the addition of expert knowledge or intuition. The SVD is numerically stable and provides a hierarchical representation of the data in terms of a new coordinate system defined by dominant correlations within the data. Moreover, the SVD is guaranteed to exist for any matrix, unlike the eigendecomposition.

## Definition of SVD

Generally, we are interested in analyzing a large data set $\mathbf{X} ∈ \mathbb{R}^{n×m}$:

$$\mathbf{X} = \begin{bmatrix} \vert & \vert & &\vert \\ \mathbf{x}_1 & \mathbf{x}_2 & \dots &\mathbf{x}_k \\ \vert & \vert & &\vert \end{bmatrix}$$

The columns $\mathbf{x}_k ∈ \mathbb{R}^n$ may be measurements from simulations or experiments. The index $k$ is a label indicating the $k^{th}$ distinct set of measurements. Often the state-dimension $n$ is very large, on the order of millions or billions of degrees of freedom. The columns are often called $\textbf{snapshots}$, and $m$ is the number of snapshots in $\mathbf{X}$. For many systems $n \gg m$, resulting in a tall-skinny matrix, as opposed to a short-fat matrix when $n \ll m$. The SVD is a unique matrix decomposition that exists for every real-valued matrix $\mathbf{X} ∈ \mathbb{R}^{n×m}$,

$$\mathbf{X} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$$

where $\mathbf{U} ∈ \mathbb{R}^{n×n}$ and $\mathbf{V} ∈ \mathbb{R}^{m×m}$ are unitary matrices (i.e. $UU^T = U^TU=1$) with orthonormal columns, and $\mathbf{\Sigma} ∈ \mathbb{R}^{m×m}$ is a matrix with real, nonnegative entries on the diagonal and zeros off the diagonal.

When $n ≥ m$, the matrix $\mathbf{\Sigma}$ has at most m nonzero elements on the diagonal, and may be written as $\mathbf{\Sigma} = \begin{bmatrix} \mathbf{\hat{\Sigma}} \\ \mathbf{0} \\ \end{bmatrix}$ .Therefore, it is possible to exactly represent $\mathbf{X}$ using the economy SVD:

$$\mathbf{X} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T = \begin{bmatrix} \mathbf{\hat{U}} & \mathbf{\hat{U}^{⊥}} \end{bmatrix} \begin{bmatrix} \mathbf{\hat{\Sigma}} \\ \mathbf{0} \\ \end{bmatrix} \mathbf{V}^T = \mathbf{\hat{U}}\mathbf{\hat{\Sigma}}\mathbf{V}^T$$

The columns of $\mathbf{\hat{U}^{⊥}}$ span a vector space that is complementary and orthogonal to that spanned by $\mathbf{\hat{U}}$. The columns of $\mathbf{U}$ are called left singular vectors of $\mathbf{X}$ and the columns of $\mathbf{V}$ are right singular vectors. The diagonal elements of $\mathbf{\Sigma}$ are called singular values and they are ordered from largest to smallest. The rank of $\mathbf{X}$ is equal to the number of nonzero singular values. The cost of computing the SVD is $\mathcal{O}(\min(mn^2,m^2n))$.

### Computing SVD

The code for computing SVD in Python is quite straightforward.

import numpy as np
X = np.random.rand(5, 3) % create random data matrix
U, S, V = np.linalg.svd(X,full_matrices=True) % full SVD
Uhat, Shat, Vhat = np.linalg.svd(X, full_matrices=False) % economy SVD

## Matrix Approximation

Perhaps the most useful and defining property of the SVD is that it provides an optimal low-rank approximation to a matrix $\mathbf{X}$. In fact, the SVD provides a hierarchy of low-rank approximations, since a rank-$r$ approximation is obtained by keeping the leading $r$ singular values and vectors, and discarding the rest.

Schmidt (of Gram-Schmidt) generalized the SVD to function spaces and developed an approximation theorem, establishing truncated SVD as the optimal low-rank approximation of the underlying matrix X. Schmidt’s approximation theorem was rediscovered by Eckart and Young, and is sometimes referred to as the $\textbf{Eckart-Young}$ theorem.

The optimal rank-$r$ approximation to $\mathbf{X}$, in a leastsquares sense, is given by the rank-$r$ SVD truncation $\mathbf{\tilde{X}}$:

$$\underset{\mathbf{\tilde{X}}, s.t. rank(\mathbf{\tilde{X}})=r}{argmin} ||\mathbf{X} - \mathbf{\tilde{X}}||_F = \mathbf{\tilde{U}}\mathbf{\tilde{\Sigma}}\mathbf{\tilde{V}}^T$$

Here, $\mathbf{\tilde{U}}$ and $\mathbf{\tilde{V}}$ denote the first $r$ leading columns of $\mathbf{U}$ and $\mathbf{U}$, and $\mathbf{\Sigma}$contains the leading $r × r$ sub-block of $\mathbf{\Sigma}$. $|| \cdot ||_F$ is the Frobenius norm.

Here, we establish the notation that a truncated SVD basis (and the resulting approximated matrix $\mathbf{\tilde{X}}$) will be denoted by $\mathbf{\tilde{U}}\mathbf{\tilde{\Sigma}}\mathbf{\tilde{V}}^T$. Because $\mathbf{\Sigma}$ is diagonal, the rank-$r$ SVD approximation is given by the sum of $r$ distinct rank-$1$ matrices:

$$\mathbb{\tilde{\Sigma}} = \sum_{k=1}^r \sigma_k \mathbf{u}_k \mathbf{v}_k^T = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^T + \sigma_2 \mathbf{u}_2 \mathbf{v}_2^T + \dots + \sigma_r \mathbf{u}_r \mathbf{v}_r^T.$$

This is the so-called $\textbf{dyadic}$ summation. For a given rank $r$, there is no better approximation for $\mathbf{X}$, in the $\mathcal{l}_2$ sense, than the truncated SVD approximation $\mathbf{\tilde{X}}$. Thus, high-dimensional data may be well described by a few dominant patterns given by the columns of $\mathbf{\tilde{U}}$ and $\mathbf{\tilde{V}}$.

## Image Compression

We demonstrate the idea of matrix approximation with a simple example: image compression. Natural images present a simple and intuitive example of this inherent compressibility. A grayscale image may be thought of as a real-valued matrix $\mathbf{X} ∈ \mathbb{R}^{n×m}$, where $n$ and $m$ are the number of pixels in the vertical and horizontal directions, respectively.

Consider the gray scale image of the lion. .

The figures below shows the approximate matrix $\mathbf{\tilde{X}}$ for the various SVD truncation values $r$. By $r = 100$, the reconstructed image is quite accurate. The SVD truncation results in a compression of the original image requiring $26.67\% = (5000\times 100 + 100 + 100\times3000)/(5000\times3000)$ storage if the original image has $5000 × 3000$ pixels, since only the first $100$ columns of $\mathbf{U}$ and $\mathbf{V}$, along with the first $100$ diagonal elements of $\mathbb{\Sigma}$ need to be stored.

.

.

.

The Python code for the truncated SVD is given below:

from matplotlib.image import imread
import matplotlib.pyplot as plt
import numpy as np
import os

img = plt.imshow(A)
img.set_cmap('gray')
plt.axis('off')
plt.show()

X = np.mean(A, -1)
U, S, VT = np.linalg.svd(X,full_matrices=False)
S = np.diag(S)

j = 0
for r in (5, 20, 100):
# Construct approximate image
Xapprox = U[:,:r] @ S[0:r,:r] @ VT[:r,:]
plt.figure(j+1)
j += 1
img = plt.imshow(Xapprox)
img.set_cmap('gray')
plt.axis('off')
plt.title('r = ' + str(r))
plt.show()

## Eigen Faces

In this problem, PCA (i.e. SVD on mean-subtracted data) is applied to a large library of facial images to extract the most dominant correlations between images. The result of this decomposition is a set of eigenfaces that define a new coordinate system. Images may be represented in these coordinates by taking the dot product with each of the principal components. Here, we demonstrate this algorithm using the Extended Yale Face Database B, consisting of cropped and aligned images of $38$ individuals ($28$ from the extended database, and $10$ from the original database) under $9$ poses and $64$ lighting conditions.Each image is $192$ pixels tall and $168$ pixels wide. Each of the facial images have been reshaped into a large column vector with $192 × 168 = 32, 256$ elements. We use the first $36$ people in the database as our training data for the eigenfaces example, and we hold back two people as a test set. As mentioned before, each image is reshaped into a large column vector, and the average face is computed and subtracted from each column vector. The mean-subtracted image vectors are then stacked horizontally as columns in the data matrix $X$. Thus, taking the SVD of the mean-subtracted matrix $\mathbf{X}$ results in the PCA. The columns of $\mathbf{U}$ are the eigenfaces, and they may be reshaped back into $192 \times 168$ images. Using the eigenface library, $\mathbf{\tilde{U}}$, we will approximately represent an image that was not in the training data. At the beginning, we held back two individuals (the $37th$ and $38th$ people), and we now use one of their images as a test image, $\mathbf{x_{test}}$.We will see how well a rank-$r$ SVD basis will approximate this image using the projection $\mathbf{\tilde{x}_{test}} = \mathbf{\tilde{U}} \mathbf{\tilde{U}}^T \mathbf{{x}_{test}}$.

import matplotlib.pyplot as plt
import numpy as np
import scipy.io

faces = mat_contents['faces'] #(32256, 2410)
m = int(mat_contents['m'])
n = int(mat_contents['n'])
nfaces = np.ndarray.flatten(mat_contents['nfaces']) # number of images for each person

# We use the first 36 people for training data
trainingFaces = faces[:,:np.sum(nfaces[:36])]
avgFace = np.mean(trainingFaces, axis=1) # size 192*168 by 1

# Compute eigenfaces on mean-subtracted training data
X = trainingFaces - np.tile(avgFace,(trainingFaces.shape[1],1)).T
U, S, VT = np.linalg.svd(X,full_matrices=False)

fig1 = plt.figure()
img_avg = ax1.imshow(np.reshape(avgFace,(m,n)).T)
img_avg.set_cmap('gray')
plt.axis('off')

img_u1 = ax2.imshow(np.reshape(U[:,0],(m,n)).T)
img_u1.set_cmap('gray')
plt.axis('off')

plt.show()

## Now show eigenface reconstruction of image that was omitted from test set
testFace = faces[:,np.sum(nfaces[:36])] # First face of person 37
plt.imshow(np.reshape(testFace,(m,n)).T)
plt.set_cmap('gray')
plt.title('Original Image')
plt.axis('off')
plt.show()

testFaceMS = testFace - avgFace
r_list = [50, 200, 800, 1600]

for r in r_list:
reconFace = avgFace + U[:,:r]  @ U[:,:r].T @ testFaceMS
img = plt.imshow(np.reshape(reconFace,(m,n)).T)
img.set_cmap('gray')
plt.title('r = ' + str(r))
plt.axis('off')
plt.show()

## References

Data-Driven Science and Engineering