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

learn more… | top users | synonyms

5
votes
0answers
74 views

IEEE 754 as a mathematical space

Integer operations in computers (i.e. 32-bit integers) probably can be represented best by modular arithmetic (because of integer overflows/underflows). What about IEEE 754 floating point arithmetic? ...
1
vote
1answer
43 views

Special Matrix 2-norm and F-norm Inequalities

This is a homework problem for my Numerical Linear Algebra course. It states the following: If A is an mxm nonsingular matrix, prove the following: (1)$\|A+(A^{*})^{-1}\| _{2} \ge 2$ ...
1
vote
1answer
49 views

Using the Gauss-Seidel method, will the matrix A converge

Just came back from my Numerical Analysis midterm, posting up the questions and my solutions for an estimation as to how I did. If you were to perform the Gauss-Seidel method on a matrix $A$, where ...
0
votes
0answers
29 views

Find the Cholesky Factorization of the matrix A

Just came from my Numerical Analysis midterm. There were 3 questions on it, trying to check my solutions to estimate my grade. Find the Cholesky of $$A = \begin{pmatrix}25 & 15 & -5\\15 & ...
1
vote
0answers
12 views

Finding eigenvalues in a region

I have an eigenvalue problem (of a very large (n~1000000) but sparse complex system) wherein I need to determine all the eigenvalues in a certain region(a rectangle) in the positive half plane. I am ...
2
votes
1answer
58 views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
2
votes
1answer
38 views

Is it true: $||A||_2 = \min\{ ||A||_1 ,||A||_3,||A||_4,\ldots \ldots, ||A||_{\infty},\|A\|_F\} $?

While running one algorithm , I observed the following peculiar relationship (at-least to me). I am not quite sure whether it is true in general, but I could not succeeded either in producing any ...
1
vote
2answers
38 views

Relation between condition number and perturbed matrix

Prove that if $A\vec{x} = \vec{b}$ and $(A+\delta{}A)(\vec{x}+\delta\vec{x}) = \vec{b}$, then $\dfrac{\|\delta\vec{x}\|/\|\vec{x}+\delta\vec{x}\|}{\|\delta{}A\|/\|A\|} \le \kappa{(A)}$, where ...
1
vote
1answer
42 views

What does it mean for a matrix to be nearly singular?

I am currently enrolled in numerical analysis course, and a terminology I have not heard of came up; nearly singular matrix. I know that a non-singular matrix is one where the column vectors are ...
0
votes
0answers
9 views

Predict values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set

I need to solve a problem about predicting values of some numerical vectors by using other numerical vectors with all these vectors in the same vector set, which is generated by one or more black box ...
0
votes
1answer
70 views

Condition number vs. reconstruction error

