2
votes
1answer
21 views

Eigenvalue of (1-0) matrix

Assume I have 2 matrices, each of size nxn with only 1 and 0 as entries in both. (n>10) The first matrix (call it A) has each row summing up to 2 (ie: on each row, it has two "1" and n-2 "0"). It is ...
0
votes
0answers
13 views

create sparse matrix from diagonal array in matlab

I have the 7 diagonal that come from a 3D finite volume discretization in separate arrays. These 7 arrays have 3D shape and correspond to each elements of the stencil for all points: top, bottom, ...
2
votes
0answers
33 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
0
votes
0answers
21 views

Diagonal Pivoting Algorithm

Commonly in LU factorization, partial pivoting is used. I know there is another pivoting which is diagonal pivoting. However, on the internet very few resources discussing diagonal pivoting (Only ...
1
vote
2answers
50 views

Exponential of a 3x3 lower bidiagonal matrix

I have a 3x3 matrix with non-zero entries ONLY along the main diagonal and the diagonal above. There are exactly two non zero diagonals in the matrix like this \begin{pmatrix} a & 0 & 0 \\ d ...
1
vote
1answer
17 views

Solving Ax = b where A is composed of diagonal blocks

I would like to solve the equation $Ax=b$ where $x\in\mathbb{R}^n$ and $A$ is of the form: $$A= \begin{bmatrix} D_1 & D_2 &D_3 \\ D_2 & D_4 & D_5 \\ D_3 & D_5 & D_6 ...
1
vote
1answer
15 views

Checksum Invariants for Matrix Inversion via Gaussian Elimination

In general, when solving $Ax=b$, we make the $[A|b]$ matrix and doing row operations to reduce the left hand side to an identity. It's painfully annoying to find mistakes in the process. Assuming we ...
0
votes
0answers
14 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
2
votes
0answers
35 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
0
votes
1answer
31 views

Householder Reflection

I am working on algorithms for SVD by first performing Householder transformation. I got my algorithm to work but I'm trying to gain a better intuition of it. My understanding is that the ...
0
votes
0answers
26 views

Rank and solvability of a matrix

I am working with linear complementarity problems (LCPs) which look for a solution $\mathbf{x} \in \mathbb{R}^{n}$ in the form $$ \begin{matrix} \mathbf{x} & \geq & 0 \\ ...
1
vote
2answers
32 views

Square Idempotent matrix: efficient algorithms for finding eigenvectors

Given a square idempotent $N \times N$ matrix $A$ with large $N$, and a priori knowledge of the rank $K$, what is the most efficient way to compute the $K$ eigenvectors corresponding to the $K$ ...
0
votes
1answer
31 views

matrix exponential and Spectral abscissa

Prove that $\lim_{t \rightarrow \infty} \|e^{tA}\| = 0$ if and only if $\alpha(A) < 0 $, where $\alpha$ is the Spectral abscissa, defined as $\max{Re(\lambda_i)}$. I tried to approach this ...
2
votes
0answers
29 views

Smallest set of Liner equations, which exactly fit a set of points

I have a set of 2-d points,(it can be of any arbitrary dimension n). I want to find the minimum set of straight lines(linear equations) which exactly passes through the given 2-d points (unlike ...
4
votes
4answers
120 views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and ...
0
votes
3answers
50 views

About matrix products $A^{T}A$ and $ AA^{T} $

I'm investigating the relationship between 2-norms and eigenvalues of $A^{T}A$ and $ AA^{T} $, in order to better understand the SVD decomposition. How can I prove that $A^{T}A$ and $ AA^{T} $ are ...
1
vote
0answers
37 views

Inverse of the sum of a symmetric and diagonal matrices

I have two square matrices, $A$ and $B$. $A$ is a block symmetric matrix with 1's along the diagonal (and therefore 1's in whole blocks along the diagonal). $B$ is a block diagonal, with the same ...
0
votes
0answers
7 views

need to determine weights so that quadrature formula holds

Let $l$ be an interval on the real axis, $t_1,...,t_n$ be distinct $n$ points, then there exists n numbers $m_1,...,m_n$ such that the quadrature formula, $\int_l p(t)dt = m_1p(t_1) + ... + ...
1
vote
1answer
32 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
0
votes
0answers
41 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
4
votes
2answers
363 views

Algorithm to find an orthogonal basis (orthogonal to a given vector)

Let $K$ be a given integer, with $K$ even (and "large"). Let $\mathbf{v} \in \mathbb{R}^{K \times 1}$ be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix ...
0
votes
1answer
31 views

Is it possible to solve a system of equations comprising FFTs?

Consider the following known matrices, A, B, C and these unknown matrices X,Y, all of which comprise values in the Real domain. Also consider $F(x)$ as the *Fast Fourier Transform function* (the ...
3
votes
1answer
94 views

How to solve this system of 3 equations with 3 variables?

I stumbled upon this system with constants $a_{i,j}>0$ that I want to solve for $x,y,z \in\mathbb{R}$: \begin{align} a_{2,1}y+a_{3,1}z=& x(y+z) \\ a_{1,2}x+a_{3,2}z=& y(x+z) \\ ...
0
votes
1answer
32 views

Inverse Square root of a rectangular matrix

I am trying to compute the inverse square root ($X^{-1/2}$) of a $n \times p$ matrix with $n > p$. I was wondering if we can compute it via SVD just as we do it for square diagonalizable matrices ...
0
votes
1answer
20 views

Residual norm for iterative scheme

Consider a linear system $A\vec{x} = \vec{b}$, where $A \in \mathbb{R}^{m\times{}m}$ is non-singular and positive definite. Given the following iteration scheme $\vec{x}^{(k+1)} = \vec{x}^{(k)} + ...
0
votes
0answers
21 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 & ...
2
votes
1answer
39 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
37 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
29 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 ...
0
votes
0answers
8 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
41 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$ = ...
1
vote
4answers
116 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 ...
0
votes
1answer
24 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
39 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
57 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
41 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
43 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 ...
1
vote
0answers
79 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
20 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
77 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
70 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 ...
2
votes
2answers
44 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
115 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
27 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
1answer
48 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 ...
1
vote
2answers
94 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 ...
0
votes
1answer
94 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
37 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
36 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
27 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 ...