Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in \mathbb{Z}...
0
votes
0answers
25 views

absolute value matrix and derivation of A^1 b

I have a question who could I solve the following sentence? Given is the vector $\vec{b} \in \mathbb{R^n}$ and the function $f : GL(n,\mathbb{R}) \to \mathbb{R}^n$ with $f(A) = A^{-1}b$. Then ...
1
vote
0answers
16 views

why does matrix balancing improve the linear systems condition number of the eigenvector matrix?

Matrix balancing or diagonal scaling, where at each iteration we choose a diagonal matrix so that the row and column norms are approximately equal (Osborne, 1960, Parlett and Reinsch, 1969, many ...
0
votes
1answer
37 views

Matrix-free conjugate gradient

In the conjugate gradient method for solving $Ax = b$, to update the search direction $p$ you would need to evaluate the matrix-vector product $Ap$, i.e. making sure that each search direction are A-...
2
votes
2answers
48 views

If $A\in \mathbb{R}^n$ is symmetric and satisfies [the following] then $A$ is positive definite.

The following being: $$A(i,i) >\sum_{j\ne i} |A(i,j)| \quad \text{for} \quad i=1,2,...,n $$ How can I prove this?
1
vote
0answers
5 views

Fast square of a row-stochastic matrix

I would like to implement the square $M^2$ of a row-stochastic matrix $M$. Running time is critical. Are there any known algorithms that exploit the special nature of $M$ and are faster than the usual ...
1
vote
1answer
60 views

Please explain the last step of this newton method for system of equations

The step of working out x$^1$. I know the above is the formula but do they actually work out the inverse of the derivative matrix, is there a quicker way to do this?
2
votes
1answer
41 views

Prove that if $\|A\|<1$, then $\|(I-A)^{-1}\|\geq {1\over1+\|A\|}$.

Prove that if $\|A\|<1$, then $\|(I-A)^{-1}\|\geq {1\over1+\|A\|}$. I'm not sure how to prove this result. I see feel like a geometric series is involved though. Any solutions or hints are ...
0
votes
1answer
22 views

Prove These Properties of the Pseudoinverse

Prove these properties of the pseudo inverse: 1) $(AA^*)^{\dagger}={A^{\dagger}}^*A^{\dagger}$; 2) $A^{\dagger}=A^*(AA^*)^{\dagger}$. I'm quite sure I need to use the four properties of the pseudo ...
0
votes
5answers
88 views

Why, if a matrix $Q$ is orthogonal, then $Q^T Q = I$?

I was looking at the definition of an orthogonal matrix, which is as follows: Square matrix $Q$ is orthogonal if its columns are pairwise orthonormal, i.e., $$Q^TQ = I$$ Hence also ...
0
votes
1answer
18 views

Bounds on a quadratic form