Suppose I want to solve a simple, linear inverse problem given by $\mathbf{y} = \mathbf{A} \cdot \mathbf{c}$ where $\mathbf{A}$ is an $M \times K$ matrix and I want to solve for $\mathbf{c}$ ($M$ = ...
2
votes
1answer
97 views

Parallel Algorithms for SVD

I just have completed a preliminar theoretical study of the important SVD decomposition. Now, I'm moving to numerical calculation of SVD. I would like to learn directly a parallel algorithm to ...
0
votes
0answers
17 views

How to go from linear “equality-constrained” least squares (LSE) to linear “less-equality-constrained” LSE

I am trying to figure out how to pass from one problem to other. The linear equality-constrained least squares problem can be solved using a generalized RQ factorization (lapack solves this using ...
1
vote
4answers
143 views

How to tell if two matrices are equal up to a permutation

Given two real rectangular matrices A, B how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations? (This is closely related to the question I ...
2
votes
0answers
41 views

Find the eigenvector with maximum overlap

Given a large symmetric matrix $A$, there are methods to find the largest or smaller eigenvalue, or the eigenvalue closest to some initial value. Is there any method to find the normalized ...
0
votes
1answer
32 views

A problem in a Question paper on Linear Transformation

anyone please solve it . Let the linear transformation $T: F^2\to F^3$ be defined by $T(x_1,x_2)=(x_1,x_1+x_2,x_2)$ . Then the nullity of T is 0 1 2 3 Also please mention how it is solved
1
vote
0answers
44 views

Representation of Uncertainty in linear systems

I have a linear uncertain system represented by a family of models: $\dot{x}=A_ix$,$i=1,\cdots,N$ I want to represent the system as: $A_i=A_0+B\Delta_iC$ subject to the condition that $\lVert ...
1
vote
0answers
62 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
3
votes
0answers
46 views

Conditions of a Monotonic Process?

$f$ is the output of a discrete time process described by $f(k)=\sum_{i=1}^{k-1}w_{ki}f(i)$ where $f(1)\geq0$ is a known initial condition and $w_{ki}\geq0$ are weights of previous states on the ...
1
vote
1answer
51 views

Inverse of a triangular matrix in a statistical problem

Can any one give to me idea how to solve this problem? Find the inverse of the triangular matrix T, where $ T =\left[ \begin{array}{ccc} I & J & J \\ 0 & I & J \\ 0 & 0 & I ...
0
votes
2answers
37 views

What is a good unstructured matrix solver?

If I were to hand you a general unstructured matrix A and a right hand side b, what would be your preferred iterative solver for solving Ax=b? Why?
1
vote
0answers
82 views

is it possible to generate a unique number given a set of N integers regardless of their permutation?

I need to efficiently compute an "id" for a set of N integers, the id needs to be unique if any of the numbers is different from some other set. At the same time the id needs to be the same if the ...
0
votes
0answers
23 views

Matrix conditioning with one degree of freedom

Given a not so well conditioned, NxK, N>>K matrix A with a certain structure. I have just one degree of freedom: I can multiply each row with a different factor. In formula: $$ \mathbf{B} = ...
2
votes
2answers
96 views

QR-factorization of a tridiagonal matrix super diagonals question

I understand it is possible to QR-factorize a tridiagonal matrix A by performing Given's plane rotations: $$ J(n-1,n)J(n-2,n-1)... J(1,2) A =R$$ where $R$ is upper triangular. I have read that in ...
3
votes
2answers
114 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
0answers
49 views

How can solve this differential equation (third equation )?

How can I solve this differential equation? $$ \frac{dy}{dx}=\sqrt{\frac{A}{y}+\frac{B}{y^2}+\frac{C}{y^4}+\frac{D}{y^5}+\frac{1}{(\frac{1}{y}+\frac{3}{y^2})^2}} $$ where $A,B,C,D$ are constants.
0
votes
2answers
48 views

Estimated time required to apply to matrix

I'm completely lost on this question, any help would be appreciated. Suppose the application of the Gaussian Elimination algorithm on a 50 by 50 matrix is timed at 500 μ seconds. How much time do you ...
0
votes
0answers
37 views

algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
2
votes
2answers
49 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...
1
vote
2answers
127 views

Showing that $A=B+\alpha \cdot I$ is an invertible matrix

Let $B$ be a non-zero random $n\times n$ matrix generated using the matlab command $B=rand(n,n)$. I need to show that $A=B+\alpha \cdot I$ is an invertible matrix, where $\alpha=\|B\|_{\infty}$. I ...
0
votes
1answer
37 views

Inequality matrix norm

Let $A$ be an $n\times n$ random matrix $A=rand(n,n)$. Let $\alpha=max_{i,j}|a_{ij}|$ (i.e, $\alpha$ is the largest entry in $A$ in absolute value).I need to show that $\ \alpha < \| A \|_{2}$. ...
0
votes
2answers
100 views

determine whether the equation $Ax = b$ is consistent for every $b$ in $\mathbb R^m$

I have two problems, the first one is the following matrix: $$\begin{bmatrix}1 & 0\\ -2 & 1\end{bmatrix}$$ where the RREF is $$\begin{bmatrix}1&0\\0&1\end{bmatrix}$$ and where the ...
2
votes
1answer
75 views

SOR and Gauss-Seidel Method - Confusion

Can anyone explain to me the SOR Method for finding the root(s) of a function? Its supposedly very similar to the Gauss-Seidel method. The Gauss-Seidel method, from my understanding, is similar to ...
1
vote
2answers
120 views

Householder QR Factorization for m by n Matrix (both m>=n and m<n)

Why in all of books I read about numerical linear algebra (e.g. Matrix Computations by Golub and Numerical Linear Algebra and Applications by Datta and many others), Householder QR factorization have ...
2
votes
3answers
148 views

What is the practical impact of a matrix's condition number?

Let's say I am trying to solve a square linear system $Ax = b$ for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by ...
0
votes
1answer
32 views

Is the scheme for generating $\displaystyle p_n=\left(\frac{1}{3}\right)^n$ stable? [duplicate]

Is the scheme for generating $\displaystyle p_n=\left(\frac{1}{3}\right)^n$ stable? $\displaystyle p_{n} = \frac{5}{6} p_{n-1} - \frac{1}{6} p_{n-2}$
0
votes
0answers
13 views

Singularity check for Homographies

I know that the standard singularity check for a matrix represented in some finite-precision format (IEEE-754 or whatnot) is "the matrix is singular if the reciprocal of the condition number of the ...
0
votes
1answer
139 views

Linear Transformation induced by the following matrix A

Suppose $T:\mathbb R^4\rightarrow\mathbb R^4$ is the transformation induced by the following matrix $A$. Determine whether $T$ is one-to-one and/or onto. If it is not one-to-one, show this by ...
1
vote
1answer
72 views

Partial QR factorization to solve least squares problem

I'm trying to understand how to solve a least squares problem of the form: $$\begin{bmatrix}A& B \end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = [b]$$ where I only explicitly solve for $y$ and ...
0
votes
2answers
34 views

Stability of method through step size

When investigating the stability of a system of ODEs,$$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ then let $y(t)=R^{-1}u(t)$ such that $$y'=\Lambda y.$$ Let ...
1
vote
1answer
41 views

Algorithm to generate normal matrices at random

I would like to generate normal matrices by an, say python, algorithm, that produces normal matrices distributed evenly in the limit of large n. I would not like to be restricted to Hermitian matrices ...
2
votes
1answer
39 views

Orthogonality on complex inner product space

Let $V$ be a complex inner product space. I need to show the following: $(x\ and \ y\ are\ orthogonal)\ \Rightarrow (\left \| \lambda x+\beta y \right \|^{2}=\left | \lambda \right |^{2}\left \| x ...
0
votes
0answers
16 views

Is any method which allows segmentation of long diagonalizing procedures?

This is a question for a smarter way of numerical computation. When I diagonalize a certain type of Vandermonde-matrices in Pari/GP ("mateigen(M)"), for instance of size 16x16 then this can be ...
0
votes
1answer
30 views

For which $a \in \mathbb{R}$ Jacobi converge?

I tried to solve the following problem and I don't know if it's correct and I have a few questions: Let \begin{align} A = \left[ {\begin{array}{cc} a & 1 & 0 \\ 1 & a & 1 \\ 0 & ...
0
votes
1answer
59 views

Can a 6-arm star be convex

Please help me with the following question. Suppose that the constant level contours of some function $V:\mathbb{R}^{2} \rightarrow \mathbb{R}$ have the shape of a symmetric 6-arm star. Can such a ...
0
votes
1answer
49 views

Stability analysis of Numerical Method

For a system of ODEs, I'm looking at the case where $$u'=Au$$ where $A$ is diagonalisable so $$u'=R\Lambda R^{-1}u.$$ In the notes I am looking at it goes on to say we can premultiply by $R^{-1}$ so ...
0
votes
0answers
42 views

(Numerical) Cholesky Decomposition of a Product of Matrices

Let $E$ be a symmetric positive definite matrix and let $O$ be an orthonormal matrix i.e. $O^{T}O=I$. Let $chol(A)=L$ such that $A=LL^{T}$ i.e. $chol(.)$ is the operation that returns the lower ...
1
vote
1answer
89 views

Does a Convex Function need to be Continuous

I have been trying the following problem and I am very confused. If possible the problem should be solved with derivatives. If the derivative exists for all the points on the graph then it is ...
0
votes
2answers
138 views

Quadratic Function must be positive definite to have a unique minimum

I have attempted the following question multiple times and I am very confused about the proof please help me solve it. Let $V(x)=a+b^{T}x+\frac{1}{2}x^{T}Cx$ for some $a \in \mathbb{R}, b \in ...
2
votes
2answers
153 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...