text:
It is currently 19 Nov 2017, 11:28

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# If d is a positive integer and f is the product of the first

Author Message
TAGS:

### Hide Tags

Intern
Joined: 09 Sep 2005
Posts: 21

Kudos [?]: 8 [0], given: 0

If d is a positive integer and f is the product of the first [#permalink]

### Show Tags

10 Sep 2005, 12:58
8
This post was
BOOKMARKED
00:00

Difficulty:

65% (hard)

Question Stats:

49% (01:00) correct 51% (01:01) wrong based on 286 sessions

### HideShow timer Statistics

If d is a positive integer and f is the product of the first 30 positive integers, what is the value of d?

(1) 10^d is a factor of f
(2) d>6 Not Sufficient.

OPEN DISCUSSION OF THIS QUESTION IS HERE: if-d-is-a-positive-integer-and-f-is-the-product-of-the-first-126692.html
[Reveal] Spoiler: OA

Kudos [?]: 8 [0], given: 0

Math Expert
Joined: 02 Sep 2009
Posts: 42257

Kudos [?]: 132703 [4], given: 12335

Re: Number Properties from GMATPrep [#permalink]

### Show Tags

05 Oct 2009, 05:58
4
KUDOS
Expert's post
DenisSh wrote:
Bunuel wrote:
2. Finding the number of powers of a prime number k, in the n!.
What is the power of 3 in 35!...

In the same way as for 5? i.e., 35/3 + 35/9 + 35/27 = 11 + 3 + 1 = 15.

Am I right?

Absolutely, here is the way to calculate the number of powers of a prime number k, in n!.
The formula is:
$$\frac{n}{k}+\frac{n}{k^2}+\frac{n}{k^3}$$ ... till $$n>k^x$$

What is the power of 2 in 25!
$$\frac{25}{2}+\frac{25}{4}+\frac{25}{8}+\frac{25}{16}=12+6+3+1=22$$

There is another formula finding powers of non prime in n!, but think it's not needed for GMAT.
_________________

Last edited by bb on 21 Oct 2009, 13:14, edited 3 times in total.
formulas

Kudos [?]: 132703 [4], given: 12335

Manager
Joined: 14 Jul 2005
Posts: 104

Kudos [?]: 9 [3], given: 0

Location: Sofia, Bulgaria

### Show Tags

10 Sep 2005, 15:13
3
KUDOS
Statement 1 tells us that we need to find out how many times is 30! divisible by 10. The hardest way to solve this is to break down 30! to its prime factors and count the 2s and 5s, because they make up the 10s. It is pretty easy to see that there are many more 2s than 5s in 30!, because we have 15 even numbers and only 6 numbers divisible by 5.

The numbers that contain 5s are 5=5, 2*5=10, 3*5=15, 4*5=20, 5*5=25, 6*5=30. So we have a total of seven 5s and more than seven 2s, which means that 30! can be evenly divided by 10 up to seven times. Therefore 1 <= d <=7. We can't figure out the exact value, so the statement is insufficient.

Statement 2 tells us that d > 6, which is a worthless piece of information on its own.

When we combine the 2 statements, we get C.

There was a very nice discussion of a similar problem about a month ago, but I can't find the post. The approach is "stolen" from there.

Kudos [?]: 9 [3], given: 0

Math Expert
Joined: 02 Sep 2009
Posts: 42257

Kudos [?]: 132703 [3], given: 12335

Re: GMATPrep DS Product of first 30 integers [#permalink]

### Show Tags

30 Nov 2009, 22:54
3
KUDOS
Expert's post
If d is a positive integer and f is the product of the first 30 positive integers, what is the value of d?

(1) 10^d is a factor of f --> $$k*10^d=30!$$.

First we should find out how many zeros $$30!$$ has, it's called trailing zeros. It can be determined by the power of $$5$$ in the number $$30!$$ --> $$\frac{30}{5}+\frac{30}{25}=6+1=7$$ --> $$30!$$ has $$7$$ zeros.

$$k*10^d=n*10^7$$, (where $$n$$ is the product of other multiples of 30!) --> it tells us only that max possible value of $$d$$ is $$7$$. Not sufficient.

(2) $$d>6$$ Not Sufficient.

(1)+(2) $$d>6$$, $$d_{max}=7$$ --> $$d=7$$.

_________________

Kudos [?]: 132703 [3], given: 12335

Math Expert
Joined: 02 Sep 2009
Posts: 42257

Kudos [?]: 132703 [2], given: 12335

Re: Number Properties from GMATPrep [#permalink]

### Show Tags

05 Oct 2009, 05:02
2
KUDOS
Expert's post
If you are aiming for 700+ in GMAT you should know 2 important things about factorials:

1. Trailing zeros:
Trailing zeros are a sequence of 0s in the decimal representation (or more generally, in any positional representation) of a number, after which no other digits follow.

125000 has 3 trailing zeros;

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer n, can be determined with this formula:

$$\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+...+\frac{n}{5^k}$$, where k must be chosen such that 5^(k+1)>n

It's more simple if you look at an example:

How many zeros are in the end (after which no other digits follow) of 32!?
$$\frac{32}{5}+\frac{32}{5^2}=6+1=7$$ (denominator must be less than 32, $$5^2=25$$ is less)

So there are 7 zeros in the end of 32!

The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

2. Finding the number of powers of a prime number k, in the n!.

What is the power of 3 in 35!

Tell me if you need this one too.
_________________

Kudos [?]: 132703 [2], given: 12335

Director
Joined: 16 May 2007
Posts: 547

Kudos [?]: 76 [1], given: 0

DS : product of first 30 positive integers [#permalink]

### Show Tags

09 Aug 2007, 19:39
1
KUDOS
If d is a positive integer and f is the product if the first 30 positive integers, what is the value of d?

1. 10^d is a factor of f.
2. d>6

Kudos [?]: 76 [1], given: 0

VP
Joined: 10 Jun 2007
Posts: 1434

Kudos [?]: 370 [1], given: 0

Re: DS : product of first 30 positive integers [#permalink]

### Show Tags

09 Aug 2007, 21:26
1
KUDOS
trahul4 wrote:
If d is a positive integer and f is the product if the first 30 positive integers, what is the value of d?

1. 10^d is a factor of f.
2. d>6

C.

Given: f=30!
(1) 10^d is a factor of f
Plug in d=1, 10 is a factor of f, Yes!
d=2, 100 is a factor of f, Yes! because 25*4 = 100
INSUFFICIENT.

(2) d>6. INSUFFICIENT

Together, plug in d=7, Is 10^7 is a factor of f?
5*2 = 10
10 = 10
15*12 = 180 = 18*10
20 = 2*10
25*4= 10*10
30 = 3*10
I don't think there is any more, SUFFICIENT.

Kudos [?]: 370 [1], given: 0

Manager
Joined: 10 Jul 2009
Posts: 164

Kudos [?]: 120 [1], given: 8

### Show Tags

10 Aug 2009, 11:21
1
KUDOS
f = 30!

1) 10^d is a factor of f
so we have to find the powers of 10 in the 30!
number of powers of 10 is equal to the number of 2 and 5
multiples of 5 less than or equal to 30 are 5,10, 15, 20, 25, 30.
So number of powers of 5 in 30! = 7
As we have many multiple is 2, the maximum value of d is 7
(i.e. d can be 1 or 2 or 3 or 4 ...)
2) d>6.
d can take any value.
Clubbing 1 and 2 we get,
d = 7

Kudos [?]: 120 [1], given: 8

Manager
Joined: 08 Oct 2009
Posts: 61

Kudos [?]: 30 [1], given: 5

Re: Number Properties from GMATPrep [#permalink]

### Show Tags

19 Oct 2009, 15:51
1
KUDOS
Great stuff Bunuel !!

Kudos [?]: 30 [1], given: 5

Manager
Joined: 24 Jun 2009
Posts: 58

Kudos [?]: 94 [1], given: 2

GMATPrep DS Product of first 30 integers [#permalink]

### Show Tags

30 Nov 2009, 18:44
1
KUDOS

Kudos [?]: 94 [1], given: 2

Senior Manager
Affiliations: PMP
Joined: 13 Oct 2009
Posts: 296

Kudos [?]: 175 [1], given: 37

Re: GMATPrep DS Product of first 30 integers [#permalink]

### Show Tags

30 Nov 2009, 20:07
1
KUDOS
I think the answer is C.

S1 by itself is not sufficient, coz if d=1 means 10 is a factor of 30!, true, if d =2, 100 is also a factor of 30!, d can be 1,2 or more... so insuff
S2 by itself is not sufficient, coz d>6 means d can be 7,8,9 or anything - clearly insuff

combining the two however we can asnwer the question, because in 30! we have 7 powers of 10 as below:

1.2.3.4.5 has one power for 10 (2*5)
6.7.8.9.10 has one power for 10 (10)
11.12.13.14.15 has one power for 10 (15*14 or 15*12)
16.17.18.19.20 has one power for 10 (20)
21.22.23.24.25 has 2 powers for 10 (25*24)
26.27.28.29.30 has one power for 10 (30)
total of 7 so $$10^7$$ is the highest $$10^d$$ being fact of 30! hence d=7
_________________

Thanks, Sri
-------------------------------
keep uppp...ing the tempo...

Press +1 Kudos, if you think my post gave u a tiny tip

Kudos [?]: 175 [1], given: 37

Math Expert
Joined: 02 Sep 2009
Posts: 42257

Kudos [?]: 132703 [1], given: 12335

Re: DS : product of first 30 positive integers [#permalink]

### Show Tags

11 Aug 2010, 16:26
1
KUDOS
Expert's post
masland wrote:
Is there anyway to quickly determine if d>7 is not a factor of 30! ?

If d is a positive integer and f is the product of the first 30 positive integers, what is the value of d?

(1) 10^d is a factor of f --> $$k*10^d=30!$$.

First we should find out how many zeros $$30!$$ has, it's called trailing zeros. It can be determined by the power of $$5$$ in the number $$30!$$ --> $$\frac{30}{5}+\frac{30}{25}=6+1=7$$ --> $$30!$$ has $$7$$ zeros.

$$k*10^d=n*10^7$$, (where $$n$$ is the product of other multiples of 30!) --> it tells us only that max possible value of $$d$$ is $$7$$. Not sufficient.

Side notes: 30! is some huge number with 7 trailing zeros (ending with 7 zeros). Statement (1) says that $$10^d$$ is factor of this number, but $$10^d$$ can be 10 (d=1) or 100 (d=2) ... or 10,000,000 (d=7). Basically $$d$$ can be any integer from 1 to 7, inclusive (if $$d>7$$ then $$10^d$$ won't be a factor of 30! as 30! has only 7 zeros in the end). So we can not determine single numerical value of $$d$$ from this statement. Hence this statement is not sufficient.

(2) $$d>6$$ Not Sufficient.

(1)+(2) $$d>6$$, $$d_{max}=7$$ --> $$d=7$$.

Hope it helps.
_________________

Kudos [?]: 132703 [1], given: 12335

Math Expert
Joined: 02 Sep 2009
Posts: 42257

Kudos [?]: 132703 [1], given: 12335

Re: DS : product of first 30 positive integers [#permalink]

### Show Tags

13 Aug 2010, 02:53
1
KUDOS
Expert's post
estreet wrote:
It can be determined by the power of $$5$$ in the number $$30!$$ --> $$\frac{30}{5}+\frac{30}{25}=6+1=7$$ --> $$30!$$ has $$7$$ zeros.

I don't understand the calculations that were performed here. How did you get to $$\frac{30}{5}+\frac{30}{25}=6+1=7$$? How did you know that the 5 was the factor needed? Thanks

_________________

Kudos [?]: 132703 [1], given: 12335

Intern
Joined: 09 Sep 2005
Posts: 21

Kudos [?]: 8 [0], given: 0

### Show Tags

10 Sep 2005, 16:27
WELL DONE ... BRILLIANT ... BRAVO

Many thanks

Kudos [?]: 8 [0], given: 0

Manager
Joined: 06 Aug 2005
Posts: 197

Kudos [?]: 13 [0], given: 0

### Show Tags

10 Sep 2005, 22:04
The maximum value of d = int(d/5) + int (d/(5^2)) + ....

d = int(30/5) + int(30/25) + ... = 6 + 1 + 0 = 7

Kudos [?]: 13 [0], given: 0

VP
Joined: 13 Jun 2004
Posts: 1111

Kudos [?]: 51 [0], given: 0

Location: London, UK
Schools: Tuck'08

### Show Tags

10 Sep 2005, 22:44
this problem is great, I was totally lost and I would have gone for E
very nice answer Vasild, I am gonna study this later

Kudos [?]: 51 [0], given: 0

Intern
Joined: 11 Sep 2005
Posts: 14

Kudos [?]: [0], given: 0

### Show Tags

15 Sep 2005, 14:18
vasild wrote:
Statement 1 tells us that we need to find out how many times is 30! divisible by 10. The hardest way to solve this is to break down 30! to its prime factors and count the 2s and 5s, because they make up the 10s. It is pretty easy to see that there are many more 2s than 5s in 30!, because we have 15 even numbers and only 6 numbers divisible by 5.

The numbers that contain 5s are 5=5, 2*5=10, 3*5=15, 4*5=20, 5*5=25, 6*5=30. So we have a total of seven 5s and more than seven 2s, which means that 30! can be evenly divided by 10 up to seven times. Therefore 1 <= d <=7. We can't figure out the exact value, so the statement is insufficient.

Statement 2 tells us that d > 6, which is a worthless piece of information on its own.

When we combine the 2 statements, we get C.

There was a very nice discussion of a similar problem about a month ago, but I can't find the post. The approach is "stolen" from there.

i didnt get how we get "total of seven 5s"..i am able to see only six 5's.

Kudos [?]: [0], given: 0

Intern
Joined: 11 Sep 2005
Posts: 14

Kudos [?]: [0], given: 0

### Show Tags

15 Sep 2005, 14:20
davesh wrote:
vasild wrote:
Statement 1 tells us that we need to find out how many times is 30! divisible by 10. The hardest way to solve this is to break down 30! to its prime factors and count the 2s and 5s, because they make up the 10s. It is pretty easy to see that there are many more 2s than 5s in 30!, because we have 15 even numbers and only 6 numbers divisible by 5.

The numbers that contain 5s are 5=5, 2*5=10, 3*5=15, 4*5=20, 5*5=25, 6*5=30. So we have a total of seven 5s and more than seven 2s, which means that 30! can be evenly divided by 10 up to seven times. Therefore 1 <= d <=7. We can't figure out the exact value, so the statement is insufficient.

Statement 2 tells us that d > 6, which is a worthless piece of information on its own.

When we combine the 2 statements, we get C.

There was a very nice discussion of a similar problem about a month ago, but I can't find the post. The approach is "stolen" from there.

i didnt get how we get "total of seven 5s"..i am able to see only six 5's.

My apologies..i got ur funda..

Kudos [?]: [0], given: 0

Manager
Joined: 26 Jun 2006
Posts: 151

Kudos [?]: 7 [0], given: 0

### Show Tags

19 Aug 2006, 10:15
Stumbled on this one. Anyone knows how to do it?

If d is a positive integer and F is the product of the first 30 positive integers, what is the value of d?

(1) 10^d is a factor of F

(2) d>6

Thanks!

Kudos [?]: 7 [0], given: 0

Intern
Joined: 26 Apr 2005
Posts: 19

Kudos [?]: [0], given: 0

### Show Tags

19 Aug 2006, 10:35
I think it is C
F = 1*2*3...*30
From A we know 10^d * X = F means..
and F contains for 7 instances of (5*2)
as in... 1*2*3*4...10 has two (5*2 and 10)
11 to 20 has (15 and 20)(meaning another 5 and 2*10 makes 2)
21 to 30 has a 25 and 30 (5 * 5 = 25 and 3 *10...for makes 3 instances of 10)
so d could be from 1 to 7...
from statement 2 u get that d > 6

Thus combining both u get the exact vlue of d...
Hence C

Kudos [?]: [0], given: 0

19 Aug 2006, 10:35

Go to page    1   2   3   4    Next  [ 70 posts ]

Display posts from previous: Sort by


text:
# Multiset notation in LaTeX

Does anyone know how to make (nice looking) double bracket multiset notation in LaTeX. i.e something like (\binom{n}{k}) where there are two outer brackets instead of 1 as in binomial? You can see an example of what I mean in http://en.wikipedia.org/wiki/Multiset under the heading "Multiset coefficients" with the double brackets.

In wikpedia they typset it as: \left(\!\!{n\choose k}\!\!\right) but although this works well for LaTeX in maths mode, with inline equations the outer bracket becomes much larger than the inner bracket.

I have also tried using \genfrac{((}{))}{0pt}{}{n}{k} but it has an error with the double brackets.

I am using \binom as well in my document, so I would like the bracket sizes to be similar for \binom and \multiset.

Thanks for any help. I'm surprised I can't find a solution on google.

• @user2084: I can't reproduce your observation that with inline equations the outer parentheses become much larger than the inner ones. Can you add a minimal example that illustrates your problem? Nov 23 '10 at 18:07

I got the definition below after some tinkering. It seems to look fine at any size.

\documentclass[a4paper,12pt]{article}
\pagestyle{empty}
\usepackage{mathtools}
\def\multiset#1#2{\ensuremath{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}}

\begin{document}
Consider an inline multiset, \multiset{n}{k}, or a displayed one,
$\multiset{n}{k},$
or perhaps even a displayed one with something big up- and downstairs,
$\multiset{ {\displaystyle \sum_{j=1}^n n^j}} {{\displaystyle \sum_{j=1}^n (-1)^j n^j}}_{n \text{ even}}.$
\end{document}

• Your post was much better before the edit! It's much nicer to see the complete code here on this site. Nov 23 '10 at 11:52
• There you go. It's edited back in Nov 23 '10 at 11:56
• Thanks! By the way, it doesn't seem that the minimal class cares about the 12pt option. Nov 23 '10 at 18:01
– jjh
Nov 25 '10 at 4:47

\def\multiset#1#2{\left(\!\left({#1\atopwithdelims..#2}\right)\!\right)} maybe? Looks ok in inline equations.

• The spacing between parens is a bit too large. Wikipedia's multiset page uses a similar hack but with two \!'s instead of just one on either side, e.g. \left(\!\!{4\choose18}\!\!\right). Jan 24 '17 at 21:54

Old post, but I ran into issues with the other answers, so here's mine:

\newcommand{\mch}[2]{
\left.\mathchoice
{\left(\kern-0.48em\binom{#1}{#2}\kern-0.48em\right)}
{\big(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\big)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
\right.}

With Kahen's answer I had issues if a non-display-mode line had both \binom and \mch (the name \multiset seems a bit off too; I read the symbol as "multichoose"), namely the outer and inner parens weren't of equal size. This answer incorporates jjh's comment above without making you use two separate macros. I'm sure there are minor issues with it, but it works for me in a paper that uses it a bunch of times.

• Did not work for me. "\ch" was not recognized. Jul 25 '19 at 15:52
• Whoops, \ch was just a synonym for \binom. I've updated it. Jul 25 '19 at 20:59
• Thanks, I should have guessed that. Jul 29 '19 at 6:22

format: plain


text:
# Solution to a modified linear system using two methods

I am trying to obtain the solution to a modified linear system. I am comparing two methods to solve this modified linear system, and I'm noticing some issues with one of the methods.

A linear system is written as $$Ax=b$$

where $$A \in \mathbb{R}^{n\times n}$$ and $$x,b \in \mathbb{R}^n$$. For a non-singular $$A$$ and a known $$b$$, we can obtain $$x$$ using $$x=A^{-1}b$$

I came across a problem where I am basically given something that looks like $$Ax=b$$, but 1 element in $$x$$ is known beforehand, and 1 element in $$b$$ is unknown beforehand.

Suppose the known element in $$x$$ is $$x_i$$ and unknown element in $$b$$ is $$b_j$$. $$b_p$$ is known for $$p \in \{1,\ldots,n\}\setminus \{j\}$$. $$x_q$$ is unknown for $$q \in \{1,\ldots,n\}\setminus \{i\}$$

I want to formulate the system $$A'x'=b'$$ where $$x'$$ is the vector of unknowns and $$b'$$ is the vector of knowns. I want to solve for $$x'$$.

I've basically identified two ways to solve to do this. Method 1, which does some "swapping" PRIOR to taking an inverse, and Method 2, which does the "swapping" AFTER taking an inverse.

# Method 1:

We can write the original system as

$$\begin{bmatrix} A_{1,1}x_1 + \cdots + A_{1,i-1}x_{i-1} + A_{1,i}x_i + A_{1,i+1}x_{i+1} + \cdots + A_{1,n}x_{n} \\ \vdots\\ A_{j-1,1}x_1 + \cdots + A_{j-1,i-1}x_{i-1} + A_{j-1,i}x_i + A_{j-1,i+1}x_{i+1} + \cdots + A_{j-1,n}x_{n} \\ A_{j,1}x_1 + \cdots + A_{j,i-1}x_{i-1} + A_{j,i}x_i + A_{j,i+1}x_{i+1} + \cdots + A_{j,n}x_{n} \\ A_{j+1,1}x_1 + \cdots + A_{j+1,i-1}x_{i-1} + A_{j+1,i}x_i + A_{j+1,i+1}x_{i+1} + \cdots + A_{j+1,n}x_{n} \\ \vdots\\ A_{n,1}x_1 + \cdots + A_{n,i-1}x_{i-1} + A_{n,i}x_i + A_{n,i+1}x_{i+1} + \cdots + A_{n,n}x_{n} \\ \end{bmatrix} = \begin{bmatrix} b_1 \\ \vdots \\ b_{j-1} \\ b_j \\ b_{j+1} \\ \vdots \\ b_n \end{bmatrix}$$

We can rearrange the terms so that the RHS consists only of knowns and all the known $$x$$'s are on the RHS (I call this step the "swapping"): $$\begin{bmatrix} A_{1,1}x_1 + \cdots + A_{1,i-1}x_{i-1} + 0 + A_{1,i+1}x_{i+1} + \cdots + A_{1,n}x_{n} \\ \vdots\\ A_{j-1,1}x_1 + \cdots + A_{j-1,i-1}x_{i-1} + 0 + A_{j-1,i+1}x_{i+1} + \cdots + A_{j-1,n}x_{n} \\ A_{j,1}x_1 + \cdots + A_{j,i-1}x_{i-1} - b_j + A_{j,i+1}x_{i+1} + \cdots + A_{j,n}x_{n} \\ A_{j+1,1}x_1 + \cdots + A_{j+1,i-1}x_{i-1} + 0 + A_{j+1,i+1}x_{i+1} + \cdots + A_{j+1,n}x_{n} \\ \vdots\\ A_{n,1}x_1 + \cdots + A_{n,i-1}x_{i-1} + 0 + A_{n,i+1}x_{i+1} + \cdots + A_{n,n}x_{n} \\ \end{bmatrix} = \begin{bmatrix} b_1 - A_{1,i}x_i \\ \vdots \\ b_{j-1} - A_{j-1,i}x_i \\ -A_{j,i}x_i \\ b_{j+1} - A_{j+1,i}x_i \\ \vdots \\ b_n - A_{n,i}x_i \end{bmatrix}$$

So now we can form $$A'x'=b'$$ where $$A' = \begin{bmatrix} A_{1,1} & \cdots & A_{1,i-1} & 0 & A_{1,i+1} & \cdots & A_{1,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ A_{j-1,1} & \cdots & A_{j-1,i-1} & 0 & A_{j-1,i+1} & \cdots & A_{j-1,n} \\ A_{j,1} & \cdots & A_{j,i-1} & -1 & A_{j,i+1} & \cdots & A_{j,n} \\ A_{j+1,1} & \cdots & A_{j+1,i-1} & 0 & A_{j+1,i+1} & \cdots & A_{j+1,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ A_{n,1} & \cdots & A_{n,i-1} & 0 & A_{n,i+1} & \cdots & A_{n,n} \\ \end{bmatrix} \\ x' = \begin{bmatrix} x_1 \\ \vdots \\ x_{i-1} \\ b_j \\ x_{i+1}\\ \vdots \\ x_n \end{bmatrix} \\ b' = \begin{bmatrix} b_1 - A_{1,i}x_i \\ \vdots \\ b_{j-1} - A_{j-1,i}x_i \\ -A_{j,i}x_i \\ b_{j+1} - A_{j+1,i}x_i \\ \vdots \\ b_n - A_{n,i}x_i \end{bmatrix}$$

So we can now solve for $$x'=A'^{-1}b'$$. But I am finding that $$A'$$ has a large condition number in some of my application cases. In one case the condition number was $$O(10^{16})$$, which is basically numerically singular.

# Method 2:

We work with the original $$Ax=b$$. We take the inverse of $$A$$, and write $$x=A^{-1}b = Cb$$ where $$C=A^{-1}$$. Recall that $$b_j$$ is unknown and $$x_i$$ is known.

So if we expand out the terms we can write something that looks like this (note the "swapping" in this method occurs after we have taken the inverse): $$\begin{bmatrix} x_1 - b_j*C_{1,j}\\ \vdots \\ x_{i-1}-b_j*C_{i-1,j} \\ -b_j*C_{i,j} \\ x_{i+1}-b_j*C_{i+1,j} \\ \vdots\\ x_n-b_j*C_{n,j} \end{bmatrix} = \begin{bmatrix} C_{1,1} & \cdots & C_{1,j-1} & 0 & C_{1,j+1} & \cdots & C_{1,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ C_{i-1,1} & \cdots & C_{i-1,j-1} & 0 & C_{i-1,j+1} & \cdots & C_{i-1,n} \\ C_{i,1} & \cdots & C_{i,j-1} & -1 & C_{i,j+1} & \cdots & C_{i,n} \\ C_{i+1,1} & \cdots & C_{i+1,j-1} & 0 & C_{i+1,j+1} & \cdots & C_{i+1,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ C_{n,1} & \cdots & C_{n,j-1} & 0 & C_{n,j+1} & \cdots & C_{n,n} \\ \end{bmatrix} \begin{bmatrix} b_1 \\ \vdots \\ b_{j-1} \\ x_i \\ b_{j+1} \\ \vdots \\ b_{n} \end{bmatrix}$$

Multiplying $$Cb$$ gives me the LHS of the above equation. Then I can solve for $$b_j$$ and use that to get the unknown $$x$$'s.

# Question/Confusion

Both methods should arrive at the same answer (and it does in most cases), but the issue is in Method 1, the matrix that is being inverted, $$A'$$, is close to being singular in some cases, whereas the matrix $$A$$ in Method 2 is much more well conditioned. For example, in one case that I conducted, $$A'$$ had a condition number that was $$O(10^{17})$$, but $$A$$'s condition number was only $$O(10^6)$$. But both methods should arrive at the same answer, so my confusion is why is method 1 so ill conditioned (for some cases) when they're effectively solving the same problem, just with some different sequence of linear algebra operations?

# Edit (Including the referenced matrix that is giving me issues)

Here is the matrix that is causing me issues ($$n=6$$):

$$A=\begin{bmatrix} 567e+009 & -49e+003 & 0 & 0 & 77e+000 & 623e+006\\ 0 & 0 & 567e+009 & -49e+003 & 260e+000 & -10.1493e+012\\ 590e+003 & 5e+012 & 2e+006 & -77e+015 & 17e+015 & -1e+009\\ -217e+000 & 20e+012 & -77e+000 & -623e+006 & 0 & 0\\ -590e+003 & -4e+012 & -6e+006 & 618e+015 & -2e+015 & -62e+003\\ 0 & 0 & -283e+009 & -8e+000 & -217e+000 & 20e+012 \end{bmatrix}$$ This matrix has a condition number that is $$O(10^6)$$. This matrix is obviously not that well conditioned to begin with.

For this matrix, $$i = 3$$ and $$j=2$$, so we can write  A'=$$\begin{bmatrix} 567e+009 & -49e+003 & 0 & 0 & 77e+000 & 623e+006\\ 0 & 0 & -1 & -49e+003 & 260e+000 & -10.1493e+012\\ 590e+003 & 5e+012 & 0 & -77e+015 & 17e+015 & -1e+009\\ -217e+000 & 20e+012 & 0 & -623e+006 & 0 & 0\\ -590e+003 & -4e+012 & 0 & 618e+015 & -2e+015 & -62e+003\\ 0 & 0 & 0 & -8e+000 & -217e+000 & 20e+012 \end{bmatrix}$$

This matrix has a condition number of about $$O(10^{16})$$. Matlab is actually telling me that this matrix is rank 5..

# MATLAB Script Below (in reference to above matrices):

clc;  clear all; close all
format shorteng

%note this matrix was copied over from a simulation code for debugging
A = [   567322834646.66357       -49079.870115227313        0.0000000000000000        0.0000000000000000        77.820576525741828        623686024.79204798
0.0000000000000000        0.0000000000000000        567322834646.66357       -49079.870115227313        260.93116192028197       -10149285653847.125
590586.40976551455        4733201765487.0498        1980226.8884948289       -77023718450704160.        17221828521465004.       -1489883811.0520439
-217.85980585264346        20382594821474.887       -77.820576525741828       -623686024.79204798        0.0000000000000000        0.0000000000000000
-590586.40976551455       -4733201765487.0498       -6613420.0652273158        6.1874039153838144E+017  -2152728565180286.5       -62487.145455156555
0.0000000000000000        0.0000000000000000       -283661417322.95770       -8.2338259132967249       -217.85980585264346        20382594821474.887 ]

i = 3;
j = 2;

%This is A' on math.stackexchange
A_prime = A;
A_prime(:,i) = 0;
A_prime(j,i) = -1;

fprintf('The rank of A is: %i \n', rank(A))
fprintf('The rank of A_prime is: %i \n', rank(A_prime))
fprintf('The condition number of A is: %e \n', cond(A))
fprintf('The condition number of A_prime is: %e \n', cond(A_prime))

If you execute this code, you will get the following output:

The rank of A is: 6
The rank of A_prime is: 5
The condition number of A is: 1.635215e+06
The condition number of A_prime is: 8.141279e+17

So $$x'$$ is not solvable if using method 1. Or I should say that it appears method 1 is suggesting that $$x'$$ is not unique.

But if you use method 2, then you can obtain a unique (?) $$x'$$. All we need to do is invert the original $$A$$ matrix, do some swapping and some simple algebra to get $$x'$$.

My gut tells me method 1 is more sound, and that method 2 might be producing a $$x'$$ vector, but the solution produced is not unique?

• It seems your matrix for $A'$ does not match what it should based on your equations. The bottom row seems to have a $0$ replacing an element of the matrix that it should not be. Assuming you fix that, does the results change? Mar 7 '19 at 7:36
• I should clarify that I'm talking about your example $A'$ at the bottom of your answer in the Edit section. It doesn't match the $A'$ equation you define earlier, which makes sense. Mar 7 '19 at 14:11
• @spektr I think that’s a typo in the OP. I will check my code when I get to my computer.
– 24n8
Mar 7 '19 at 14:14
• Just checked. It was a typo when I copied it over on here.
– 24n8
Mar 7 '19 at 14:25

As a toy problem, consider the system of equations

\begin{align} \underbrace{\begin{bmatrix} a & b \\ c & d \end{bmatrix}}_{A} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix} \end{align}

Let us assume we know $$x_1$$ and don't know $$r_1$$. We can rewrite the system of equations to be

\begin{align} \underbrace{\begin{bmatrix} -1 & b \\ 0 & d \end{bmatrix}}_{A'} \begin{bmatrix} r_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} -a x_1 \\ r_2 - c x_1 \end{bmatrix} \end{align}

We know that $$\text{det}(A) = ad - bc$$. We also readily see that $$\text{det}(A') = -d$$. Clearly, the determinants between $$A$$ and $$A'$$ are very different and we can see that if $$|d| \rightarrow 0$$, we will begin to have a poorly conditioned system of equations that ultimately become singular. This is essentially Method 1.

If we consider Method 2, we find that

\begin{align} C = A^{-1} &= \begin{bmatrix} a & b \\ c & d\end{bmatrix}^{-1} \\ &= \text{det}(A)^{-1} \begin{bmatrix} d & -b \\ -c & a\end{bmatrix} \end{align}

Using the $$C$$ found above and separating known and unknown terms in the equation $$Cr = x$$, we can find the new system of equations to solve is

\begin{align} \underbrace{\text{det}(A)^{-1}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}}_{C} \begin{bmatrix} r_1 \\ r_2 \end{bmatrix} &= \begin{bmatrix}x_1 \\ x_2 \end{bmatrix} \\ &\Downarrow \\ \underbrace{\begin{bmatrix} \text{det}(A)^{-1} d & 0 \\ -\text{det}(A)^{-1} c & -1 \end{bmatrix}}_{C'} \begin{bmatrix} r_1 \\ x_2 \end{bmatrix} &= \begin{bmatrix}x_1 + \text{det}(A)^{-1} b r_2\\ -\text{det}(A)^{-1}a r_2 \end{bmatrix} \end{align}

We readily know that $$\text{det}(C) = \text{det}(A^{-1}) = \text{det}(A)^{-1}$$. We can also readily see that $$\text{det}(C') = -\text{det}(A)^{-1} d = -\text{det}(C) d$$. Interestingly in this case, if $$|d| \rightarrow 0$$, it is still possible that $$\text{det}(C)$$ could be large enough to make $$\text{det}(C')$$ not too small, particularly if $$|\text{det}(A)|$$ is small. Of course, there's also the chance that $$|\text{det}(C)| \ll 1$$, which could make some $$\text{det}(C') \rightarrow 0$$ even if $$|d|$$ is not too small.

The point here is that Method 2 actually appears to produce a different result if we assume that we compute $$C$$ as an exact inverse and don't multiply the $$Cr = x$$ equation by $$\text{det}(A)$$. Even in arbitrary precision, you could see a difference between using Method 1 versus using Method 2. Taking into account finite precision issues and you may see more dramatic differences.


text:
# Math Help - Polynomials of 9th Grade

1. ## Polynomials of 9th Grade

Use these patterns to factor polynimials that are sums and differences of cubes:
a^3 + b^3 = (a+b)(a^2-ab+b^2)
a^3 - b^3 = (a-b)(a^2-ab+b^2)

1. x^3 + 8
2. 8x^3 + 27
3. 64 - y^3
4. 2u^3 +16v^3
5. d^6 + f^3
6. w^6 - 1

Thank You so so much!!

2. Originally Posted by tecktonikk
Use these patterns to factor polynimials that are sums and differences of cubes:
a^3 + b^3 = (a+b)(a^2-ab+b^2) --- (1)
a^3 - b^3 = (a-b)(a^2-ab+b^2) --- (2)

1. x^3 + 8
Note that $x^3+8=x^3+(2)^3$. Now use (1) to factor..

2. 8x^3 + 27
Note that $8x^3+27=(2x)^3+(3)^3$. Now use (1) to factor..

3. 64 - y^3
Note that $64-y^3=(4)^3-y^3$. Now use (2) to factor..

4. 2u^3 +16v^3
Note that $2u^3+16v^3=(\sqrt[3]{2}u)^3+(2\sqrt[3]{2}v)^3$. Now use (1) to factor..

5. d^6 + f^3
Note that $d^6+f^3=(d^2)^3+f^3$. Now use (1) to factor..

6. w^6 - 1
Note that $w^6-1=(w^2)^3-1^3$. Now use (2) to factor..

Thank You so so much!!

3. Hi tecktonikk

You have been given the formula. All you have to do is just manipulate the questions so they satisfy the formula given.

Example :
x^3 + 8 = x^3 + 2^3 , so a = x and b = 2

I'm sure you can do the rest ^^

EDIT : Nice quote at the end, Chris