I am currently in the middle of a proof where it would be nice to have some estimates on the size of a quadratic form. In particular, I am looking at $$x^TAx$$ where $A$ is "small" (in the analyst's ...
0
votes
1answer
24 views

Columns of a matrix linearly independent and spans

Let $\mathbf v_1, \mathbf v_2, ...,\mathbf v_n \in \Bbb R^n$ and let $P$ be the $n\times n$ matrix whose columns are $\mathbf v_1, \mathbf v_2, ...,\mathbf v_n$ I'm wondering why the followings are ...
0
votes
0answers
26 views

Compute the condition number of the matrix and show for what $\Delta x$ it is singular

Given the laplacian $N \times N$ matrix \begin{align*} A=\frac{1}{(\Delta x)^2}\begin{pmatrix} 2&-1& & &\\ -1&2&-1& &\\ &\ddots&\ddots&\ddots&\\ &...
0
votes
1answer
23 views

Nearest singular matrix

Let the SVD of $A \in \mathbb R^{{n}*{n}} $ be given as $A=\sum_{i=0}^n \sigma_{i}u_{i}v_{i}^{T}$ where $\sigma_{1}\gt \sigma_{2}>{...}>\sigma_{n-1}=\sigma_{n}>0 $ Compute a matrix $B$ such ...
3
votes
2answers
74 views

Efficiently solving many sets of linear equations without inversion or factorization

Suppose I have the normal set of linear equations $Ax = b$. If I can store and manipulate $A$ I have a variety of techniques available to me such as inversion, factorization, or an iterative method. ...
2
votes
2answers
33 views

Reciprocal of a quadratic form

I am working with an expression of the form $$ \frac{x^TAx}{{x^TBx}}$$ and would like to simplify it. I understand that vectors do not have inverses, but viewing the bottom number as a 1 by 1 matrix, $...
0
votes
1answer
16 views

Reference that Explains Preconditioning

I would like to understand Preconditioning techniques and why they work. Could someone provide a good reference for this type of information?
0
votes
1answer
28 views

How to find matrix $A$ from the relation: $A\times (A^TA)^{-1}\times A^T = B$

Kindly help me in the following: I have two Matrices, $A$ of size $(n\times m)$; and $B$ of size $(n\times n)$, where $n>m$. $A$ is unknown, but $B$ is known. $(A^TA)$ is invertible $B$ is ...
0
votes
3answers
40 views

Real problems solved with systems

Can anybody tell me where can I find some REAL problems (i.e. form real life) that can be solved using a 3x3 system of linear equations? Or, can anybody give me an example? A solution could be a ...
0
votes
2answers
31 views

solving an XOR matrix

I'm working on a somewhat-unique linear algebra problem arising from XORing files together in order to encode them, and then figuring out how to subsequently recreate the original files from the ...
2
votes
2answers
43 views

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix.

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix. So I need to show that $x^T(AA^T+\alpha I)x>0$ for all vectors $x$. I'm ...
1
vote
0answers
27 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
1
vote
1answer
20 views

Normal system of the least square method

I'm trying to show the following. $Pa$ is the approximation system of $y$. I want to show that finding the minimmum for the function $$f(a,y)=||Pa-y||_2^2$$ is equivalent to solve the normal system of ...
0
votes
0answers
12 views

Determinants using Row Reduction replacement

I am aware replacement does not affect the value of determinant when doing a row reduction. However, I realised there isn't a good explanation on how to handle different forms of replacement when ...
0
votes
1answer
16 views

Number of iterations for Gauss-Seidel

I am having some difficulty understanding the following solved problem: Question: Shouldn't we have $||T||^k_{\infty} ||e^{0}||_{\infty} \leq 10^{-6}$ instead? Where does the $5$ come from? And ...
3
votes
1answer
59 views

Detecting singular system during Cholesky resolution

I am solving small linear systems with a symmetric positive matrix by the method of Cholesky, without pivoting. "Bad" matrices are detected when you take the square root of a diagonal element, which ...
1
vote
2answers
19 views

Turning certain elements of a Matrix to zero through multiplication

Good evening, I apologize for the somewhat dumb question, I have to confess, Linear Algebra is not my strong suit. Secondly, the aim of this question is to apply this process to Excel - using VBA. ...
0
votes
0answers
21 views

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$?

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$, where $|T| =|[T_{ij}]| = [|T_{ij}|]$ ?
0
votes
1answer
15 views

Condition number of preconditioned system

Suppose we are solving an ill-conditioned system $Ax = b$, and we are trying to solve it using preconditioned technique. Given $\kappa (T)\approx \kappa(A)$, where $\kappa(A)$ is condition number of $...
1
vote
0answers
43 views

Why is it difficult (and not precise) to compute the rank of large matrix numerically?

I have a general question. I have a large square matrix ($n> 1000$) and it is needed to compute the rank of this matrix. I am reading that the computation of the rank for large matrices, can make ...
1
vote
1answer
36 views

Is an orthogonal matrix necessarily a permutation matrix?

Is an orthogonal matrix necessarily a permutation matrix? I believe the answer is no as a permutation matrix is a special case of an orthogonal matrix, but I am having a trouble finding a ...
0
votes
1answer
15 views

Proof with an Artificial Power Method

Suppose $A$ is $m\times m$ and has a complete set of orthonormal eigenvectors, $q_1, \ldots , q_m$, and with corresponding eigenvalues $\lambda_1,\ldots , \lambda_m$. Assume that the ordering is such ...
1
vote
2answers
17 views

Robustly map rotation matrix to axis-angle

The Wikipedia article for rotation matrix gives the following formula for converting from rotation matrix, $Q$, to axis-angle, $u$ and $\theta$: $$ \begin{align} x &= Q_{zy} - Q_{yz} \\ y &= ...
0
votes
0answers
12 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve $Ad^{(n)...
0
votes
0answers
26 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use it,...
0
votes
1answer
26 views

on a characterization of convergent matrices

Let $A\in \mathbb R^{n\times n}$ a matrix. It's known that the following statements are equivalent: 1) $A$ is convergent, namely $\lim_{k\to\infty}(A^k)_{ij}=0$ 2) $\lim_{k\to\infty}||A^k||=0$ for ...
0
votes
1answer
29 views

eigenvalues lesser than 1 implies affine maps are eventually contractive

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said $\textbf{contractive}$ if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ ...
1
vote
1answer
28 views

Determining the most appropriate set of eigenmodes for a modal decomposition of an experimental data set

I have a complex vector of the transverse amplitude and phase distribution of a laser beam, derived from experimental data. When modelling these field distributions, ordinarily the eigenmodes of the ...
1
vote
0answers
30 views

Eigenvalue equation and the diffusion equation

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system $\...
0
votes
1answer
17 views

Diagonalizing a Block Matrix with one non-zero Block column

I am trying to diagonalize $(M+N) \times (M+N)$ matrix $G\Gamma_LG^\dagger\Gamma_R $$ = \left(\begin{array}{cc} 0_{M\times M} & A_{M\times N} \\ 0_{N\times M} & B_{N\times N} \end{array}\...
3
votes
1answer
55 views

eigenvalues lesser than $1$ implies contractive map

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said contractive if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ we have $d(...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
1
vote
1answer
72 views

why do we say SVD can handle singular matrx when doing least square? Comparison of SVD and QR decomposition

I don't quite understand why we say that QR decomposition doesn't handle singular matrix, while SVD does when they are used for least square problem? My example in Matlab seems to support the ...
0
votes
0answers
13 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
14 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \...
1
vote
0answers
30 views

Spectral relaxation of k-means clustering

I am working on a presentation on Spectral relaxation of k-means clustering (http://papers.nips.cc/paper/1992-spectral-relaxation-for-k-means-clustering.pdf) and I am a bit stuck. I understand ...
2
votes
0answers
22 views

Is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay

I'm studying for a test and I'd like to know is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay. I have no clue to verify the claim. Can anyone give me ...
1
vote
0answers
16 views

Is it possible to construct a consistent unstable one step method of order 2? why?

Is it possible to construct a consistent unstable one step method of order 2? why? I think the answer is no but I have no clue to prove it. Can anyone give me some explanations? Thank you in advance ...
1
vote
1answer
43 views

Proving Equality of the Induced Matrix Norm

I need to prove that the induced matrix norm satisfies $$\|A\| = \max_{\|x\| = 1} \|Ax\|$$ Here's what I've done so far, and I'm not sure how to make the connection. By definition, $$\|A\| = \max_{x\...